HashMap详解

HashMap详解

HashMap相关介绍

HashMap是Java中的比较常见的集合，主要存放的是键值对，以key-value的形式存储，不是线程安全的。它里面的存储的key和value可以为null值，但是key只允许有一个null值。HashMap是无序的，无法保证里面存储的键值对的有序性。jdk1.8之前的版本底层采用的是数组+链表的方式组成，jdk1.8之后采用的是数组+链表+红黑树的方式。数组具有查询效率高、插入、删除效率低，链表具有查询效率低，但是插入、删除效率高，HashMap采用这两种方式的结构，可以保证查询、插入、删除效率都得到保证。

HashMap数据结构

jdk1.8之后的版本使用数据+链表+红黑树的方式作为底层的数据结构，在链表长度大于阈值8之后，如果数组长度大于64时，才会转换成红黑树进行存储。阈值默认是8。下面我们介绍一下HashMap的设值过程：

1. 我们在调用HashMap的put设值时，首先会对值进行hash操作。

   public V put(K key, V value) {
   	return putVal(hash(key), key, value, false, true);
   }
   1
   2
   3

2. 判断索引的数组位置是否为空，如果为空，则进行初始化，分配空间，进行扩容。

   if ((tab = table) == null || (n = tab.length) == 0)
   	n = (tab = resize()).length;
   1
   2

3. 判断这个位置是否有值，如果没有值，则创建一个新的节点。

   if ((p = tab[i = (n - 1) & hash]) == null)
   	tab[i] = newNode(hash, key, value, null);
   1
   2

4. 如果这个位置有值，则需要解决冲突

   • 首先判断链表的头，代码中的p，先判断hash值是否和我们的相同，如果hash值相同的话，在判断具体数值，如果相同，则先记录该位置，也就是代码中的e。

     Node<K,V> e; K k;
     if (p.hash == hash &&
       ((k = p.key) == key || (key != null && key.equals(k))))
       e = p;
     1
     2
     3
     4

   • 如果不同，那就需要遍历链表，jdk1.8之后的做了优化，链表太长时，会转换成红黑树，如果是TreeNode,则调用TreeNode的方法进行插入，此时就是采用的红黑树作为数据结构。

     else if (p instanceof TreeNode)
       e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
     1
     2

   • 如果不是TreeNode,则是用循环的方式遍历链表，如果有相同的链表节点，则记录该节点,代码中的e，如果没有相同的链表节点，则e为null,此时会创建一个新的Node，插入在链表最后。

     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;
     }
     1
     2
     3
     4
     5
     6
     7
     8
     9
     10
     11
     12

   • 最后判断e是不是null,e代表的是是否存在相同的值，存在，则记录的位置，不存在，则为null,如果存在，则会直接更新e记录的位置的值。

     if (e != null) { // existing mapping for key
         V oldValue = e.value;
         if (!onlyIfAbsent || oldValue == null)
             e.value = value;
         afterNodeAccess(e);
         return oldValue;
     }
     1
     2
     3
     4
     5
     6
     7

   • 在循环遍历链表时，如果该节点是个新的节点，插入在链表最后，此时会判断链表的长度是否大于TREEIFY_THRESHOLD - 1,默认是8，如果大于8,则会调用转换成红黑树的方法，但是，方法里面还会判断数组长度是否大于MIN_TREEIFY_CAPACITY,默认是64,如果大于，则转换成红黑树。

     if ((e = p.next) == null) {
         p.next = newNode(hash, key, value, null);
         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
             treeifyBin(tab, hash);
         break;
     }
     1
     2
     3
     4
     5
     6

     int n, index; Node<K,V> e;
     if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
         resize();
     1
     2
     3

关注微信公众号「平哥技术站」, 每日更新，在手机上阅读所有教程，随时随地都能学习。

原文链接:https://monkey.blog.xpyvip.top/archives/hashmap-xiang-jie