Wikipedia: 散列表（Hash table，也叫哈希表），是根据关键字（Key value）而直接访问在内存存储位置的数据结构。 也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。 这个映射函数称做散列函数，存放记录的数组称做散列表

哈希表、二叉树、链表是最常见的数据结构，涵盖了程序员面试和笔试中几乎所有的数据结构相关问题。 本文中用C++来实现一个简单的哈希表，帮助理解哈希表是怎样运作的。为了简化代码并突出逻辑，采用简单的除余数作为散列函数，用线性探测来处理碰撞。

哈希列表项

先声明一个哈希列表项的类，来封装key和value。之所以需要在表项中存储key是因为碰撞的存在，往往不能够通过散列函数直接得到地址，还需要进一步的判断，因此列表项中需要存储key值。 不过列表项的实现是很直观的：

class HashItem{
    int key, val;
public:
    HashItem(int k, int k): key(k), val(v){}
    const int& getKey(){
        return key;
    }
    const int& getVal(){
        return val;
    }
};

当然key可以是任何支持判等运算的类型，这里设为int是为了简化逻辑。

简单的哈希表

有了HashItem便很容易写出HashTable，需要注意的是在析构函数中要记得释放动态内存。

class HashTable{
    static const int SIZE = 256;
    HashItem ** table;      // 注意这是二级指针，指向对个HashItem*
public:
    HashTable(){
        table  = new HashItem*[SIZE]();     // 这里的括号是为了初始化为0
    }
    void set(key, val){
        int idx = key%SIZE;
        if(table[idx]) delete table[idx];
        table[idx] = new HashItem(key, val);
    }
    const int get(key){
        int idx = key%SIZE;
        return table[idx] ? table[idx]->getVal() : -1;      // 注意这里需要判断key不存在的情况
    }
    ~HashTable(){
        for(int i=0; i<SIZE; i++)
            if(table[i]) delete table[i];
        delete[] table;                     // 别忘了table本身也是要销毁的
    }
};

上述算法中使用C风格的资源管理不是异常安全的。比如HashTable::set中的HashItem构造函数一旦抛出异常，table[idx]将处于无效的状态。 Effective C++: Item 29中提到了使用智能指针和copy and swap范式可以为资源替换提供异常安全，在HashTable的例子中，可以用shared_ptr来存储HashTable*：

class HashTable{
    vector<shared_ptr<HashItem>> table(SIZE);
    ...
public:
    void set(key, val){
        int idx = key%SIZE;
        shared_ptr<HashItem> tmp(new HashItem(key, val));
        swap(tmp, table[idx]);
    }
    ...
};

处理碰撞

哈希表的思路很简单：将key映射到一个下标，然后把value存进去。但有时多个key会映射到同一个下标，比如key1 == SIZE + k和k2 = SIZE*2 + K的下标均为k。 这时便需要处理碰撞了，我们使用最简单的线性探测（linear probing）来重新实现HashTable::set。

void HashTable::set(key, val){
    int idx = key%SIZE;
    while(table[idx] && table[idx]->getKey() != key)
        idx = (idx+1)%SIZE;           // 当SIZE不够大时，这里会陷入死循环。可以检测一下。
    if(table[idx]) delete table[idx];
    table[idx] = new HashItem(key, val);
}

加入处理碰撞后，HashTable::get也需要做相应的改动：

const int HashTable::get(key){
    int idx = key%SIZE;
    while(table[idx] && table[idx]->getKey() != key)
        idx = (idx+1)%SIZE;           // SIZE不够大时，这里也面临死循环的问题
    return table[idx] ? table[idx]->getVal() : -1;      // 注意这里需要判断key不存在的情况
}

本文采用 知识共享署名 4.0 国际许可协议（CC-BY 4.0）进行许可，转载注明来源即可： https://harttle.land/2015/09/29/cpp-hashtable.html。如有疏漏、谬误、侵权请通过评论或 邮件 指出。