HashMap底层原理解析

HashMap底层原理解析

1.基本、常用性质
HashMap储存的是键值对
HashMap 允许 null 键和 null 值，在计算哈希值时，null 键哈希值为 0，而HashTable则不能
HashMap 是非线程安全类，在多线程环境下可能会存在问题，HashTable、ConcurrentHashMap线程安全

2.前提
数据结构中有数组和链表来实现对数据的存储，但这两者各有利弊。
数组:
数组存储区间是连续的，占用内存严重，故空间复杂度大。但数组的二分查找时间复杂度小，为O(logn)；
二分法的关键思想是 假设该数组的长度是N那么二分后是N/2，再二分后是N/4……直到二分到1结束（最坏情况）
于是我们可以设次数为x，N*（1/2）^x=1；则x=logn,底数是2，
数组特点：寻址容易，插入和删除困难；扩展性差

       线性查找  O(N)
       二分查找  O(logN)
       无序数组的插入 O(1)
       有序数组的插入O(N)
       无序数组的删除O(N)
       有序数组的删除O(N)

链表:
链表存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，达O(N)。
链表特点：寻址困难，插入和删除容易。动态扩展存储个数大小
链表（是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。
　　 链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，
同时链表由于增加了结点的指针域，空间开销比较大。
哈希表:
那么我们综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构，这就是哈希表。
哈希表（(Hash table）既满足了数据的查找方便，同时不占用太多的内存空间，使用也十分方便。
哈希表有多种不同的实现方法，HashMap则使用的是拉链法，也叫作【链地址法】；

3.原理
HashMap 底层是基于散列算法实现，散列算法分为散列再探测和拉链式（链地址法）。
一个长度为16的数组中，每个元素存储的是一个链表的头结点
JDK 1.7之前，数组+链表；
JDK 1.8之后，数组+链表+红黑树（查找时间复杂度为 O(logn)）（链表长度大于8时转化为红黑树）

具体画图展示：
容量（capacity）：Entry[] table 的默认长度为16
负载因子（load factor）：其默认值为 0.75
size ：记录的是map中包含的Entry的数量
桶(bucket) : Entry[] table中的某一个元素及其对应的Entry<Key,Value>又被称为桶; capacity 其实就是桶的长度
阈值：threshold = loadFactor * capacity，需要resize的阈值；threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);

注：这是时间和空间成本上一种折衷：增大负载因子可以减少 Hash 表（就是那个 Entry 数组）所占用的内存空间，但会增加查询数据的时间开销，
而查询是最频繁的的操作（HashMap 的 get() 与 put() 方法都要用到查询）；减小负载因子会提高数据查询的性能，但会增加 Hash 表所占用的内存空间。

举例说明：1-100如何存进去；如何取；
在进行增删查等操作时，首先要定位到元素的所在桶的位置，之后再从链表中定位该元素。
比如我们要查询上图结构中是否包含元素35，步骤如下：
定位元素35所处桶的位置，index = 35 % 16 = 3 ，在3号桶所指向的链表中继续查找，发现35在链表中。

4. hash冲突
   冲突：哈希表基于数组，类似于key-value的存储形式，关键字值通过哈希函数映射为数组的下标，如果一个关键字哈希化到已占用的数组单元，这种情况称为冲突。
   解决冲突方法：
   a.开放定址法（线性探测再散列，二次探测再散列，伪随机探测再散列）：把冲突的数据项放在数组的其它位置；
   b.再哈希法
   c.链地址法 （Java中HashMap使用的算法）：每个单元都包含一个链表，把所有映射到同一数组下标的数据项都插入到这个链表中。
   d.建立一个公共溢出区

举例：
12%16=12,28%16=12,108%16=12,140%16=12
所以12、28、108以及140都存储在数组下标为12的位置

第一个键值对A进来，通过计算其key的hash得到的index=0，记做:Entry[0] = A。
一会后又进来一个键值对B，通过计算其index也等于0，HashMap会这样做: B.next = A,Entry[0] = B；
如果又进来C，index也等于0，那么C.next = B，Entry[0] = C；
这样我们发现index=0的地方其实是利用单链表的头插法存取了A、B、C三个键值对，他们通过next这个属性链接在一起。
所以会发生覆盖的情况，数组中存储的总是最后插入的元素。

5.扩容：为什么扩容？什么时候扩容？扩容多少？怎么扩容？
（1）为什么
由于哈希是一种压缩映射，每一个Entry节点无法对应到一个只属于自己的桶，必然会存在多个Entry共用一个桶，拉成一条链表的情况，这种情况叫做哈希冲突。
当哈希冲突产生严重的情况，某一个桶后面挂着的链表就会特别长，顺序查找效率低。

哈希冲突无法完全避免，因此为了提高HashMap的性能，HashMap不得尽量缓解哈希冲突以缩短每个桶的外挂链表长度。

频繁产生哈希冲突最重要的原因就像是要存储的Entry太多，而桶不够。
因此，当HashMap中的存储的Entry较多的时候，要考虑增加桶的数量，这样对于后续要存储的Entry来讲，就会大大缓解哈希冲突。

