如何建立哈希表

哈希表（Hash Table），亦称散列表，是一种根据关键值（Key value）而直接进行访问的数据结构。哈希表常用来存储和查找映射，例如一组键（Key）和值（Value）的集合。在哈希表中，Key 值通过哈希函数映射到数组的索引位置，将访问数据的时间复杂度降低到常数级别，因此哈希表被广泛使用。

如何建立哈希表？从以下几个角度分析：

1.哈希函数

哈希函数的作用是将 Key 值映射到哈希表的索引位置，需要满足以下几个条件：

1）哈希函数的输出值范围应满足哈希表的大小，不然就可能会发生哈希冲突。哈希冲突是指不同的 Key 值映射到了同一个索引位置，需要采用开放地址法或链表法解决。

2）哈希函数应高效，通常使其时间复杂度为 O(1)，可以使用简单的取模运算、平方取中、MD5 等函数实现。

3）哈希函数应尽量避免产生碰撞，通过使用多个哈希函数、调整哈希表大小、调整冲突处理策略等方法减少碰撞的概率。

2.冲突处理

在哈希表中，由于哈希函数的局限性或者 Key 值分布不均匀等原因，不同的 Key 值可能会映射到同一个索引位置上，即哈希冲突。这时需要采用冲突处理方法来解决，通常有以下几种：

1）开放地址法：当产生冲突时，根据某个规则（如线性探测、二次探测、双重哈希等）从冲突位置开始依次查找下一个空位置，直到找到合适的位置为止。

2）链表法：将哈希表中每个位置都对应一个链表，若发生冲突，则将冲突的键值对插入到链表的末尾。这种方法适用于链表较短或者哈希表的负载因子较高的情况。

3）再哈希法：使用另一个哈希函数进行再哈希，直到找到一个无冲突的位置插入。

3.哈希表的大小

哈希表的大小直接影响到哈希冲突的概率和空间利用率。哈希表的大小应该尽可能地满足下列条件：

1）哈希表的加载因子要控制在合适的范围内，一般的建议是哈希表大小的 0.75。

2）考虑哈希表大小，应尽量减少冲突率。

3）哈希表大小需要考虑内存限制以及哈希表的实际需求，如果哈希表大小太小容易导致冲突率上升，哈希表大小过大又会造成内存浪费。

4.哈希表的嵌套

在实际开发中，需要将多个不同属性的数据结合起来进行存储和查找，这种情况下我们可以使用哈希表的嵌套来实现。比如可以将一个哈希表作为 Value 值存在另一个哈希表中，这样就可以方便地进行嵌套的存储和查询。