哈希表、哈希桶（C++实现）【STL】_c++中的哈希表的更新和查找效率是平均o(1)

1. 哈希

1.1 概念

哈希（hash，中文：散列；音译：哈希），是一种算法思想，又称散列算法、哈希函数、散列函数等。哈希函数能指导任何一种数据，构造出一种储存结构，这种储存结构能够通过某种函数使得元素的储存位置和数据本身的值（一般称之为key值）能够建立一种映射关系，这样在查找数据时就可以通过同一个哈希函数通过key值迅速找到元素的位置。

这种查找思想类似于数组的随机访问，它的时间复杂度为$O(1)$。不同于以往，即便是红黑树，它的查找时间复杂度也是$O(lo{g}_{2}N))$。原因是不论是顺序结构还是平衡树中，元素的key值和储存之间没有映射关系，因此在查找元素时必须以key值进行若干次比较，而这恰恰增加了时间复杂度。

map和set底层都是用二叉搜索树实现的，因而他们都是有序的。而unordered_set和unorder_map中的元素都是无序的，原因是它们底层都使用了哈希思想实现。前者能使用双向迭代器，后者是单向迭代器。

这样看，前者更占优势，但为什么还有有unordered（无序）。因为后者底层使用了哈希算法实现，所以使用这种容器查找数据的效率最高，时间复杂度是$O(1)$，虽然后者的插入效率略低，但仍然能够持平。

在了解unordered_set和unorder_map容器之前，需要对哈希思想有一定了解。

从哈希查找的效率可以知道，哈希专攻的是查找功能。

1.2 例子

生活中也有不少直接或间接使用哈希思想的例子，比如：

• 英语词典；
• 花名册，只要知道你的学号就能快速找到你的个人信息；
• 各种数据库中账号和密码的映射…

因为有这样的需求，一种新的数据结构诞生了：散列表。

散列表（hash table）也叫做哈希表，它提供了键（key）和值（value）之间的映射关系，只要给出一个key，就能迅速找到对应的value，时间复杂度接近$O(1)$。

在列举出来的例子中，大多数元素的key值都是以字符串的形式存储的，那么如何用一个哈希函数将字符串转化为一个整型的数组下标值呢？

哈希表的本质就是数组，使用哈希函数算出来的每个元素对应的位置都是数组的下标。这就是哈希函数保证查找元素的时间复杂度如此低的主要原因。

1.3 散列表的基本原理

1.3.1 哈希函数

在不同的语言中，哈希函数的实现都有所区别。最简单的哈希函数实现方式是按数组长度取模运算：

为了演示方便，key值本身就是整型值，在后文中会介绍将字符串转化为整型值的哈希函数：
$$hash(key)=key\%capacity$$

例如，对于集合中元素：{0, 3, 15, 8, 12}，它们存储在数组长度为10的哈希表中的位置如上。

1.3.2 哈希表的读写操作

• 插入：根据元素的key值，用哈希函数计算出它的储存位置，并将元素存放在对应位置处。

从这样的表述中大概可以猜到，要想让查找效率时间复杂度达到$O(1)$，就必须使用数组存放数据，才能实现随机访问的效果。

根据key值用哈希函数算出来的存储位置就是数组的下标，

• 查找：用同一个哈希函数，根据元素的key值计算出元素的储存位置，这个位置的元素的key值与要查找的key值相等，则取出该元素，查找成功；反之则否。

这种查找和插入的过程是类似的，都是先用（要存放的元素或要查找的元素的）key值计算处它的存储位置，然后存放或取出该元素。

当查找元素时，只需要通过key值使用同一个哈希函数即可直接找到元素对应的位置，查找效率堪比数组。

为什么说「堪比」呢？

• 因为这种按数组长度取模运算的哈希算法会出现不同值对应同一个下标的情况，叫做哈希冲突。

1.4 哈希冲突

如上面的例子中，如果集合中多了几个这样的元素：

现在，新增的元素经过同一个哈希函数得到的数组下标值都已经被占有了，像这种不同的值映射到同一位置的情况，就叫做哈希冲突。

