HashMap的强大功能，相信大家都了解一二。之前看过HashMap的源代码，都是基于JDK1.6的，并且知其然不知其所以然，现在趁着寒假有时间，温故而知新。文章大概有以下几个方面：
我要评论 1 static class Node<K,V> implements Map.Entry<K,V> {
2 final int hash;
3 final K key;
4 V value;
5 Node<K,V> next;
6
7 Node(int hash, K key, V value, Node<K,V> next) {
8 this.hash = hash;
9 this.key = key;
10 this.value = value;
11 this.next = next;
12 }
13
14 public final K getKey() { return key; }
15 public final V getValue() { return value; }
16 public final String toString() { return key + "=" + value; }
17
18 //hashCode等其他代码
19 }
首先，HashMap 是 Map 的一个实现类，它代表的是一种键值对的数据存储形式。Key 不允许重复出现，Value 随意。jdk 8 之前，其内部是由数组+链表来实现的，而 jdk 8 对于链表长度超过 8 的链表将转储为红黑树。
底层数据结构就是 数组 + 链表 + 红黑树（长度>8），其中有一个静态内部类
1 static class Node<K,V> implements Map.Entry<K,V>
这个静态内部类就是一个小的方块，在jdk1.8之前只在构造方法里面初始化的，现在是在第一次put的时候初始化的。
put 方法的源码分析是本篇的一个重点，因为通过该方法我们可以窥探到 HashMap 在内部是如何进行数据存储的，所谓的数组+链表+红黑树的存储结构是如何形成的，又是在何种情况下将链表转换成红黑树来优化性能的。带着一系列的疑问，我们看这个 put 方法：
1 public V put(K key, V value) {
2 return putVal(hash(key), key, value, false, true);
3 }
也就是put方法调用了putVal方法，其中传入一个参数位hash(key)，我们首先来看看hash这个方法。
1 static final int hash(Object key) {
2 int h;
3 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
4 }
是一个静态final方法。这是为什么key可以位null的原因了，当插入的key值为null，他会自动把他当作0进行处理
并且调用了key的hashcode，这就是为什么map的key一定要重写hashcode和equals方法。
并且与h右移16位异或。我们来详细看看这里为什么这样做。
我们知道，按位异或就是把两个数按二进制，相同就取0，不同就取1。
比如：0101 ^ 1110 的结果为 1011。异或的速度是非常快的。
把一个数右移16位即丢弃低16为，就是任何小于2^16的数，右移16后结果都为0（2的16次方再右移刚好就是1）。
任何一个数，与0按位异或的结果都是这个数本身（很好验证）。
所以这个hash()函数对于非null的hash值，仅在其大于等于2^16的时候才会重新调整其值，小于2^16不做调整直接取他的hashcode值。
至于为什么右移16位异或，这是知乎上面的一幅图片
看到没有，变得“松散”了很多，至于为什么，我也不是很清楚。我们继续往下看putVal这个方法。
1 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
2 Node<K,V>[] tab; Node<K,V> p; int n, i;
3 //如果 table 还未被初始化，那么初始化它
4 if ((tab = table) == null || (n = tab.length) == 0)
5 n = (tab = resize()).length;
6 //根据键的 hash 值找到该键对应到数组中存储的索引
7 //如果为 null，那么说明此索引位置并没有被占用
8 if ((p = tab[i = (n - 1) & hash]) == null)
9 tab[i] = newNode(hash, key, value, null);
10 //不为 null，说明此处已经被占用，只需要将构建一个节点插入到这个链表的尾部即可
11 else {
12 Node<K,V> e; K k;
13 //当前结点和将要插入的结点的 hash 和 key 相同，说明这是一次修改操作
14 if (p.hash == hash &&
15 ((k = p.key) == key || (key != null && key.equals(k))))
16 e = p;
17 //如果 p 这个头结点是红黑树结点的话，以红黑树的插入形式进行插入
18 else if (p instanceof TreeNode)
19 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
20 //遍历此条链表，将构建一个节点插入到该链表的尾部
21 else {
22 for (int binCount = 0; ; ++binCount) {
23 if ((e = p.next) == null) {
24 p.next = newNode(hash, key, value, null);
25 //如果插入后链表长度大于等于 8 ，将链表裂变成红黑树
26 if (binCount >= TREEIFY_THRESHOLD - 1)
27 treeifyBin(tab, hash);
28 break;
29 }
30 //遍历的过程中，如果发现与某个结点的 hash和key，这依然是一次修改操作
31 if (e.hash == hash &&
32 ((k = e.key) == key || (key != null && key.equals(k))))
33 break;
34 p = e;
35 }
36 }
37 //e 不是 null，说明当前的 put 操作是一次修改操作并且e指向的就是需要被修改的结点
38 if (e != null) {
39 V oldValue = e.value;
40 if (!onlyIfAbsent || oldValue == null)
41 e.value = value;
42 afterNodeAccess(e);
43 return oldValue;
44 }
45 }
46 ++modCount;
47 //如果添加后，数组容量达到阈值，进行扩容
48 if (++size > threshold)
49 resize();
50 afterNodeInsertion(evict);
51 return null;
52 }
注释已经很清楚了，我想说下这个初始化的问题
//如果 table 还未被初始化，那么初始化它 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length;
这个resize()方法既可以初始化，也可以扩容，都是这个函数完成的。并且在多线程下，不会出现之前的死锁导致cpu飙升至100%，只会出现数据丢失的问题。
//这部分我后续在补，有点多。
如对本文有疑问， 点击进行留言回复！！
【奥鹏作业答案库网】大工20春《应用统计》在线作业1【奥鹏作业答案】
网友评论