本篇重点:
1.HashMap的存储结构
2.HashMap的put和get操作过程
3.HashMap的扩容
4.关于transient关键字
5.HashMap, HashTable, ConcurrentHashMap 对照
6.关于volatile关键字
HashMap的存储结构
-
HashMap 总体是数组+链表的存储结构, 从JDK1.8开始,当数组的长度大于64,且链表的长度大于8的时候,会把链表转为红黑树。
-
数组的默认长度是16。数组中的每一个元素为一个node,也就是链表的一个节点,node的数据包含: key的hashcode, key, value,指向下一个node节点的指针。
部分源码如下:
static class Node implements Map.Entry {
final int hash;
final K key;
V value;
Node next;
Node(int hash, K key, V value, Node next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
...
}
- 随着put操作的进行,如果数组的长度超过64,且链表的长度大于8的时候, 则将链表转为红黑树,红黑树节点的结构如下,TreeNode继承的LinkedHashMap.Entry是继承HashMap.Node的,所以TreeNode是上面Node的子类。
static final class TreeNode extends LinkedHashMap.Entry {
TreeNode parent; // red-black tree links
TreeNode left;
TreeNode right;
TreeNode prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node next) {
super(hash, key, val, next);
}
//...
}
- HashMap类的主要成员变量:
/* ---------------- Fields -------------- */
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node[] table;
/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
*/
transient Set> entrySet;
/**
* The number of key-value mappings contained in this map.
*/
transient int size;
/**
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
transient int modCount;
/**
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;
/**
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;
View Code
HashMap的put操作过程
本小节讲述put操作中的主要步骤,细小环节会忽略。
- map.put(key, value),首先计算key的hash,得到一个int值。
2.如果Node数组为空则初始化Node数组。这里注意,Node数组的长度length始终应该是2的n次方,比如默认的16, 还有32,64等
3.用 hash&(length-1) 运算得到数组下标,这里要提一句,其实正常我们最容易想到的,而且也是我之前很长一段时间以为的,这一步应该进行的是求模运算:hash % length,这样得到的正好是0~length-1之间的值,可以作为数组的下标, 那么为何此处是位与运算呢?
先说结论:上面提到数组的长度length始终是2^n,在这个前提下,hash & (length-1) 与hash % length是等价的。 而位与运算更快。这里另开一遍进行详解:HashMap的哈希函数为何用(n – 1) & hash
- 如果Node[hash&(length-1)]处为空,用传入的的key, value创建Node对象,直接放入该下标;如果该下标处不为空,且对象为TreeNode类型,证明此下标处的元素们是按照红黑树的结构存储的,将传入的key,value作为新的红黑树的节点插入到红黑树;否则,此处为链表,用next找到链表的末尾,将新的元素插入。如果在遍历链表的过程中发现链表的长度超过了8,此时如果数组长度
Original: https://www.cnblogs.com/adeline-tech/p/16666235.html
Author: adeline.pan
Title: Java 中HashMap详解(含HashTable, ConcurrentHashMap)
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/620342/
转载文章受原作者版权保护。转载请注明原作者出处!