造成哈希冲突的原因之一是：哈希函数的设计不合理。

哈希函数的设计原则：

• 哈希函数的定义域必须包含需要储存的全部key值，如果哈希表允许含有m个元素，那么哈希函数的值域必须在[0, m-1]（数组下标从0开始）。
• 哈希函数计算出来的地址能较均匀地分散在这个哈希表中。
• 哈希函数应该比较简单。

哈希冲突是无法避免的，解决哈希冲突的方法主要有两种，一种是开放寻址法，一种是链表法。

1.4.1 开放寻址法

闭散列，也叫开放定址法，当发生哈希冲突时，可以将元素放在被占的元素的下一个不为空的位置，以此类推，直到放满哈希表为止。

开放寻址法根据“开放”的程度不同，分为两种：

• 线性探测
• 二次探测

线性探测

• 当发生线性冲突时，从发生冲突的位置开始，依次向后探测，直到遇到空位置为止。

$$H_i=(H_0+i)\%cap,(i=1,2,3,...)$$

其中：

• $H_0$：根据元素的key值通过哈希函数得到的数组下标值；
• $H_i$：造成冲突的元素（下标被占用的元素）通过线性探测以后得到的空位置；
• $i$：第i次冲突；
• $cap$：表的长度。

同样，以上面的例子而言：

优点

思路简单，容易实现。

缺陷

像这样按数组长度取模运算的哈希函数，我们把它叫做除留余数法（下文还会介绍若干常见哈希函数）。随着哈希表中数据的增多，发生哈希冲突的次数也会增加，且不限于key值相同与否，上图中的示例中两个key值仅冲突了一次。如果再插入key值=20的元素，就要发生6次哈希冲突。

随着元素个数的增多，插入元素发生哈希冲突的可能性越大，查找的效率也会随之变低。

从宏观看，发生线性冲突的主要原因就是因为插入元素的分布不均匀，根据key值通过哈希函数算出来的下标值总是集中在某些区域。那么线性探测就像“违章建筑”，各自侵占别的哈希值的位置。

分布不均造成的“违章建筑”，从数组的容量利用率来看，就是插入的元素太“满”了才会把别的元素挤到其他地方，进而产生链式反应。所以可以限制插入元素的个数，减少不同的集中区域之间交叉的可能性。

负载因子

$$负载因子=有效数据个数/数组长度$$

改变负载因子有两方面，有效数据个数（分子）和数组长度（分母），由于数据个数无法限制，那么我们可以通过改变数组长度进而改变负载因子。

• 负载因子越大，发生哈希冲突的概率越高，操作的效率越低。
• 负载因子越小，发生哈希冲突的概率越低，操作的效率越高。

同样地，将上面例子中数组的大小增加到20：

当增加数组长度时，上面的同一组数据中，不论是未发生还是发生冲突的，都更均匀地分散在数组中。

负载因子的表达式说明负载因子其实就是空间利用率，负载因子越小，空间利用率越低。

一般而言，对于开放定址法，负载因子一般控制在[0.7, 0.8]，超过0.8就会导致在查找时的效率呈指数级下降。

原因是CPU缓存不命中率(cache missing)会呈指数级上升。

链接：浅谈 Cache

简言之，根据局部性原理，CPU下次访问的数据很可能在上次访问的数据的周围。

所以，使用数组实现线性探测时，控制扩容与否的主要因素已经不再是它是否已满，而是负载因子是否超出范围。负载因子的存在，会让哈希表永远不会满。

二次探测

线性探测的缺点就是容易因为哈希值过于密集而出现“违章建筑”，出现链式反应，一堆影响另一堆。虽提供了可行的方案，使用负载因子控制容量，但是它的应用场景也是有限的。

而二次探测是在线性探测的基础上而言的：
$$H_i=(H_0+i^2)\%cap,(i=1,2,3,...)$$
其中：

• $H_0$：根据元素的key值通过哈希函数得到的数组下标值；
• $H_i$：造成冲突的元素（下标被占用的元素）通过线性探测以后得到的空位置；
• i：第i次冲突；
• $cap$：表的长度。

