JDK HashMap详解

HashMap的继承关系如图:

HashMap的继承关系图

初始空间大小 1<<4（16）
最大空间大小1 << 30 (1073741824)
哈希桶元素超过1，链接方式默认为链表形式，数量超过TREEIFY_THRESHOLD的阈值(默认8)将被转换成红黑树
哈希桶的元素如果降低到UNTREEIFY_THRESHOLD的阈值(默认6)会被重新转换成链表形式
最小的哈希表容量为64(4倍TREEIFY_THRESHOLD值)
哈希表节点的类型为Node<K,V>(实现Map.Entry<K,V> 接口)

结构为：
hash:哈希值
key:key
value:值
next:持有下一个节点的索引

put过程(以下是伪代码，贴有部分jdk8的代码实现)：

1. 计算key的哈希值
   采用哈希算法

    int h;
    (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)
   

   这里也是哈希能兼容key为null的原因

   哈希算法为什么这样写?
   右位移16位，正好是32bit的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。

2. 将hash，key，value移交给putVal方法处理

3. 处理节点数据

   1. 哈希表是空的：
      初始化哈希表，在初始化哈希表的过程中会进行扩容操作(resize()方法)会创建一个数组

      注意:实质上初始化数组和数组容量达到当前数组上限都会调用resize()方法并返回一个新的数组，达到容量上限的时候，会将原有数组的值copy(遍历到新的数组中)并返回新数组的引用,在扩容的时候会将原有哈希表中的元素分散到新的哈希表中，因为无论如何计算哈西元素的时候当前元素要么在当前位置(j)要么在(j+oldCap)位置，形成新的哈希桶，这样可以快速确定元素位置，而不用去重新确定元素对于所有桶的位置，这点很重要

   2. 根据当前key的哈希和当前的数组长度计算数值将被赋予的哈希桶位置，并赋值给如果当前哈希桶首元素为null，则创建一个新的node并赋予当前哈希表位置

   3. 如果不是null，则分为三种情况

      • map中已经有当前元素的key了.
        判定条件为：
        p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k)))
      • 当前节点是一个TreeNode节点(超过了树化阈值)
      • 没有当前元素并且不达到树化条件,则添加元素到链表中并将引用存入node节点的next中,如果添加元素之后达到树化条件，则将链表实现更新为红黑树的实现

      以下摘自网络
      但是超过这个阈值后HashMap开始将列表升级成一个红黑树，使用哈希值作为树的分支变量，如果两个哈希值不等，但指向同一个桶的话，较大的那个会插入到右子树里。如果哈希值相等，HashMap希望key值最好是实现了Comparable接口的，这样它可以按照顺序来进行插入。这对HashMap的key来说并不是必须的，不过如果实现了当然最好。如果没有实现这个接口，在出现严重的哈希碰撞的时候，你就并别指望能获得性能提升了。

   4. 如果map中存在次元素则替换元素的值并提供拓展点afterNodeAccess(Node<K,V> p)来处理这类数据

   5. 判定当前容量已经达到最大设置容量，如果达到给数组扩容

   6. 提供拓展点给子类提供添加之后的一些处理afterNodeInsertion(boolean evict)

get过程(以下是伪代码，贴有部分jdk8的代码实现)：

1. 链表查找：计算key的哈希值，并获取当前哈希桶，判定当前哈希桶中的首元素是不是需要的数据（进行equals）比较，如果不是，则依次遍历节点后驱直至找到key对应的node

2. 遍历红黑树：判定首节点的类型是否是TreeNode，如果是从红黑树中获取元素并返回

3. 如果没有查找到元素则返回null

    需要注意的是:
    containsKey()和containsValue()方法，其实质还是遍历一遍哈希桶，所以，如果只是判定在map中含有这个数据，用这个方法当然更好，但是如果需要这个数据做下一步运算就用get判空效率更高，因为containsKey()之后再次get相当于调用了两次遍历，效率相对下降许多
   

keySet()和values()方法:

keySet()和values()是因为hashMap继承自AbstractMap，它提供了超类实现将node中的key和value拆分到两个set中(keySet和values())，在第一次调用的时候(new KeySet的时候和values()的时候会创建一个对象，这个对象引用了key序列和value序列，这里并不需要去维护这个数组，只需要实现了set的迭代器name这个对象就会被索引到set里面(很神奇，我也惊讶了好久 但是实验过后的确是这样的))，之后就能取得set里面的数据，但是这个set的数值发生改变，map本身的数据也会发生改变，里面存放的只是对象的key/value引用。

ps:没有人比我写的更详细了吧，就问还有谁还有谁！！！