自我总结

什么是 HashMap?

首先看下类继承关系：

HashMap 是存储键值对的集合，一个 key–value , 这样的键值对也称为 Entry ，这些键值对分散存储于数组当中，组成 HashMap 的主干。

特点

其中 key 可为 null ；非线程安全；

其中 put 方法和 get 方法比较重要。

put 方法

public V put(K key, V value) {
       return putVal(hash(key), key, value, false, true);
}
  
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                  boolean evict) {
       Node<K,V>[] tab; Node<K,V> p; int n, i;
       if ((tab = table) == null || (n = tab.length) == 0)
           n = (tab = resize()).length;
       if ((p = tab[i = (n - 1) & hash]) == null)
           tab[i] = newNode(hash, key, value, null);
           .....
  }

首先根据 key 计算 hash 值 , 如何算出在 Node 数组中具体的下标呢？从上面代码我们可以大概看出：

1	i = (n-1) & hash

就是数组的长度 -1 & key 的hash 值。

得到数组下标后，再把这个键值对放入进去，完成了 put 操作。

假设我们： put(“qq”,”糖葫芦”) hash("qq") = 2, 下标为2，那么结果如下：

Entry1====> [key = "qq", value= "糖葫芦"]

但是总会有那么一种情况，就是不同 key 计算的 hash 之后是相同的，假如我们新 put("mi",value="milo") index = hash("mi") = 2 也是数组下标为2，那么此时在下标为2的位置就会通过链表的形式存储相应的键值对。

HashMap 数组的每一个元素不止是一个Entry 对象，也是一个链表的头节点。每一个Entry对象通过 Next 指针指向它的下个 Entry 节点。当再有新的 Entry 映射到这个冲突位置时，也就是计算出 hash 值也是2，只需要插入到对应的链表当中去即可，注意：新插入的会在之前的前面，称为 头插入，被新 put 进入的新元素可能被用到的概率大一些。

get 方法

了解了 put 方法，get 好理解些
1
2
3
4
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
第一步：同样根据 key 算出 hash 值；

第二步：根据 hash值和数组的长度计算数组的下标 index

第三步：假设我们取出我们 get("qq") 对应的值，我们知道下标是2，且是一个链表，我们需要循环遍历整个链表，找到 key = "qq" 的Entry。
HashMap的默认长度是多少？为什么要那么定义？

HashMap 默认长度是16，也可以自定义长度必须是2幂次方。之所以选择16，是为了方便于 key 映射 index 的算法。

为了实现一个均匀的 HashMap ,数组的长度必须是 2 的幂次方，将 index = hash(key) & (length-1) 这样做的效率也更高，通过位运算的方式。

举例：book 的 hashcode,结果为十进制的 3029737，二进制：1011100011101011101001；假定 HashMap 长度是默认的16， length-1 = 15,二进制： 1111；

index = hash(key) & (length-1)

计算结果如下图：

二进制：1001；十进制：就是index= 9。

那么假设我们自定义长度设置为：10. 那length-1=9, 二进制就是：1001，我们重新计算下index`, 如下图：

二进制为：1001 ；十进制就是： index = 9

然后我们再尝试一个新的 HashCode:

结果还是：1001；

然后我们继续来一个新的 HashCode:

结果还是：1001，index= 9.

也就是说，当 HashMap 长度为 10 的时候，多个不同的key生成的 index 可能是相同的，相同的概率比较大，这样，显然不符合 Hash 算法均匀分布的原则。

反观长度为16或者2的幂次方，length-1 的值是所有二进制全为1，这种情况下，index 的结果等同于HashCode 的后几位值，只有输入的 HashCode 本身分布均匀，Hash 算法的结果也是均匀的。