转载

HashMap的put、get原理解读

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)。

原文 https://juejin.im/post/5d6a0674f265da03c8153832

正文到此结束