哈希表的理论知识

1. 哈希表的基本概念

哈希表又称散列表，若要存储的元素个数为n，设置一个长度为m（m >= n）的连续内存单元，以每个元素的关键字为自变量，通过一个称为哈希的函数把关键字映射为内存单元地址（或下标），并将该元素存储在这个内存单元中，而这个内存单元的值也称为哈希地址，这样构造出来的线性存储结构称为哈希表

• 两个不同的关键字哈希之后可能得到相同的值，这样叫做哈希碰撞

2. 与哈希表查找性能相关的三个元素

• 填装因子，即已经放入哈希表的元素n和哈希表总大小m之比（n/m），通常填装因子控制在0.6~0.9
• 采用的哈希函数，若选用的哈希函数合适，即会使元素均匀分布，减少碰撞
• 解决哈希冲突的方法，该方法决定元素如何放置，相关查询顺序

3. 哈希函数的构造方法

哈希函数的目标是让所有元素的哈希地址尽可能均匀分布，且计算过程尽可能简单提高时间效率，下面讨论整形的哈希值

• 直接定址法

以关键字本身或加某个常量c作为哈希地址的方法，h(k) = k + c，该方法适用分布基本连续时，不然内存会极大浪费

• 除留余数法

用关键字取模不大于哈希表的长度，h(k) % p （p为不大于哈希表长度的整形），使用范围最广，比如之前介绍的HashTree底层的哈希表就是采用这种方法，该方法使映射地址的概率相同

• 还有很多方法省略这里不做说明

4. 哈希碰撞的解决方法

4.1 开放定址法

出现哈希碰撞时在表中找一个空闲的位置存放元素

• 线性探测法

从发生碰撞的地方依次往下探测空闲地址，若到了哈希表尾，则从头开始探测

• 平方探测法

即在碰撞位置向前向后加上自然数的平方来找位置

4.2 拉链法

把碰撞的元素用链表拼接起来，相比开放定址法拉链法处理简单，无堆积现象，且链表可以动态改变结构，目前推荐使用拉链法