Hash 表实现

Hash 表、二叉树、链表是最常见的数据结构。 本文中用C++来实现一个简单的哈希表，帮助理解哈希表是怎样运作的。为了简化代码并突出逻辑，采用简单的除余数作为散列函数，用线性探测来处理碰撞。

线性探查法是用开放定址法处理冲突的一种最简单的探查方法。

它从发生冲突的d单元起，依次探查下一个单元
当达到下标为m—l的表尾单元时，下一个探查的单元是下标为O的表首单元。
即把散列表看作为首尾相接的循环表，直到碰到一个空闲单元或探查完所有单元为止。
这种方法的探查序列为d，d+l，d+2，…，或表示为( d + i ) ％ m,( O ≤ i ≤ m-1)。
当然，这里的i在最坏的情况下才能取值到m-1，一般只需取前几个值就可能找到一个空闲单元。找到一个空闲单元后，把发生冲突的待插入元素存入该单元即可。

如果上述你看的比较晕，就直接看代码吧。

Hash 列表项

用 HashItem 表示,这里 key 和 value 都只用最简单的 Int 表示了，换成任何数值类型都是可以的.

class HashItem{
private:
    int key;
    int value;
public:
    HashItem(int key,int value){
        this->key = key;
        this->value = value;
    }
    int getKey(){
        return key;
    }
    int getValue(){
        return value;
    }
};

HashMap 定义

const int TABLE_SIZE = 128;

class HashMap{
private:
    HashItem **table;
public:
    HashMap(){
        // 动态分配 table 内存
        table = new HashItem *[TABLE_SIZE];
        for (int i = 0; i < TABLE_SIZE; i++) {
            table[i] = NULL;
        }
    }
    
    int get(int key){
        int hash = (key % TABLE_SIZE);
        // 处理碰撞，从当前位置一直往下找
        while (table[hash] != NULL && table[hash]->getKey() != key){
            hash = (hash + 1) %TABLE_SIZE;
        }
        if (table[hash] == NULL){
            return -1;
        } else {
            return table[hash]->getValue();
        }
    }
    
    void put(int key,int value) {
        int hash = (key % TABLE_SIZE);
        // 处理碰撞，从当前位置一直往下找
        while (table[hash] != NULL && table[hash]->getKey() != key) {
            hash = (hash + 1) %TABLE_SIZE;
        }
        if (table[hash] != NULL) {
            delete table[hash];
        }
        table[hash] = new HashItem(key,value);
    }
    
    ~HashMap(){
        // 析构函数记得释放 table 的每一项，以及 table
        for (int i = 0; i < TABLE_SIZE; i++) {
            if (table[i] != NULL) {
                delete table[i];
            }
        }
        delete[] table;
    }
};

主函数如下：

int main(int argc, char * argv[]){
    HashMap hashMap;
    hashMap.put(1,10);
    hashMap.put(2,20);
    hashMap.put(129, 15);
    cout<<hashMap.get(1)<<endl; // 10
    cout<<hashMap.get(2)<<endl; // 20
    cout<<hashMap.get(129)<<endl; // 15
    return 0;
}