如果$j=i^2$即
$$H_i=(H_0+j)\%cap,(j=1,4,9,...)$$

用一个例子理解：

理解二次探测的过程，最重要的是理解i的含义，遇到几次冲突，i就是几。

优点

二次探测是对线性探测的优化，它对元素的分散程度大于线性探测中控制负载因子带来的效果更好，毕竟是平方运算，当冲突次数越多，存放的位置也会离第一个冲突的位置越远，也就越分散。

缺陷

由于二次探测是线性探测的优化，所以它也需要用负载因子控制哈希表的容量。

总地来说，开放寻址法（闭散列）最大的缺陷就是空间利用率较低，这同时也是哈希的缺陷，即使不采用上述优化，这种处理方式也会浪费一些空间。

1.4.2 链表法

闭散列，也叫链表法、链地址法、拉链法。将同一个哈希值对应的不同的key值视为一个集合，用一个链表保存起来，把它叫做哈希桶。即每个哈希桶存放的都是哈希值相同的不同key值，每个哈希桶（链表）的首地址会被保存在哈希表（数组）中，下标对应的就是哈希桶的哈希值。

插入元素时，只需要根据key值通过哈希函数得出的下标找到对应的链表（哈希桶），依次往后链接即可。

用例子理解哈希桶组成的哈希表：

将数组横着放，链表竖着放，这样就能理解为什么把这个存储相同哈希值的不同key值的链表叫做哈希桶了。

一个题外话：

学到这里突然明白了为什么要有链表的存在，因为它能解决像这样的哈希冲突问题，非常巧妙。

这也是数据结构存在的意义，Data Structure，就是用来存取数据的结构。例如在Linux操作系统中，一切皆文件，要对文件管理就必须先描述它们之间的关系，然后用统一的方法组织，这样才能对文件管理。

优点

不会产生数据之间的链式反应，不同哈希值对应的key值不会互相侵占位置。所以负载因子的存在只会降低空间利用率，所以开散列的负载因子可以超过1，一般控制在1以下。

• 哈希桶实现的哈希表空间利用率高；
• 哈希桶在极端条件下还可以用红黑树解决。

缺点

极端情况：

全部元素的key值对应的哈希值都相同，它们都发生哈希冲突，全部都链接到同一个哈希桶中：

这样查找的效率退化为$O(N)$，在此之前，我们学过的最高效的查找结构就是红黑树，可以将链表换成红黑树。时间复杂度就提升到$O(lo{g}_{2}N)$。

在Java常用的HashMap中，当一个桶中元素个数超过8时，就会将链表换成红黑树。当少于8时，依然会使用链表存储数据。但这不是必须的，因为有的时候哈希表中负载因子也会增大，最终会使哈希表扩容，哈希冲突次数减少，一个桶中元素的个数也会减少。

2. 实现闭散列哈希表

实现闭散列哈希表，其实就是控制数组下标对元素进行增删查改操作。

2.1 哈希表存储结构

闭散列的查找有个坑，如果出现这种情况：

所以可以用枚举常量规定每个位置的状态：

// 枚举常量表示位置状态
enum State
{
    EMPTY,
    EXIST,
    DELETE
};
1
2
3
4
5
6
7

用枚举常量标识状态时可行的，原因是如果按照原来的思路，通常会将未存放的位置的值置为-1等，但假如要放入的元素key值本来就为-1呢？

每个位置有三种情况，即已被占有（EXIST）、已被删除（DELETE）、未被占有（EMPTY）。之所以要设置为DELETE，就是为了避免上面的坑。

单位存储结构

那么，哈希表中每个位置都应该包含位置的状态和数据：

// 哈希表中每个位置的存储结构
template<class K, class V>
struct HashData
{
    pair<K, V> _kv;
    State _state = EMPTY;
};
1
2
3
4
5
6
7

由于哈希是由key值计算的数组下标，存的是元素的value值，所以每个元素存储的是一个键值对，可以用pair结构体保存。

