一.概念
哈希表是什么？
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。
这是百度百科里面的概念。
首先我们来看个例子来理解一下：
关键码值key：{14, 19, 5, 7, 21, 1, 13, 0, 18}
散列表：大小为13的数组array[13]
散列函数：f(x) = x%13;(取余)
我们对各个关键码值key求哈希值：
f（14） = 1；
f（19） = 6；
f（5） = 5；
f（7） = 7；
f（21） = 8；
f（1） = 1；
f（13） = 0；
f（0） = 0；
f（18） = 5；
因此对应的存储方式为：
图片.png
并且f（13）与f（0）的哈希值相等，出现了哈希冲突。
我们这里的处理方式是hash+1（线性探测法），即将哈希值加一存储，如果哈希值加一已被占用就继续加一直到可以存储。
所以这里当f（13）的值存储到arra[0]之后，f（0）的值存储到array[3]。
通过这个例子，相信你对哈希表已经有一个初步的认识了。。
二.哈希冲突
什么是哈希冲突？
哈希冲突
对不同的关键字可能得到同一散列地址，即k1≠k2，而f(k1)=f(k2)，或f(k1) MOD 容量 =f(k2) MOD 容量，这种现象称为碰撞，亦称冲突。
影响产生冲突多少有以下三个因素：
1.负载因子（load factor）
这里要提到两个参数：初始容量，加载因子，这两个参数是影响hash表性能的重要参数。
容量： 表示hash表中数组的长度，初始容量是创建hash表时的容量。
加载因子： 是hash表在其容量自动增加之前可以达到多满的一种尺度（存储元素的个数），它衡量的是一个散列表的空间的使用程度。
loadFactor= 加载因子 / 容量
一般情况下，当loadFactor <= 1时，hash表查找的期望复杂度为O(1).
对使用链表法的散列表来说，负载因子越大，对空间的利用更充分，然后后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。系统默认负载因子为0.75。
2. 处理冲突的方法
线性探测法： 当发生冲突时，因为f(key) + d，所以首先5 + 1 = 6，得到下一个hash地址为6，又冲突，依次类推，最后得到空闲的hash地址是8，然后将数据填入hash地址为8的空闲区域。
二次探测法： 当发生冲突时，因为d = 1^2，所以5 + 1 = 6，得到的下一个hash地址为6，又冲突，因为d = -1^2,所以5 + (-1) = 4，得到下一个hash地址为4，是空闲则将数据填入该区域。
伪随机数探测法： 随机数法就是完全根据伪随机序列来决定的，如果根据一个随机数种子得到一个伪随机序列{1，-2，2，。。。，k}，那么首先得到的地址为6，第二个是3，依次类推，空闲则将数据填入。
链地址法（拉链法，位桶法）
将产生冲突的关键字的数据存储在冲突hash地址的一个线性链表中。实现时，一种策略是散列表同一位置的所有冲突结果都是用栈存放的，新元素被插入到表的前端还是后端完全取决于怎样方便。
图片.png
扩容
当hash表中元素越来越多的时候，碰撞的几率也就越来越高（因为数组的长度是固定的），所以为了提高查询的效率，就要对数组进行扩容。而在数组扩容之后，最消耗性能的点就出现了，原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是扩容。
什么时候进行扩容呢？当表中元素个数超过了容量 * loadFactor时，就会进行数组扩容。
参考文章
网友评论