哈希表、哈希冲突

大家好，又见面了，我是你们的朋友全栈君。

哈希表
1.哈希表是一种以键值key存储数据value的结构，以key作为标识值存储value值；只要输入待查找的key，即可获取其对应的value值。当按照键值查询元素时，使用相同的hash函数将key转换为数组下标，从数组中按照下标对应的位置获取数据。它实际上是数组的一种扩展，数组+链表+红黑树。
2.哈希表的设计
哈希函数的设计首先不能过于复杂，复杂的哈希函数会间接的影响hash表的性能；其次要求哈希值应该尽可能随机且均匀分布，避免或者减少哈希冲突的数量，使每个桶中存储的数据比较平均。

常规的设计方法有数据分析法，选择数据的业务特征提取部分数据进行计算，然后得到结果再与哈希表数组的长度求余后最为哈希值。另外还有直接寻址法、平方取中法、折叠法和随机数法等。

负载因子（加载因子）：减少链表长度
低效扩容：乘以2进行扩容
加载因子越大，哈希表中存储的元素越多，空闲的位置就越少，哈希冲突的概率就越大，插入、删除和查找数据时的性能就随之降低。
应该避免低效扩容，因为极个别情况插入速度非常慢，会导致用户崩溃。
哈希函数
1.哈希函数计算达到的哈希值应该是一个非负整数
2.如果key1==key2，那么hash(key1)==hash(key2)
3.即使两个key的hash值相等，但是有可能key值不相等
4.应用场景：安全加密、唯一标识、数据校验、负载均衡、数据分片和分布式存储等
哈希冲突
由于映射的范围限制，key取值的可能性大于映射范围，出现两个不同的key映射到同一个位置

解决哈希冲突的常见方法有开放地址法和链表法。
开放地址法：一旦出现hash值冲突则通过重新探测新位置的方法来解决冲突。对于线性探测法当哈希表中存储的元素越多时，哈希冲突的概率越高，极端情况下需要探测整个哈希表，时间复杂度为O(n)。
链表法：链地址法，在具体的应用中使用较多，在哈希表中每个桶对应一个链表，把哈希值相同的元素存放在相同桶位置的对应链表中，由于需要对比key值所以插入时间复杂度为O(k)，查找和删除时的时间复杂度与链表的长度成正比O(k)，一般当k值不是很大时可以粗略的认为O(1)。需要尽量减少链表长度，可以引入一个参数：负载因子或者称为加载因子。负载因子用于间接的限定链表的长度，如果值越大则允许的链表长度越大，哈希表的性能越差，但是加载因子越小空间浪费越严重。

HashMap采用的是链表法解决hash冲突，ThreadLocalMap通过基于线性检测的开放寻址法解决冲突。

开放寻址法数据存储在数组中，可以有效地利用CPU缓存加快查询速度，不会涉及链表和指针的问题。当加载因子较大时会导致大量的探测行为操作，性能会急剧下降，同时删除数据也很麻烦，而且比链表法需要占用更多的存储空间。数据量比较小、负载因子小的时候适合开放地址法。
链表法数据存储在链表中，对内存的利用率比开发地址法高一些，可以容忍比较大的装载因子，由于节点中需要存储next指针，会消耗额外的内存空间【有效载荷问题】。实际上如果考虑链表长度变长的问题，可以考虑引入红黑树，以避免恶意的将数据存储在一个桶中的哈希碰撞攻击问题。