首页 > 代码库 > 算法学习 - Hash Table操作，分离链接法解决哈希冲突

算法学习 - Hash Table操作，分离链接法解决哈希冲突

2024-07-15 23:50:05   221人阅读

分离链接法

hash table是映射机制的，最大的优点就是它的操作是O(1)级别的。但是会出现哈希冲突，这就需要几种办法来解决。这里先说一种：分离链接法。

就是当插入的位置已经存在一个值之后，那么在这个值之后插入，就可以了，也叫拉链法。（但是其实会降低查找速度，变成O(n)级别）

下面是代码：

//
//  main.cpp
//  HashTable_SeparateChaining
//
//  Created by Alps on 14-8-5.
//  Copyright (c) 2014年 chen. All rights reserved.
//

#include <iostream>
#include <math.h>
#include "HashTable.h"
#define MinTableSize 1

using namespace std;

bool Prime(int size){
    for (int i = 2; i < sqrt(size); i++) {
        if (size%i == 0) {
            return false;
        }
    }
    return true;
}

int NextPrime(int Tablesize){
    if (Tablesize <= 2) {
        return 2;
    }else{
        while (!Prime(Tablesize)) {
            Tablesize++;
        }
        return Tablesize;
    }
    return Tablesize;
}

HashTable InitializeTable(int Tablesize){
    HashTable H;
    int i;
    
    if (Tablesize < MinTableSize) {
//        Error("table size is too small!");
        exit(0);
    }
    H = (HashTable)malloc(sizeof(struct HashTb));
    if (H == NULL) {
        //Error("out of space");
        exit(0);
    }
    H->Tablesize = NextPrime(Tablesize);
    H->TheList = (List*)malloc(sizeof(List) * H->Tablesize);
    for (i = 0; i < H->Tablesize; i++) {
        H->TheList[i] = (List)malloc(sizeof(struct ListNode));
        H->TheList[i]->Next = NULL;
    }
    
    return H;
}

int Hash(int key, int Tablesize){
    return key%Tablesize;
}

Position Find(ElementType key, HashTable H){
    int i = Hash(key, H->Tablesize);
    List L = H->TheList[i]->Next;
    while (L != NULL && L->element != key) {
        L = L->Next;
    }
    return L;
}

void Insert(ElementType key, HashTable H){
    if (Find(key, H) == NULL) {
        int i = Hash(key, H->Tablesize);
        List L = (List)malloc(sizeof(struct ListNode));
        L->element = key;
        Position P = H->TheList[i];
        L->Next = P->Next;
        P->Next = L;
    }
}


int main(int argc, const char * argv[])
{
    HashTable H = InitializeTable(10);
    printf("%d\n",H->Tablesize);
    Insert(5, H);
    Insert(3, H);
    Position P = Find(5, H);
    printf("%d\n",P->element);
    return 0;
}


下面是头文件：
//
//  HashTable.h
//  HashTable_SeparateChaining
//
//  Created by Alps on 14-8-5.
//  Copyright (c) 2014年 chen. All rights reserved.
//

#ifndef HashTable_SeparateChaining_HashTable_h
#define HashTable_SeparateChaining_HashTable_h
#define ElementType int

struct ListNode;
typedef struct ListNode *Position;
struct HashTb;
typedef HashTb *HashTable;

HashTable InitializeTable(int Tablesize);
void Destory(HashTable H);
Position Find(ElementType key, HashTable H);
void Insert(ElementType key, HashTable H);

#endif

struct ListNode{
    ElementType element;
    Position Next;
};

typedef Position List;

struct HashTb{
    int Tablesize;
    List * TheList;
};




联系
我们