哈希表也称为散列表，是根据关键字值（key value）而直接进行访问的数据结构。也就是说，它通过把关键字值映射到一个位置来访问记录，以加快查找的速度。这个映射函数称为哈希函数（也称为散列函数），映射过程称为哈希化，存放记录的数组叫做散列表。
哈希表既具备快速查询，又能快速插入删除元素。
哈希表的最主要有点是利用它能在o(1)时间内找到某一元素，效率最高的查找方式，空间换时间。
负载因子
哈希表还有一个重要的属性: 负载因子(load factor)，它用来衡量哈希表的 空/满 程度，一定程度上也可以体现查询的效率，计算公式为:
负载因子 = 总键值对数 / 箱子个数
负载因子越大，意味着哈希表越满，越容易导致冲突，性能也就越低。因此，一般来说，当负载因子大于某个常数(可能是 1，或者 0.75 等)时，哈希表将自动扩容。
重哈希
哈希表在自动扩容时，一般会创建两倍于原来个数的箱子，因此即使 key 的哈希值不变，对箱子个数取余的结果也会发生改变，因此所有键值对的存放位置都有可能发生改变，这个过程也称为重哈希(rehash)。
- 如果哈希表中本来箱子就比较多，扩容时需要重新哈希并移动数据，性能影响较大。
- 如果哈希函数设计不合理，哈希表在极端情况下会变成线性表，性能极低。
解决哈希冲突
那么问题来了，这种方式对不同的关键字，可能得到同一个散列地址，即同一个数组下标，这种现象称为冲突，那么我们该如何去处理冲突呢？
1.开放定址法（线性探测再散列，二次探测再散列，伪随机探测再散列）
1.1 线性探测法
所谓线性探测，即线性地查找空白单元。我举个例子，如果21是要插入数据的位置，但是它已经被占用了，那么就是用22，然后23，以此类推。数组下标一直递增，直到找到空白位。下面是基于线性探测法的哈希表实现代码：
找。
2.链地址法(Java hashmap就是这么做的)
在哈希表每个单元中设置链表（即链地址法），某个数据项的关键字值还是像通常一样映射到哈希表的单元，而数据项本身插入到这个单元的链表中。其他同样映射到这个位置的数据项只需要加到链表中，不需要在原始的数组中寻找空位。
3.再哈希法
4.建立一个公共溢出区
链地址法特点
(1)拉链法处理冲突简单。且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
(2)因为拉链法中各链表上的结点空间是动态申请的。故它更适合于造表前无法确定表长的情况。
(3)开放定址法为降低冲突。要求装填因子α较小。故当结点规模较大时会浪费非常多空间。而拉链法中可取α≥1，且结点较大时，拉链法中添加的指针域可忽略不计，因此节省空间；
(4)在用拉链法构造的散列表中，删除结点的操作易于实现。仅仅要简单地删去链表上对应的结点就可以。而对开放地址法构造的散列表，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是由于各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。
网友评论