[数据结构与算法]简述哈希表

????????哈希表，又称为散列表，是一种根据键来直接访问内存位置的一种数据结构。它通过一个计算键值的函数（散列函数）来将所查询的数据映射到哈希表中的一个位置来查找该位置的内容，从而达到快速查找的目的。（存放记录的数组就称为哈希表）。

? ? ? ? 哈希表是由数组加链表或红黑树组成。哈希表的默认数组长度为16，通过比较两个对象的哈希值、地址值以及equals结果可以判断哈希表的新增元素是否重复。

? ? ? ? 哈希表的新增过程如下:

? ? ? ? 1.首先计算新增元素的哈希值

? ? ? ? 2.通过hash值%数组的长度

? ? ? ? 3.根据计算结果找到元素在哈希表的位置，如果该位置为空，则直接新增成功。

? ? ? ? 4.如果该位置有元素，则接着比较地址值与equals结果看元素是否重复，如果不重复，则新增成功。如果重复，则新增失败。

? ? ? ? 哈希表的扩容:

? ? ? ? 1.当哈希表同一个索引值下的元素超过8个，且数组长度小于64时

? ? ? ? 2.哈希表的数组索引值占有率超过0.75（加载因子）时

? ? ? ? 以上两种情况哈希表会进行扩容，新容量是旧容量的二倍。上述的加载因子可以通过构造方法指定修改（loadFactor）。还可以通过构造方法指定数组的初始长度。第一种情况，哈希表扩容时会将超过8个元素位置的元素一对一均分给扩容前数组的对称位置。

? ? ? ? 哈希表的扩容还有一条规则，就是当数组的长度大于64时，同一个索引值下的元素超过8个，当前索引值下的链表会转换成红黑树存储。