HashMap中使用的数组加链表（java8以后链表数据超过8以后，就改成红黑树存储）来存储键值，那HashMap为何使用数组，数组如何起作用，以及为什么加链表，java8又为何将链表改成红黑树了呢？带着这样的疑问来看看下面的分析：
先说说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);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
//代码太多占篇幅，省略掉resize() ;
不想找源码的同学可以到HashMap源码
源码解析
- 从源码中可以看到调用put操作时，实际上是调用的putVal，它会将key进行hash计算一次，计算出来的值呢就是这个key在Node数组中的索引，所以在进行get操作的时候会通过这个索引来找到相应的键值，时间复杂度为O(1)，下面来详细看看putVal的操作。
- 这段意思是如果这个数组为空那么就把这个数组给resize()一下。简单概括一下resize()，如果Node数组为空那么就把它初始化为一个负载因子为0.75(默认)，长度为16(默认)的数组，否则就将当前数组增长为以前数组的两倍。这里说明一下，虽然数组长度为16但是它的门限值只有 16*0.75 = 12(容量 * 负载因子= 门限值)，只要数组中元素超过门限值就会进行resize()，扩容两倍。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
- 通过对hash值和长度-1进行按位与来作为索引查找，如果这个位置没有值。就生成一个新节点插入。
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
- 下面来详细看看else中的逻辑，如果这个位置以前有值
- 就看看这个值的hash值还有key值等不等于以前的值，如果都等，那么说明key是一样的，就会直接返回以前的那个node => p，来对旧结点进行操作。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
- 如果key值不等，就说明存在hash碰撞（hash碰撞就是key不同，但hash值相同的情况），那么接下来我就看看当前节点是不是树节点(红黑树)，如果是树节点就进行树节点的put操作
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
- 如果key值不等，并且不是树节点，那么说明现在是存入的是链表，就循环这个链表，如果遇到的节点为空，就将节点插入，如果插入后的节点数量超过8，那么就会将这个链表进行树化。如果在循环链表过程中又遇到有相同的key值，又直接对旧节点返回。
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
- 经过一大波周折，终于是拿到了需要插入节点在数组中的位置，但这个时候还需要看看，这个位置是不是已经存在数据了，如果存在就把以前的那个数据返给你，如果为空就说明可以插入你想插入的数据了。我们已经获得了插入数据的位置，这个时候这个位置可能为空，可能不为空。
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
- put操作的最后，有个modCount，它是记录数据被修改的次数，为什么需要这个次数的存在，这里简单提一下，因为HashMap是线程不安全的，如果HashMap使用迭代器但是其他线程修改了这个Hashmap，就会有ConcurrentModificationException，这个异常的抛出就是因为，在生成HashMap迭代器的时候会将这个修改次数赋给迭代器，当其他线程又去修改HashMap就会造成数据的不一致，所以使用这个修改次数就是一个另类的线程安全，即fail-fast策略。
- 接下来看size(指代当前HashMap的size)，因为要插入节点到数组中所以先自增，如果超门限值，数组就翻倍。afterNodeInsertion(evict)，这个在网上查了一下，是为了继承HashMap的LinkedHashMap类服务的，LinkedHashMap中被覆盖的afterNodeInsertion方法，用来回调移除最早放入Map的对象。至此put操作结束。
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
呼，说了这么多终于到get了
还是先代码再解释
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
- 同样get操作是通过调用getNode方法来实现的，还是老规矩先对key进行hash计算，传入函数，返回getNode函数返回的值。
- 第一个if判断，如果table为空就返回空值
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
- 不为空就先去看看第一个位置的节点hash值和key值是否相同(为什么要去先看第一个，因为存在hash碰撞的概率很小，通常链表中的节点数为一个，没必要去循环遍历整个链表，直接先看看第一个节点就是了，这里是为了效率考虑)
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
- 当然如果链表中不止一个节点那么就需要循环遍历了，如果存在多个hash碰撞这个是跑不掉的。如果节点是树节点那么就使用树节点的get方法来取数就是了。到这里get也结束了。
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
最后回答一下最开始提出的为什么java8以后链表数据超过8以后，就改成红黑树存储？
这就涉及到拒接服务攻击了，比如某些人通过找到你的hash碰撞值，来让你的HashMap不断地产生碰撞，那么相同key位置的链表就会不断增长，当你需要对这个HashMap的相应位置进行查询的时候，就会去循环遍历这个超级大的链表，性能及其地下。java8使用红黑树来替代超过8个节点数的链表后，查询方式性能得到了很好的提升，从原来的是O(n)到O(logn)。
网友评论