（2）什么时候扩容: put()
当size大于等于某一个阈值thresholdde时候且该桶并不是一个空桶
当map中包含的Entry的数量大于等于threshold = loadFactor * capacity的时候，且新建的Entry刚好落在一个非空的桶上，此刻触发扩容机制，将其容量扩大为2倍。
理解 ：因为size 已经大于等于阈值了，说明Entry数量较多，哈希冲突严重，那么若该Entry对应的桶不是一个空桶，
这个Entry的加入必然会把原来的链表拉得更长，因此需要扩容；若对应的桶是一个空桶，那么此时没有必要扩容。
源码中：put(K, V)操作

（3）扩容多少
resize()容量需要是2倍这样扩张。HashMap的容量必须是2的幂，这么设计是为了性能。
在HashMap通过键的哈希值进行定位桶位置的时候，调用了一个indexFor(hash, table.length)方法
static int indexFor(int h, int length) {
return h & (length-1);
}
这里将哈希值h与桶数组的length-1（实际上也是map的容量-1）进行了一个与操作得出了对应的桶的位置，h & (length-1)。

不采用h % length，因为Java的%、/操作比&慢10倍左右，因此采用&运算会提高性能。

通过限制length是一个2的幂数，使得h & (length-1)和h % length结果是一致的。

举例：
hashcode是311，对应的二进制是(1 0011 0111)

length为16，对应的二进制位(1 0000)

%操作：311 = 16*19 + 7；所以结果为7，二进制位(0111)；

&操作：(1 0011 0111) & (0111) = 0111 = 7, 二进制位(0111)

（4）怎么扩容？
resize() : 重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作
rehash() : 经过rehash之后，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置
transfer() : 使用一个容量更大的数组来代替已有的容量小的数组，transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里。
对于resize的过程，相对来讲是比较简单清晰易于理解的。
旧桶数组中的某个桶的外挂单链表是通过头插法插入新桶数组中的，并且原链表中的Entry结点并不一定仍然在新桶数组的同一链表。

（5）结合图8.9分析1.8以后的优势
（6）举例说明扩容的给的大小
比如说，我们有1000个元素new HashMap(1000), 但是理论上来讲new HashMap(1024)更合适，但即使是1000，hashmap也自动会将其设置为1024。
但是new HashMap(1024)还不是更合适的，因为0.75*1000 < 1000, 也就是说为了让0.75 * size > 1000, 我们必须这样new HashMap(2048)才最合适，
既考虑了&的问题，也避免了resize的问题。

6. 再散列rehash过程
   将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中。
   这个过程叫作rehashing，因为它调用hash方法找到新的bucket位置

当哈希表的容量超过默认容量时，必须调整table的大小。当容量已经达到最大可能值时，那么该方法就将容量调整到Integer.MAX_VALUE返回，
这时，需要创建一张新表，将原表的映射到新表中。
元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化
因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，
是0的话索引没变，是1的话索引变成“原索引+oldCap”，可以看看下图为16扩充为32的resize示意图

7. 负载因子：
   当我们调低负载因子时，HashMap 所能容纳的键值对数量变少。扩容时，重新将键值对存储新的桶数组里，键的键之间产生的碰撞会下降，链表长度变短。
   此时，HashMap 的增删改查等操作的效率将会变高，这里是典型的拿空间换时间。
   相反，如果增加负载因子（负载因子可以大于1），HashMap 所能容纳的键值对数量变多，空间利用率高，但碰撞率也高。这意味着链表长度变长，
   效率也随之降低，这种情况是拿时间换空间。

8. 看源码
   get(): first = tab[(n - 1) & hash]
   这里通过(n - 1)& hash即可算出桶的在桶数组中的位置，(n - 1) & hash 等价于对 length 取余。举个例子说明一下吧，假设 hash = 185，n = 16。

计算键的 hash 值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

导致了计算结果只与低位信息有关，高位数据没发挥作用。为了处理这个缺陷，我们可以上图中的 hash 高4位数据与低4位数据进行异或运算，即 hash ^ (hash >>> 4)。通过这种方式，让高位数据与低位数据进行异或，以此加大低位信息的随机性，变相的让高位数据参与到计算中。此时的计算过程如下：
重新计算 hash 的另一个好处是可以增加 hash 的复杂度。当我们覆写 hashCode 方法时，可能会写出分布性不佳的 hashCode 方法，进而导致 hash 的冲突率比较高。
通过移位和异或运算，可以让 hash 变得更复杂，进而影响 hash 的分布性。

HashMap的遍历：
HashMap<Integer, String> map = new HashMap(16);
map.put(7, "");
map.put(11, "");
map.put(43, "");
map.put(59, "");
map.put(19, "");
map.put(3, "");
map.put(35, "");

    for (Integer key : map.keySet()) {
        int h;
        int s=(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        Log.i("hahhaha", "setupView: "+key+"->"+key.hashCode()+"->"+s);
    }

插入操作：
插入操作的入口方法是 put(K,V)，但核心逻辑在V putVal(int, K, V, boolean, boolean) 方法中。putVal 方法主要做了这么几件事情：

1.当桶数组 table 为空时，通过扩容的方式初始化 table
2.查找要插入的键值对是否已经存在，存在的话根据条件判断是否用新值替换旧值
3.如果不存在，则将键值对链入链表中，并根据链表长度决定是否将链表转为红黑树
4.判断键值对数量是否大于阈值，大于的话则进行扩容操作
以上就是 HashMap 插入的逻辑，并不是很复杂，这里就不多说了。接下来来分析一下扩容机制。