【JDK源码】HashMap-jdk1.8源码
先来一段源码注释hh
Map接口的基于哈希表的实现。 此实现提供所有可选的映射操作，并允许空值和空键。 （ HashMap类大致等同于Hashtable ，除了它是非同步的并且允许空值。）该类不保证映射的顺序； 特别是，它不保证订单会随着时间的推移保持不变。 此实现为基本操作（ get和put ）提供恒定时间性能，假设散列函数在桶中正确分散元素。 迭代集合视图需要的时间与HashMap实例的“容量”（桶的数量）加上它的大小（键值映射的数量）成正比。 因此，如果迭代性能很重要，则不要将初始容量设置得太高（或负载因子太低），这一点非常重要。 HashMap的实例有两个影响其性能的参数：初始容量和负载因子。 容量是哈希表中的桶数，初始容量就是哈希表创建时的容量。 负载因子是衡量哈希表在其容量自动增加之前允许达到多满的指标。 当哈希表中的条目数超过负载因子和当前容量的乘积时，重新哈希表（即重建内部数据结构），使哈希表具有大约两倍的桶数。 作为一般规则，默认负载因子 (.75) 在时间和空间成本之间提供了很好的权衡。 较高的值会减少空间开销，但会增加查找成本（反映在HashMap类的大多数操作中，包括get和put ）。 在设置其初始容量时，应考虑映射中的预期条目数及其负载因子，以尽量减少重新哈希操作的次数。 如果初始容量大于最大条目数除以负载因子，则不会发生重新哈希操作。 如果将许多映射存储在一个HashMap实例中，那么创建具有足够大容量的映射将比让它根据需要执行自动重新散列来更有效地存储映射以增加表。 请注意，使用具有相同hashCode()多个键是降低任何哈希表性能的可靠方法。 为了改善影响，当键是Comparable ，此类可以使用键之间的比较顺序来帮助打破联系。 请注意，此实现不是同步的。 如果多个线程并发访问一个散列映射，并且至少有一个线程在结构上修改了映射，则必须在外部进行同步。 （结构修改是添加或删除一个或多个映射的任何操作；仅更改与实例已包含的键关联的值不是结构修改。）这通常是通过同步一些自然封装映射的对象来完成的. 如果不存在这样的对象，则应使用Collections.synchronizedMap方法“包装”地图。 这最好在创建时完成，以防止对地图的意外不同步访问： Map m = Collections.synchronizedMap(new HashMap(...)); 此类的所有“集合视图方法”返回的迭代器都是快速失败的：如果在创建迭代器后的任何时间对映射进行结构修改，除了通过迭代器自己的remove方法以外的任何方式，迭代器都会抛出ConcurrentModificationException . 因此，面对并发修改，迭代器快速而干净地失败，而不是在未来不确定的时间冒着任意、非确定性行为的风险。 请注意，无法保证迭代器的快速失败行为，因为一般而言，在存在非同步并发修改的情况下不可能做出任何硬保证。 快速失败的迭代器会尽最大努力抛出ConcurrentModificationException 。 因此，编写一个依赖此异常来确保其正确性的程序是错误的：迭代器的快速失败行为应该仅用于检测错误。 此类是Java Collections Framework的成员
一、成员变量
private static final long serialVersionUID = 362498820763181265L;
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64;
--------------------------------------------------------------------------------------
/**
* 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<K,V>[] table;
/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
*/
transient Set<Map.Entry<K,V>> 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;
静态参数
serialVersionUID：序列化ID。DEFAULT_INITIAL_CAPACITY: 默认初始化容量，大小为16，扩容以2的倍数扩容。MAXIMUM_CAPACITY: 最大容量，大小为 1 << 30。DEFAULT_LOAD_FACTOR：默认负载因子，当达到元素个数 == 负载因子 * 容量时会进行扩容，比如 元素个数 = 12 = 16 * 0.75就会扩容。TREEIFY_THRESHOLD：树化阈值，当链表长度超过8则会成为转化为红黑树的条件之一。UNTREEIFY_THRESHOLD：当链表的值小于6则会从红黑树转回链表。MIN_TREEIFY_CAPACITY：树化另容量最小值，当map中的元素总和达到64时，而且链表长度大于等于8才会树化；当桶数组容量小于该值时，优先进行扩容，而不是树化。（这个值不能小于TREEIFY_THRESHOLD(8) * 4）。
动态参数
-
transient Node<K,V>[] table：HashMap的链表数组，扩容的时候总是2的次幂 -
transient Set<Map.Entry<K,V>> entrySet：表示HashMap中的Entry的Set集合 -
transient int size：表示HashMap中存放的键值对的个数 -
transient int modCount：凡是我们做的增删改都会引发modCount值的变化，跟版本控制功能类似，可以理解成version，在特定的操作下需要对version进行检查。- 在java的集合类中存在一种Fail-Fast的错误检测机制，当多个线程对同一集合的内容进行操作时，可能就会产生此类异常。比如当A通过iterator去遍历某集合的过程中，其他线程修改了此集合，此时会抛出ConcurrentModificationException异常。此类机制就是通过modCount实现的，在迭代器初始化时，会赋值expectedModCount，在迭代过程中判断modCount和expectedModCount是否一致
-
int threshold：扩容阈值，初始容量 * 负载因子。这个是在resize改变的，构造方法只会赋个初始容量。 -
final float loadFactor：自定义负载因子。一般都是用的自带的0.75。
二、内部类
存放于 table 中的 Node节点
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;//hash值
final K key;
V value;
Node<K,V> next;//用于发生hash冲突时转化链表用
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
三、构造方法
public HashMap(int initialCapacity, float loadFactor) {
//检查参数
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
// 调整阈值，将当前阈值为输入阈值的最小的2的次幂，并且此处相当于初始化容量，在第一次put resize的时候会初始化为 当前值 * 负载因子
this.threshold = tableSizeFor(initialCapacity);
}
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and the default load factor (0.75).
*
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// 通过Map集合来构造HashMap
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
- 主要是负载因子和容量的初始化，所以hashmap是懒加载，table的初始化会放在put时去做，节省空间。
- 如果传入容量大小不是2的整数幂，则会被调整为大于该值的最小2的整数幂
四、Hash函数
/*计算 key.hashCode() 并将哈希的较高位传播（XOR）到较低位。 由于该表使用二次幂掩码，因此仅在当前掩码之上位变化的散列集将始终发生冲突。 （已知的例子是在小表中保存连续整数的 Float 键集。）因此，我们应用了一种变换，将高位的影响向下传播。 在位扩展的速度、实用性和质量之间存在折衷。 因为许多常见的散列集已经合理分布（所以不要从传播中受益），并且因为我们使用树来处理 bin 中的大量冲突，我们只是以最便宜的方式对一些移位的位进行异或，以减少系统损失，以及合并最高位的影响，否则由于表边界，这些最高位将永远不会用于索引计算
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
- 获得key对应的hashcode
- 将hash值和无符号右移16位后的结果异或（扰动，低位相同概率较大，将数据均匀分布）
- 为什么异或? : 异或生成 0，1概率更平均。
五、put()
主要步骤
- 如果哈希表为空或者哈希表的长度为0，调用resize方法建立哈希表
- 根据hash值计算位置，如果计算出来的位置为空（没有hash冲突），直接插入
- 如果发生了hash冲突，并且第一个节点的key和要插入的key相等，则用e做个标记
- 如果不相等，则判断当前节点类型，如果是链表，则按照链表方式查找，如果是红黑树，按照红黑树方式查找。如果查找到了节点用e做个标记
- 在查找的过程中，如果没有查找到值，则会创建一个新的节点，然后插入数据（如果为链表方式插入时候还会判断是否要转换成红黑树）
- 如果查找到了相等的值的话e为查找到的值，否则为空，然后就可以根据e来替换值了。并且返回旧值
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)// 如果没有初始化table或者长度为0，则调用resize初始化
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);
// “binCount >= 7”：p从链表.index(0)开始，当binCount == 7时，p.index == 7,newNode.index == 8；
//也就是说，当链表已经有8个节点了，此时再新链上第9个节点，在成功添加了这个新节点之后，立马做链表转红黑树。
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);// 如果大于了转换树阈值（8），则转换成红黑树
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//不为null则覆盖原来的数据。
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;
}
treeifyBin()
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//如果n < MIN_TREEIFY_CAPACITY还是不会树化 ^_^
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
六、扩容resize()
主要步骤
-
首先获取当前哈希表的长度和当前的阈值
-
如果当前哈希表的大于0 ，并且长度大于最大允许长度了，就直接返回当前哈希表。
-
如果当前哈希表长度大于0，则新哈希表长度为当前的两倍，如果新哈希表的长度在16-最大值之间，新阈值是扩大为原来的两倍
-
如果哈希表长度小于等于0，但是当前阈值大于0（证明初始化的时候设置了初始容量，并且是第一次resize），则新的哈希表长度为当前的阈值
-
否则哈希表的长度为默认值（16），新的阈值为
默认容量 * 默认负载因子（12） -
如果新的阈值等于0（当前哈希表数组大小为1-15之间的值，或者初始化的时候设置了初始容量，并且是第一次resize）。将新阈值设置成
新哈希表容量 * 加载因子。（如果新的哈希表大小或者阈值超过了限制值，则新阈值为int的最大值） -
根据新阈值和新哈希表长度重建哈希表。
-
(e.hash & oldCap)：如果为0，则当前元素在新数组位置不会变化；如果不为0 ，则在新数组的位置是原下标 + 原数组长度。保证这个方式计算新位置正确的前提是：哈希表的大小为2的次幂示例1： e.hash= 10 0000 1010 oldCap=16 0001 0000 & =0 0000 0000 比较高位的第一位 0 结论：元素位置在扩容后数组中的位置没有发生改变 示例2： e.hash= 17 0001 0001 oldCap=16 0001 0000 & =1 0001 0000 比较高位的第一位 1 结论：元素位置在扩容后数组中的位置发生了改变，新的下标位置是原下标位置+原数组长度
-
//该函数有2种使用情况：1、初始化哈希表 2、当前数组容量过小，需扩容
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; // 扩容前的数组（当前数组）
int oldCap = (oldTab == null) ? 0 : oldTab.length; // 扩容前的数组的容量
int oldThr = threshold;// 扩容前的数组的阈值
int newCap, newThr = 0;
// 针对情况2：若扩容前的数组容量超过最大值，则不再扩充
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 针对情况2：若无超过最大值，就扩充为原来的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 通过右移扩充2倍
}
// 针对情况1：初始化哈希表（采用指定值或者默认值）
else if (oldThr > 0)
newCap = oldThr;
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 计算新的扩容阈值
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//旧数组数据移动到新数组里，整体过程也是遍历旧数组每个数据
if (oldTab != null) {
// 把每个bucket都移动到新的buckets中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 链表优化重hash的代码块
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//这个待会细讲
do {
next = e.next;
//原索引
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引 + oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
七、get()
主要步骤
- 获得key的hash然后根据hash和key按照插入时候的思路去查找get。
- 如果数组位置为NULL则直接返回 NULL。
- 如果数组位置不为NULL则先直接看数组位置是否符合。
- 如果数组位置有类型说红黑树类型，则按照红黑树类型查找返回。
- 如果数组有next，则按照遍历链表的方式查找返回。
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;
}
八、remove()
主要步骤
- 首先判断哈希表不为空，并且判断要删除的节点在哈希表的位置不为null，如果为null则直接返回null
- 否则判断第一个节点的键和要删除的键是否相等。如果相等，用node记录当前节点。
- 如果不相等判断是否是红黑树节点，如果是红黑树节点按照红黑树方式查找，否则按照链表方式查找。如果找到了使用node记录当前节点
- 如果找到了节点，然后看是否还要匹配value，如果都通过匹配了那么就开始删除了
- 如果是红黑树节点，按照红黑树方式删除节点，如果是第一个节点，直接将下一个作为头节点，否则链表删除。然后更新版本号和大小
/**
* @param hash 要移除的key的hash
* @param key 要删除的key
* @param value 要删除的value，只有当matchValue为true的时候才有用
* @param matchValue 是否要将value也作为删除判断的依据
* @param movable 删除之后是否移动节点，如果为false则不移动
* @return 如果删除了返回被删除对象，否则返回null
*/
final HashMap.Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) { // 确保哈希表不为空，并且通过哈希表获取得到值。否则直接返回
HashMap.Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p; // 如果头节点（或根节点）的键和查找的键相等
else if ((e = p.next) != null) { // 如果有哈希冲突的节点
if (p instanceof HashMap.TreeNode) // 如果是一个红黑树的节点，按照红黑树的方式获取节点
node = ((HashMap.TreeNode<K,V>)p).getTreeNode(hash, key);
else { // 否则按照链表的方式查找节点
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value || // 如果查找到了节点，再判断一下是否还需要通过value判断
(value != null && value.equals(v)))) {
// 进入此处的节点，那么这个节点就确定是要删除的了
if (node instanceof HashMap.TreeNode) // 如果是红黑树节点，按照红黑树的方式删除
((HashMap.TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p) // 如果node == p，则证明要删除的节点是头节点（不是根节点，根节点会进入上一个if）
tab[index] = node.next;
else // 否则链表方式删除节点
p.next = node.next;
++modCount; // 更新版本号，便于后续抛出异常
--size; // 减小大小
afterNodeRemoval(node);
return node; // 返回删除的节点
}
}
// 如果没有查找到节点的话就返回null
return null;
}
查看10道真题和解析
国家电网工作强度 101人发布