当创建出一个位置时，它的默认状态是空，所以给_state以缺省值EMPTY。

哈希表

对于整个哈希表(HashTable)而言，其本质是一个数组，因为闭散列的优化中会使用负载因子控制数组长度，所以需要一个动态长度的数组，在此，我们直接使用STL中的vector容器，它的每个元素的类型都是HashData。

template<class K, class V>
class HashTable
{
public:
    // ...
private:
    vector<HashData<K, V>> _table; // 哈希表
    size_t _n = 0;                 // 负载因子
};
1
2
3
4
5
6
7
8
9

注意，数组元素的类型只是每个位置的类型，因为每个位置要包含状态和数据，所以它不仅仅是一个下标指定的位置。

key值转整型

在本文开头介绍哈希函数时，说到key值是要转为整型才能对数组长度取模运算的，上文中都是以整型的key值为例，所以并未提到key值转整型的例子。由于现实中key值还可能是字符串等类型，所以可以使用仿函数+模板特化的方式来匹配不同类型的key值转化为整型值。

直接转整型

当key值本身是整型时，只需要返回强转为size_t后的值即可。

size_t 类型定义在cstddef头文件中，该文件是C标准库的头文件stddef.h的C++版。 它是一个与机器相关的unsigned类型，其大小足以保证存储内存中对象的大小。 --来源于网络

至于为什么要转化成unsigned类型，是因为当%取模运算操作符的右边为负数时，本身就会发生隐式类型转换，将负数转换为正数。

如：

-17 % 10 = -7

17 % -10 = 7

-17 % -10 = -7

// 仿函数
template<class K>
struct HashFunc
{
    size_t operator()(const K& key)
    {
        return (size_t)key;
    }
};
1
2
3
4
5
6
7
8
9

同时，哈希表的类中也要增加一个模板参数，以将key值转化为整型值：

template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
    // ...
}
1
2
3
4
5

将key值转化函数的缺省值设置为HashFunc。

字符串转整型

许多场景中，key值都是字符串类型的，将字符串转化为整型值有很多办法，比如首字符ASCII值，但是这样哈希冲突的概率太大了。字符串作为一种经常被使用的类型，有许多大佬都对字符串转整型的哈希函数有自己的见解，其主流思想是：

• 将字符串的每个字符的ASCII值累加得到整型的哈希值；

BKDRHash算法：

这是是Kernighan和Dennis在《The C programming language》中提出的，它对每次累加后的结果再乘以素数131。

至于为什么是素数131，这是个数学问题，众所周知计算机科学家都是数学家。

因为我们之前已经实现了整型本身转整型的仿函数，所以如果想要让别的类型转化为整型，需要用到模板的特化：

