数据结构中散列表「哈希表」经典之冲突处理

1. 基本概念

哈希表（Hash Table）又叫散列表，是根据关键码值(Key Value)而直接进行访问的数据结构。哈希表通过把关键码值映射到表中的一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数，存放记录的数组叫做哈希表。

当两个不同的关键码值映射到同一个位置时就产生了哈希冲突，需要解决冲突问题，不同的解决方法就是哈希表的不同实现方法之一。

2. 哈希冲突处理方法

2.1. 开放地址法

开放地址哈希表中，当哈希函数发现冲突时，会尝试在其他的单元格中寻找空的单元格进行存储。最普遍的开放地址哈希函数包括线性寻址和二次探测，其中线性寻址顾名思义就是按线性的顺序去寻找空的位置，而二次探测则是按照一定的探测序列去寻找空的位置。

线性探测：

int hash(int key)
{
    return key % size;
}
void insert(int key)
{
    int h = hash(key);
    while(hashTable[h] != NULL && hashTable[h] != "DELETED")
    {
        h = (h + 1) % size;
    }
    hashTable[h] = newNode;
}

二次探测：

int hash(int key)
{
    return key % size;
}
void insert(int key)
{
    int h = hash(key);
    for(int i = 0; i < size; i++)
    {
        int pos = (h + i * i) % size;
        if(hashTable[pos] == NULL || hashTable[pos] == "DELETED")
        {
            hashTable[pos] = newNode;
            break;
        }
    }
}

开放地址哈希表的优点在于不需要一开始就分配完整的空间，但是当数据量特别大的时候容易产生大量的冲突，严重影响效率。

2.2. 链地址法

链地址哈希表中，当哈希函数发现冲突时，会将新的数据存放到同一个位置的链表中，因此也叫做拉链法。链表可以用数组实现也可以用指针实现。

链地址哈希表：

const int MAXN = 1000000;
const int MOD = 1000003;
struct ListNode
{
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};
ListNode* hashTable[MOD];
int hash(int key)
{
    return key % MOD;
}
void insert(int key)
{
    int h = hash(key);
    ListNode* p = hashTable[h];
    while(p != NULL && p->val != key)
    {
        p = p->next;
    }
    if(p == NULL)
    {
        ListNode* newHead = new ListNode(key);
        newHead->next = hashTable[h];
        hashTable[h] = newHead;
    }
}

链地址哈希表的优点在于可以解决冲突问题，但是当链表的长度过长时，搜索效率将会降低，严重影响效率。

2.3. 其他方法

还有一些其他的冲突解决方法，比如说：

双散列

建立公共溢出区

但是这些方法不如开放地址法或链地址法来得常用和实用。总体而言，哈希表的冲突处理方法在不同的场景和需求下会有不同的选择。