侧边栏壁纸
博主头像
Monkey部落博主等级

Monkey部落,分享技术、经验、遇到的问题及解决方法,欢迎大家互相讨论分享。

  • 累计撰写 59 篇文章
  • 累计创建 36 个标签
  • 累计收到 2 条评论

目 录CONTENT

文章目录

HashMap详解

Monkey部落
2022-10-31 / 1 评论 / 0 点赞 / 527 阅读 / 1,092 字

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);
    }
    
  2. 判断索引的数组位置是否为空,如果为空,则进行初始化,分配空间,进行扩容。

    if ((tab = table) == null || (n = tab.length) == 0)
    	n = (tab = resize()).length;
    
  3. 判断这个位置是否有值,如果没有值,则创建一个新的节点。

    if ((p = tab[i = (n - 1) & hash]) == null)
    	tab[i] = newNode(hash, key, value, null);
    
  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;
      
    • 如果不同,那就需要遍历链表,jdk1.8之后的做了优化,链表太长时,会转换成红黑树,如果是TreeNode,则调用TreeNode的方法进行插入,此时就是采用的红黑树作为数据结构。

      else if (p instanceof TreeNode)
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
      
    • 如果不是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;
      }
      
    • 最后判断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;
      }
      
    • 在循环遍历链表时,如果该节点是个新的节点,插入在链表最后,此时会判断链表的长度是否大于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;
      }
      
      int n, index; Node<K,V> e;
      if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
          resize();
      

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

觉得写的还不错的小伙伴,请作者喝杯咖啡☕ ,支持一下。😊

如有侵权请立即与我们联系,我们将及时处理,联系邮箱:865934097@qq.com。

0

评论区