// BKDRHash算法
template<>
struct HashFunc<string>
{
    size_t operator()(const string& key)
    {
        size_t ret = 0;
        for(auto& e : key)
        {
            ret *= 131;
            ret += e;
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.2 闭散列哈希表的查找

1. 判断哈希表长度是否为0，是0则查找失败；
2. 根据key值通过哈希函数得到下标值；
3. 从得到的下标值开始，在哈希表中向后线性探测，遇到DELETE继续；遇到EMPTY结束，查找失败；遇到key值相等的元素则查找成功。

// 查找函数
HashData<K, V>* Find(const K& key)
{
    if (_table.size() == 0)
    {
        return nullptr;
    }

    Hash hash;
    size_t size = _table.size();
    size_t start = hash(key) % size;    // 根据key值通过哈希函数得到下标值
    size_t hashi = start;

    while (_table[hashi]._state != EMPTY)
    {
        if (_table[hashi]._state != DELETE && _table[hashi]._kv.first == key)
        {
            return &_table[hashi];
        }
        hashi++;
        hashi %= size;

        if (hashi == start)
        {
            break;
        }
    }
    return nullptr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

2.3 闭散列哈希表的插入

插入步骤

1. 若哈希表中已存在key值对应的元素，插入失败；
2. 以负载因子为指标判断是否要对哈希表扩容；
3. 插入元素；
4. 有效元素计数器+1。

扩容步骤

1. 若哈希表最初的大小为0，则设置哈希表大小为10；
2. 若哈希表的负载因子大于0.7，则需要创建一个大小是原大小两倍的新数组。然后遍历原数组，将所有元素插入到新数组；
3. 将新的数组的地址更新到哈希表中。

因为扩容改变了数组的长度，哈希函数也随之变化，每个元素的位置都有可能改变。

更新哈希表的步骤

1. 根据元素的key值通过新的哈希函数得到下标值；
2. 若产生哈希冲突，则从哈希冲突的位置开始，向后线性探测，直到遇到状态为EMPTY或DELETE的位置；
3. 插入元素，将位置的状态更新为EXIST。

bool Insert(const pair<K, V> kv)
{
    if (Find(kv.first) != nullptr)            // 哈希表中已存在相同key值的元素
    {
        return false;
    }

    // 扩容操作
    if (_table.size() == 0 || _size * 10 / _table.size() >= 7) // 扩容
    {
        size_t newSize = _table.size() == 0 ? 10 : _table.size() * 2;

        HashTable<K, V, Hash> newHashTable;  // 创建新哈希表
        newHashTable._table.resize(newSize); // 扩容
        for (auto& e : _table) // 遍历原哈希表
        {
            if (e._state == EXIST)
            {
                newHashTable.Insert(e._kv); // 映射到新哈希表
            }
        }
        _table.swap(newHashTable._table);
    }

    // 插入操作
    Hash hash;
    size_t size = _table.size();
    size_t hashi = hash(kv.first) % size;   // 得到key值对应的哈希值
    while (_table[hashi]._state == EXIST)   // 线性探测
    {
        int i = 0;
        i++;
        hashi = (hashi + i) % size;
    }

    // 探测到空位置，下标是hashi
    _table[hashi]._kv = kv;                 // 插入元素，更新位置上的kv值
    _table[hashi]._state = EXIST;           // 更新位置的状态
    ++_size;                                // 更新有效元素个数

    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

2.4 闭散列哈希表的删除

删除一个元素只需要将该位置的状态改成DELETE即可。

// 删除函数
bool Erase(const K& key)
{
    HashData<K, V>* find = Find(key);
    if(find != nullptr)
    {
        find->_state = DELETE;
        _size--;
        return true;
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12

3. 实现开散列哈希表

3.1 哈希表结构

开头介绍的链表法，哈希表（数组）的每一个位置存储的都是一个链表的头结点地址。每个哈希桶存储的数据都是一个结点类型，这个结点类就是链表中的结点。

结点类

template<class K, class V>
struct HashNode
{
    pair<K, V> _kv;         // 键值对
    HashNode<K, V>* _next;  // 后继指针
    // 结点构造函数
    HashNode(const pair<K, V> kv)
        :_kv(kv)
        , _next(nullptr)
    {}
};
1
2
3
4
5
6
7
8
9
10
11

由于模板参数和命名的繁杂，为了代码的可读性，可以将结点类typedef为Node：

typedef HashNode<K, V> Node;
1

哈希表

哈希表底层一个动态长度的数组，同样地，使用STL的vector做为哈希表。数组中的每个元素类型都是Node*。

template<class K, class V>
class HashTable
{
    typedef HashNode<K, V> Node;
public:
    // ... 
private:
    vector<Node*> _table;
    size_t _size = 0;
};
1
2
3
4
5
6
7
8
9
10

3.2 开散列哈希表的查找

1. 判断哈希表长度是否为0，是0则查找失败；
2. 根据key值通过哈希函数得到下标值；
3. 找到下标值对应的哈希桶，遍历单链表。

// 查找函数
HashNode<K, V>* Find(const K& key)
{
    if(_table.size() == 0)
    {
        return nullptr;
    }

    size_t pos = key % _table.size(); // 得到下标值
    HashNode<K, V>* cur = _table[pos];  // 找到哈希桶首地址
    while (cur)                         // 遍历链表
    {
        if (cur->_kv.first == key)
        {
            return cur;
        }
        cur = cur->_next;
    }
    return nullptr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.3 开散列哈希表的插入

步骤和闭散列哈希表的插入是类似的，不同的是开散列的负载因子是到1才会扩容。

插入步骤

1. 若哈希表中已存在key值对应的元素，插入失败；
2. 以负载因子为指标判断是否要对哈希表扩容；
3. 插入元素；
4. 有效元素计数器+1。

扩容步骤

1. 若哈希表最初的大小为0，则设置哈希表大小为10；
2. 若哈希表的负载因子等于1，则需要创建一个大小是原大小两倍的新数组。然后遍历原数组，将所有元素插入到新数组；
3. 将新的数组的地址更新到哈希表中。

因为扩容改变了数组的长度，哈希函数也随之变化，每个元素的位置都有可能改变。

更新哈希表的步骤

1. 根据元素的key值通过新的哈希函数得到下标值；
2. 若产生哈希冲突，直接头插到下标位置的单链表即可；

注意

当扩容需要将旧哈希表数据迁移到新哈希表中时，直接在遍历的同时通过新的哈希函数计算出的下标值链接到对应的哈希桶（链表）即可。不复用Insert函数的原因是Insert函数会在其内部new一个Node然后再插入，像这样迁移数据的动作不断new和delete（函数结束会自动delete释放资源）的操作会带来不必要的开销。

哈希桶可以用任意链表实现，单双链表皆可。但是在此为了代码上的简单，使用了单链表，因为此节重点是学习哈希思想，链表应该在之前就已经掌握了。其次，对单链表的操作是头插和头删。原因是不管是什么类型的链表，它的插入和查找的时间复杂度都是$O(N)$，这么做的目的是提高插入（主要）和删除的效率。

// 插入函数
bool Insert(const pair<K, V>& kv)
{
    if(Find(kv.first) != nullptr) // 元素已经存在
    {
        return false;
    }

    // 扩容操作
    if(_size == _table.size())
    {
        size_t oldSize = _table.size();
        size_t newSize = oldSize == 0 ? 10 : 2 * oldSize;
        vector<Node*> newTable;                         // 建立新表
        newTable.resize(newSize);                       // 扩容
        for(size_t i = 0; i < oldSize; i++)             // 转移数据
        {
            Node* cur = _table[i];                      // 下标i对应的链表的首地址
            while(cur)
            {
                Node* next = cur->_next;

                size_t hashi = cur->_kv.first % newSize;// 新下标值
                cur->_next = newTable[hashi];           // 重新链接
                newTable[hashi] = cur;

                cur = next;                             // 链表向后迭代
            }
            _table[i] = nullptr;
        }
        _table.swap(newTable);                          // 替换新哈希表
    }

    // 头插元素
    size_t hashi = kv.first % _table.size();
    Node* newnode = new Node(kv);
    newnode->_next = _table[hashi];
    _table[hashi] = newnode;
    _size++;

    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

3.4 开散列哈希表的删除

1. 根据元素的key值通过哈希函数得到哈希桶的标号；
2. 遍历哈希桶，找到待删除结点；
3. 找到则删除结点并释放结点资源；
4. 更新哈希表中元素个数计数器。

注意

由于哈希桶是由链表实现的，所以即使先用Find找到key值对应的结点，删除时依然要遍历链表，因为单链表的删除需要知道它上一个结点的地址。

// 删除函数
bool Erase(const K& key)
{
    size_t pos = key % _table.size();       // 得到key值对应的哈希桶下标
    Node* prev = nullptr;
    Node* cur = _table[pos];
    while (cur)
    {
        if(cur->_kv.first == key)           // 找到和key值对应的结点
        {
            if (prev == nullptr)            // 找到的结点在链表首部
            {
                _table[pos] = cur->_next;   // 直接将头部往后移动一个单位
            }
            else                            // 找到的结点不在链表首部
            {
                prev->_next = cur->_next;   // 直接跳过它即可
            }

            delete cur;                     // 释放结点资源
            _size--;                        // 更新计数器
            return true;
        }
        prev = cur;                         // 迭代
        cur = cur->_next;
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

4. 补充

4.1 哈希表的大小为何是素数

在本文的开头介绍了一个哈希函数BKDRHash算法，它对每次累加后的结果再乘以素数131。我想原理都是类似的，对于哈希思想，要想发挥它的优势，即查找，就必须扬长避短，避免哈希冲突。

这里有一篇文章和一个讨论详细介绍了哈希表的大小是素数能减少哈希冲突的原因：哈希表的大小为何是素数、Why is it best to use a prime number as a mod in a hashing function?

文中一开始例子中的数列，因子是数列元素之间的间隔。

总地来说，这是由模运算这种运算方式决定的：
$$A\%B$$
其中：

• A：被模数，通常是key值；
• B：模数，通常是哈希表长度。

由于$A\%B$的结果是$A/B$的余数，这个余数就是哈希表的下标，也是判断哈希冲突的依据。当A和B之间存在非1的公共因子时，它们会出现多次结果相同的情况（这就是产生哈希冲突的情况），假设其中一个相同的结果是C。

原因：

A总是能通过B乘以一个非负整数再加上C来表示，例如：A是4的倍数，B是8：

对于A和B，用结果表示A：

这个表格也是计算A%B的原理，出现相同的结果的原因就是A和B之间存在若干非1公共因子。想降低发生哈希冲突的概率，就是减少出现相同哈希值的次数，所以就要减少A和B的公共因子个数，由于每个数都有一个因子是1，所以使哈希表的长度为素数。

在stl_hashtable.h中，专门有一个数组保存了素数，相邻素数之间相差一倍，每当需要扩容时，都从这个数组中找下一个素数作为新哈希表的长度。

static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
  53,         97,         193,       389,       769,
  1543,       3079,       6151,      12289,     24593,
  49157,      98317,      196613,    393241,    786433,
  1572869,    3145739,    6291469,   12582917,  25165843,
  50331653,   100663319,  201326611, 402653189, 805306457, 
  1610612741, 3221225473, 4294967291
};
1
2
3
4
5
6
7
8
9
10

所以上面的扩容操作中可以用这个素数数组优化。

// 获取新哈希表素数长度
size_t GetNextPrime(size_t prime)
{
	const int PRIMECOUNT = 28;
	size_t i = 0;
	for (i = 0; i < PRIMECOUNT; i++)
	{
		if (MyPrimeList[i] > prime)
			return MyPrimeList[i];
	}
	return MyPrimeList[i];
}
1
2
3
4
5
6
7
8
9
10
11
12

4.2 哈希函数

哈希函数除了上面常用的直接定址法和除留余数法以外，还有下面几种常见的哈希函数：

平方取中法

假设关键字为 1234，对它平方就是 1522756，抽取中间的 3 位 227 作为哈希地址。使用场景：不知道关键字的分布，而位数又不是很大的情况。

折叠法

折叠法是将关键字从左到右分割成位数相等的几部分（最后一部分位数可以短些），然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。

使用场景：折叠法适合事先不需要知道关键字的分布，或关键字位数比较多的情况。

随机数法

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即
$$Hash(Key)=random(Key)$$
其中：

• random为随机数函数。

使用场景：通常应用于关键字长度不等时。

数字分析法

设有N个M位数，每一位可能有X种不同的符号，这X中不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，而在某些位上分布不均匀，只有几种符号经常出现。此时，我们可根据哈希表的大小，选择其中各种符号分布均匀的若干位作为哈希地址。

假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是相同的，那么我们可以选择后面的四位作为哈希地址。

如果这样的抽取方式还容易出现冲突，还可以对抽取出来的数字进行反转（如1234改成4321）、右环位移（如1234改成4123）、左环位移（如1234改成2341）、前两数与后两数叠加（如1234改成12+34=46）等操作。

数字分析法通常适合处理关键字位数比较大的情况，或事先知道关键字的分布且关键字的若干位分布较均匀的情况。