HashMap详解
HashMap相关介绍
HashMap是Java中的比较常见的集合,主要存放的是键值对,以key-value的形式存储,不是线程安全的。它里面的存储的key和value可以为null值,但是key只允许有一个null值。HashMap是无序的,无法保证里面存储的键值对的有序性。jdk1.8之前的版本底层采用的是数组+链表的方式组成,jdk1.8之后采用的是数组+链表+红黑树的方式。数组具有查询效率高、插入、删除效率低,链表具有查询效率低,但是插入、删除效率高,HashMap采用这两种方式的结构,可以保证查询、插入、删除效率都得到保证。
HashMap数据结构
jdk1.8之后的版本使用数据+链表+红黑树的方式作为底层的数据结构,在链表长度大于阈值8之后,如果数组长度大于64时,才会转换成红黑树进行存储。阈值默认是8。下面我们介绍一下HashMap的设值过程:
-
我们在调用HashMap的put设值时,首先会对值进行hash操作。
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }
-
判断索引的数组位置是否为空,如果为空,则进行初始化,分配空间,进行扩容。
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);
-
如果这个位置有值,则需要解决冲突
-
首先判断链表的头,代码中的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();
-
关注微信公众号「平哥技术站」, 每日更新,在手机上阅读所有教程,随时随地都能学习。
原文链接:https://monkey.blog.xpyvip.top/archives/hashmap-xiang-jie
标签:hash,HashMap,value,链表,详解,key,null From: https://www.cnblogs.com/aibianchengya/p/16846233.html