Java哈希表以及哈希冲突

Java哈希表

概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(log N)，搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
当向该结构中：
插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(HashTable)(或者称散列表)

冲突

不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

避免冲突

*由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的，这就导致一
个问题，冲突的发生是必然的，但我们能做的应该是尽量的降低冲突率。*而不能完全避免哈希冲突。

哈希函数的设计方法

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。 哈希函数设计原则：

哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
哈希函数计算出来的地址能均匀分布在整个空间中
哈希函数应该比较简单

常见哈希函数

1. 直接定制法–(常用)
   取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B 优点：简单、均匀 缺点：需要事先知道关键字的分布情况 使用场景：适合查找比较小且连续的情况


2. 除留余数法–(常用)
   例如：数据集合{1，7，6，4，5，9}；
   哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。
   设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址
   
   用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快


3. 平方取中法–(了解)
   假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况


4. 折叠法–(了解)
   折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
   折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况


5. 随机数法–(了解)
   选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。通常应用于关键字长度不等时采用此法

负载因子调节

负载因子 = 0.75；

所以当冲突率达到一个无法忍受的程度时，我们需要通过降低负载因子来变相的降低冲突率。
已知哈希表中已有的关键字个数是不可变的，那我们能调整的就只有哈希表中的数组的大小。（2倍扩容）

为什么负载因是0.75

HashMap的扩容时取决于threshold, 而threshold取决于loadFactor, loadFactor(负载因子)HashMap的默认值是0.75(3/4), 那么为什么当HashMap的容量超过3/4时就需要扩容了呢? 为什么不是1/2扩容 或者 等于table.length时扩容呢?

根据统计学的结果, hash冲突是符合泊松分布的, 而冲突概率最小的是在7-8之间, 都小于百万分之一了; 所以HashMap.loadFactor选取只要在7-8之间的任意值即可,
但是为什么就选了3/4这个值？
HashMap.loadFactor的选值是3/4就能理解了, table.length * 3/4可以被优化为(table.length >> 2) <<2) &＃8211; (table.length >> 2) == table.length &＃8211; (table.lenght >> 2),
JAVA的位运算比乘除的效率更高, 所以取3/4在保证hash冲突小的情况下兼顾了效率;

解决哈希冲突两种常见的方法是：闭散列和开散列

解决哈希冲突两种常见的方法是：闭散列和开散列

哈希表和 java 类集的关系

1. HashMap 和 HashSet 即 java 中利用哈希表实现的 Map 和 Set


2. java 中使用的是哈希桶方式解决冲突的


3. java 会在冲突链表长度大于一定阈值后，将链表转变为搜索树（红黑树）


4. java 中计算哈希值实际上是调用的类的 hashCode 方法，进行 key 的相等性比较是调用 key 的 equals 方
   法。所以如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值，必须覆写 hashCode 和 equals 方
   法，而且要做到 equals 相等的对象，hashCode 一定是一致的。