青岛达内it培训 > 达内新闻
HashMap 源码详细分析(JDK1.8)1
- 发布:青岛IT培训
- 来源:青岛IT培训
- 时间:2019-04-17 11:41
青岛IT培训的小编总结,本篇文章我们来聊聊大家日常开发中常用的一个集合类 - HashMap.HashMap 最早出现在 JDK 1.2中,底层基于散列算法实现。HashMap 允许 null 键和 null 值,在计算哈键的哈希值时,null 键哈希值为 0.HashMap 并不保证键值对的顺序,这意味着在进行某些操作后,键值对的顺序可能会发生变化。另外,需要注意的是,HashMap 是非线程安全类,在多线程环境下可能会存在问题。
在本篇文章中,我将会对 HashMap 中常用方法、重要属性及相关方法进行分析。需要说明的是,HashMap 源码中可分析的点很多,本文很难一一覆盖,请见谅。
2.原理
上一节说到 HashMap 底层是基于散列算法实现,散列算法分为散列再探测和拉链式。HashMap 则使用了拉链式的散列算法,并在 JDK 1.8 中引入了红黑树优化过长的链表。
对于拉链式的散列算法,其数据结构是由数组和链表(或树形结构)组成。在进行增删查等操作时,首先要定位到元素的所在桶的位置,之后再从链表中定位该元素。比如我们要查询上图结构中是否包含元素35,步骤如下:
定位元素35所处桶的位置,index = 35 % 16 = 3
在3号桶所指向的链表中继续查找,发现35在链表中。
上面就是 HashMap 底层数据结构的原理,HashMap 基本操作就是对拉链式散列算法基本操作的一层包装。不同的地方在于 JDK 1.8 中引入了红黑树,底层数据结构由数组+链表变为了数组+链表+红黑树,不过本质并未变。好了,原理部分先讲到这,接下来说说源码实现。
3.源码分析
本篇文章所分析的源码版本为 JDK 1.8.与 JDK 1.7 相比,JDK 1.8 对 HashMap 进行了一些优化。比如引入红黑树解决过长链表效率低的问题。重写 resize 方法,移除了 alternative hashing 相关方法,避免重新计算键的 hash 等。不过本篇文章并不打算对这些优化进行分析,本文仅会分析 HashMap 常用的方法及一些重要属性和相关方法。如果大家对红黑树感兴趣,可以阅读我的另一篇文章 - 红黑树详细分析。
3.1 构造方法
3.1.1 构造方法分析
HashMap 的构造方法不多,只有四个。HashMap 构造方法做的事情比较简单,一般都是初始化一些重要变量,比如 loadFactor 和 threshold.而底层的数据结构则是延迟到插入键值对时再进行初始化。HashMap 相关构造方法如下:
/** 构造方法 1 */
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/** 构造方法 2 */
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/** 构造方法 3 */
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;
this.threshold = tableSizeFor(initialCapacity);
}
/** 构造方法 4 */
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
上面4个构造方法中,大家平时用的最多的应该是第一个了。第一个构造方法很简单,仅将 loadFactor 变量设为默认值。构造方法2调用了构造方法3,而构造方法3仍然只是设置了一些变量。构造方法4则是将另一个 Map 中的映射拷贝一份到自己的存储结构中来,这个方法不是很常用。
上面就是对构造方法简单的介绍,构造方法本身并没什么太多东西,所以就不说了。接下来说说构造方法所初始化的几个的变量。
3.1.2 初始容量、负载因子、阈值
我们在一般情况下,都会使用无参构造方法创建 HashMap.但当我们对时间和空间复杂度有要求的时候,使用默认值有时可能达不到我们的要求,这个时候我们就需要手动调参。在 HashMap 构造方法中,可供我们调整的参数有两个,一个是初始容量 initialCapacity,另一个负载因子 loadFactor.通过这两个设定这两个参数,可以进一步影响阈值大小。但初始阈值 threshold 仅由 initialCapacity 经过移位操作计算得出。
相关代码如下:
/** The default initial capacity - MUST be a power of two. */
static final int DEFAULT_INITIAL_CAPACITY = 1 《 4;
/** The load factor used when none specified in constructor. */
static final float DEFAULT_LOAD_FACTOR = 0.75f;
final float loadFactor;
/** The next size value at which to resize (capacity * load factor)。 */
int threshold;
如果大家去看源码,会发现 HashMap 中没有定义 initialCapacity 这个变量。这个也并不难理解,从参数名上可看出,这个变量表示一个初始容量,只是构造方法中用一次,没必要定义一个变量保存。但如果大家仔细看上面 HashMap 的构造方法,会发现存储键值对的数据结构并不是在构造方法里初始化的。这就有个疑问了,既然叫初始容量,但最终并没有用与初始化数据结构,那传这个参数还有什么用呢?这个问题我先不解释,给大家留个悬念,后面会说明。
默认情况下,HashMap 初始容量是16,负载因子为 0.75.这里并没有默认阈值,原因是阈值可由容量乘上负载因子计算而来(注释中有说明),即threshold = capacity * loadFactor.但当你仔细看构造方法3时,会发现阈值并不是由上面公式计算而来,而是通过一个方法算出来的。这是不是可以说明 threshold 变量的注释有误呢?还是仅这里进行了特殊处理,其他地方遵循计算公式呢?关于这个疑问,这里也先不说明,后面在分析扩容方法时,再来解释这个问题。接下来,我们来看看初始化 threshold 的方法长什么样的的,源码如下:
/**
* Returns a power of two size for the given target capacity.
*/
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;
}
上面的代码长的有点不太好看,反正我第一次看的时候不明白它想干啥。不过后来在纸上画画,知道了它的用途。总结起来就一句话:找到大于或等于 cap 的最小2的幂。至于为啥要这样,后面再解释。
上面是 tableSizeFor 方法的计算过程图,这里cap = 536,870,913 = 2<sup>29</sup> + 1,多次计算后,算出n + 1 = 1,073,741,824 = 2<sup>30</sup>.通过图解应该可以比较容易理解这个方法的用途,这里就不多说了。
说完了初始阈值的计算过程,再来说说负载因子(loadFactor)。对于 HashMap 来说,负载因子是一个很重要的参数,该参数反应了 HashMap 桶数组的使用情况(假设键值对节点均匀分布在桶数组中)。通过调节负载因子,可使 HashMap 时间和空间复杂度上有不同的表现。当我们调低负载因子时,HashMap 所能容纳的键值对数量变少。扩容时,重新将键值对存储新的桶数组里,键的键之间产生的碰撞会下降,链表长度变短。此时,HashMap 的增删改查等操作的效率将会变高,这里是典型的拿空间换时间。相反,如果增加负载因子(负载因子可以大于1),HashMap 所能容纳的键值对数量变多,空间利用率高,但碰撞率也高。这意味着链表长度变长,效率也随之降低,这种情况是拿时间换空间。至于负载因子怎么调节,这个看使用场景了。一般情况下,我们用默认值就可以了。
3.2 查找
HashMap 的查找操作比较简单,查找步骤与原理篇介绍一致,即先定位键值对所在的桶的位置,然后再对链表或红黑树进行查找。通过这两步即可完成查找,该操作相关代码如下:
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;
// 1. 定位键值对所在桶的位置
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) {
// 2. 如果 first 是 TreeNode 类型,则调用黑红树查找方法
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first)。getTreeNode(hash, key);
// 2. 对链表进行查找
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}

查找的核心逻辑是封装在 getNode 方法中的,getNode 方法源码我已经写了一些注释,应该不难看懂。我们先来看看查找过程的第一步 - 确定桶位置,其实现代码如下:
// index = (n - 1) & hash
first = tab[(n - 1) & hash]
这里通过(n - 1)& hash即可算出桶的在桶数组中的位置,可能有的朋友不太明白这里为什么这么做,这里简单解释一下。HashMap 中桶数组的大小 length 总是2的幂,此时,(n - 1) & hash 等价于对 length 取余。但取余的计算效率没有位运算高,所以(n - 1) & hash也是一个小的优化。举个例子说明一下吧,假设 hash = 185,n = 16.
3.3 遍历
和查找查找一样,遍历操作也是大家使用频率比较高的一个操作。对于 遍历 HashMap,我们一般都会用下面的方式:
for(Object key : map.keySet()) {
// do something
}
或
for(HashMap.Entry entry : map.entrySet()) {
// do something
}
从上面代码片段中可以看出,大家一般都是对 HashMap 的 key 集合或 Entry 集合进行遍历。上面代码片段中用 foreach 遍历 keySet 方法产生的集合,在编译时会转换成用迭代器遍历,等价于:
Set keys = map.keySet();
Iterator ite = keys.iterator();
while (ite.hasNext()) {
Object key = ite.next();
// do something
}
大家在遍历 HashMap 的过程中会发现,多次对 HashMap 进行遍历时,遍历结果顺序都是一致的。但这个顺序和插入的顺序一般都是不一致的。产生上述行为的原因是怎样的呢?大家想一下原因。我先把遍历相关的代码贴出来,如下:
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
ks = new KeySet();
keySet = ks;
}
return ks;
}
/**
* 键集合
*/
final class KeySet extends AbstractSet<K> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<K> iterator() { return new KeyIterator(); }
public final boolean contains(Object o) { return containsKey(o); }
public final boolean remove(Object key) {
return removeNode(hash(key), key, null, false, true) != null;
}
// 省略部分代码
}
/**
* 键迭代器
*/
final class KeyIterator extends HashIterator
implements Iterator<K> {
public final K next() { return nextNode()。key; }
}
abstract class HashIterator {
Node<K,V> next; // next entry to return
Node<K,V> current; // current entry
int expectedModCount; // for fast-fail
int index; // current slot
HashIterator() {
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) { // advance to first entry
// 寻找第一个包含链表节点引用的桶
do {} while (index < t.length && (next = t[index++]) == null);
}
}
public final boolean hasNext() {
return next != null;
}
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e)。next) == null && (t = table) != null) {
// 寻找下一个包含链表节点引用的桶
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
//省略部分代码
}
如上面的源码,遍历所有的键时,首先要获取键集合KeySet对象,然后再通过 KeySet 的迭代器KeyIterator进行遍历。KeyIterator 类继承自HashIterator类,核心逻辑也封装在 HashIterator 类中。HashIterator 的逻辑并不复杂,在初始化时,HashIterator 先从桶数组中找到包含链表节点引用的桶。然后对这个桶指向的链表进行遍历。遍历完成后,再继续寻找下一个包含链表节点引用的桶,找到继续遍历。找不到,则结束遍历。
以上就是青岛IT培训给大家做的内容详解,更多关于UI的学习,请继续关注青岛IT培训
最新开班时间
- 北京
- 上海
- 广州
- 深圳
- 南京
- 成都
- 武汉
- 西安
- 青岛
- 天津
- 杭州
- 重庆
- 哈尔滨
- 济南
- 沈阳
- 合肥
- 郑州
- 长春
- 苏州
- 长沙
- 昆明
- 太原
- 无锡
- 石家庄
- 南宁
- 佛山
- 珠海
- 宁波
- 保定
- 呼和浩特
- 洛阳
- 烟台
- 运城
- 潍坊
HashMap 源码详细分析(JDK1.8)1
- 发布:青岛IT培训
- 来源:青岛IT培训
- 时间:2019-04-17 11:41
青岛IT培训的小编总结,本篇文章我们来聊聊大家日常开发中常用的一个集合类 - HashMap.HashMap 最早出现在 JDK 1.2中,底层基于散列算法实现。HashMap 允许 null 键和 null 值,在计算哈键的哈希值时,null 键哈希值为 0.HashMap 并不保证键值对的顺序,这意味着在进行某些操作后,键值对的顺序可能会发生变化。另外,需要注意的是,HashMap 是非线程安全类,在多线程环境下可能会存在问题。
在本篇文章中,我将会对 HashMap 中常用方法、重要属性及相关方法进行分析。需要说明的是,HashMap 源码中可分析的点很多,本文很难一一覆盖,请见谅。
2.原理
上一节说到 HashMap 底层是基于散列算法实现,散列算法分为散列再探测和拉链式。HashMap 则使用了拉链式的散列算法,并在 JDK 1.8 中引入了红黑树优化过长的链表。
对于拉链式的散列算法,其数据结构是由数组和链表(或树形结构)组成。在进行增删查等操作时,首先要定位到元素的所在桶的位置,之后再从链表中定位该元素。比如我们要查询上图结构中是否包含元素35,步骤如下:
定位元素35所处桶的位置,index = 35 % 16 = 3
在3号桶所指向的链表中继续查找,发现35在链表中。
上面就是 HashMap 底层数据结构的原理,HashMap 基本操作就是对拉链式散列算法基本操作的一层包装。不同的地方在于 JDK 1.8 中引入了红黑树,底层数据结构由数组+链表变为了数组+链表+红黑树,不过本质并未变。好了,原理部分先讲到这,接下来说说源码实现。
3.源码分析
本篇文章所分析的源码版本为 JDK 1.8.与 JDK 1.7 相比,JDK 1.8 对 HashMap 进行了一些优化。比如引入红黑树解决过长链表效率低的问题。重写 resize 方法,移除了 alternative hashing 相关方法,避免重新计算键的 hash 等。不过本篇文章并不打算对这些优化进行分析,本文仅会分析 HashMap 常用的方法及一些重要属性和相关方法。如果大家对红黑树感兴趣,可以阅读我的另一篇文章 - 红黑树详细分析。
3.1 构造方法
3.1.1 构造方法分析
HashMap 的构造方法不多,只有四个。HashMap 构造方法做的事情比较简单,一般都是初始化一些重要变量,比如 loadFactor 和 threshold.而底层的数据结构则是延迟到插入键值对时再进行初始化。HashMap 相关构造方法如下:
/** 构造方法 1 */
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/** 构造方法 2 */
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/** 构造方法 3 */
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;
this.threshold = tableSizeFor(initialCapacity);
}
/** 构造方法 4 */
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
上面4个构造方法中,大家平时用的最多的应该是第一个了。第一个构造方法很简单,仅将 loadFactor 变量设为默认值。构造方法2调用了构造方法3,而构造方法3仍然只是设置了一些变量。构造方法4则是将另一个 Map 中的映射拷贝一份到自己的存储结构中来,这个方法不是很常用。
上面就是对构造方法简单的介绍,构造方法本身并没什么太多东西,所以就不说了。接下来说说构造方法所初始化的几个的变量。
3.1.2 初始容量、负载因子、阈值
我们在一般情况下,都会使用无参构造方法创建 HashMap.但当我们对时间和空间复杂度有要求的时候,使用默认值有时可能达不到我们的要求,这个时候我们就需要手动调参。在 HashMap 构造方法中,可供我们调整的参数有两个,一个是初始容量 initialCapacity,另一个负载因子 loadFactor.通过这两个设定这两个参数,可以进一步影响阈值大小。但初始阈值 threshold 仅由 initialCapacity 经过移位操作计算得出。
相关代码如下:
/** The default initial capacity - MUST be a power of two. */
static final int DEFAULT_INITIAL_CAPACITY = 1 《 4;
/** The load factor used when none specified in constructor. */
static final float DEFAULT_LOAD_FACTOR = 0.75f;
final float loadFactor;
/** The next size value at which to resize (capacity * load factor)。 */
int threshold;
如果大家去看源码,会发现 HashMap 中没有定义 initialCapacity 这个变量。这个也并不难理解,从参数名上可看出,这个变量表示一个初始容量,只是构造方法中用一次,没必要定义一个变量保存。但如果大家仔细看上面 HashMap 的构造方法,会发现存储键值对的数据结构并不是在构造方法里初始化的。这就有个疑问了,既然叫初始容量,但最终并没有用与初始化数据结构,那传这个参数还有什么用呢?这个问题我先不解释,给大家留个悬念,后面会说明。
默认情况下,HashMap 初始容量是16,负载因子为 0.75.这里并没有默认阈值,原因是阈值可由容量乘上负载因子计算而来(注释中有说明),即threshold = capacity * loadFactor.但当你仔细看构造方法3时,会发现阈值并不是由上面公式计算而来,而是通过一个方法算出来的。这是不是可以说明 threshold 变量的注释有误呢?还是仅这里进行了特殊处理,其他地方遵循计算公式呢?关于这个疑问,这里也先不说明,后面在分析扩容方法时,再来解释这个问题。接下来,我们来看看初始化 threshold 的方法长什么样的的,源码如下:
/**
* Returns a power of two size for the given target capacity.
*/
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;
}
上面的代码长的有点不太好看,反正我第一次看的时候不明白它想干啥。不过后来在纸上画画,知道了它的用途。总结起来就一句话:找到大于或等于 cap 的最小2的幂。至于为啥要这样,后面再解释。
上面是 tableSizeFor 方法的计算过程图,这里cap = 536,870,913 = 2<sup>29</sup> + 1,多次计算后,算出n + 1 = 1,073,741,824 = 2<sup>30</sup>.通过图解应该可以比较容易理解这个方法的用途,这里就不多说了。
说完了初始阈值的计算过程,再来说说负载因子(loadFactor)。对于 HashMap 来说,负载因子是一个很重要的参数,该参数反应了 HashMap 桶数组的使用情况(假设键值对节点均匀分布在桶数组中)。通过调节负载因子,可使 HashMap 时间和空间复杂度上有不同的表现。当我们调低负载因子时,HashMap 所能容纳的键值对数量变少。扩容时,重新将键值对存储新的桶数组里,键的键之间产生的碰撞会下降,链表长度变短。此时,HashMap 的增删改查等操作的效率将会变高,这里是典型的拿空间换时间。相反,如果增加负载因子(负载因子可以大于1),HashMap 所能容纳的键值对数量变多,空间利用率高,但碰撞率也高。这意味着链表长度变长,效率也随之降低,这种情况是拿时间换空间。至于负载因子怎么调节,这个看使用场景了。一般情况下,我们用默认值就可以了。
3.2 查找
HashMap 的查找操作比较简单,查找步骤与原理篇介绍一致,即先定位键值对所在的桶的位置,然后再对链表或红黑树进行查找。通过这两步即可完成查找,该操作相关代码如下:
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;
// 1. 定位键值对所在桶的位置
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) {
// 2. 如果 first 是 TreeNode 类型,则调用黑红树查找方法
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first)。getTreeNode(hash, key);
// 2. 对链表进行查找
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}

查找的核心逻辑是封装在 getNode 方法中的,getNode 方法源码我已经写了一些注释,应该不难看懂。我们先来看看查找过程的第一步 - 确定桶位置,其实现代码如下:
// index = (n - 1) & hash
first = tab[(n - 1) & hash]
这里通过(n - 1)& hash即可算出桶的在桶数组中的位置,可能有的朋友不太明白这里为什么这么做,这里简单解释一下。HashMap 中桶数组的大小 length 总是2的幂,此时,(n - 1) & hash 等价于对 length 取余。但取余的计算效率没有位运算高,所以(n - 1) & hash也是一个小的优化。举个例子说明一下吧,假设 hash = 185,n = 16.
3.3 遍历
和查找查找一样,遍历操作也是大家使用频率比较高的一个操作。对于 遍历 HashMap,我们一般都会用下面的方式:
for(Object key : map.keySet()) {
// do something
}
或
for(HashMap.Entry entry : map.entrySet()) {
// do something
}
从上面代码片段中可以看出,大家一般都是对 HashMap 的 key 集合或 Entry 集合进行遍历。上面代码片段中用 foreach 遍历 keySet 方法产生的集合,在编译时会转换成用迭代器遍历,等价于:
Set keys = map.keySet();
Iterator ite = keys.iterator();
while (ite.hasNext()) {
Object key = ite.next();
// do something
}
大家在遍历 HashMap 的过程中会发现,多次对 HashMap 进行遍历时,遍历结果顺序都是一致的。但这个顺序和插入的顺序一般都是不一致的。产生上述行为的原因是怎样的呢?大家想一下原因。我先把遍历相关的代码贴出来,如下:
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
ks = new KeySet();
keySet = ks;
}
return ks;
}
/**
* 键集合
*/
final class KeySet extends AbstractSet<K> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<K> iterator() { return new KeyIterator(); }
public final boolean contains(Object o) { return containsKey(o); }
public final boolean remove(Object key) {
return removeNode(hash(key), key, null, false, true) != null;
}
// 省略部分代码
}
/**
* 键迭代器
*/
final class KeyIterator extends HashIterator
implements Iterator<K> {
public final K next() { return nextNode()。key; }
}
abstract class HashIterator {
Node<K,V> next; // next entry to return
Node<K,V> current; // current entry
int expectedModCount; // for fast-fail
int index; // current slot
HashIterator() {
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) { // advance to first entry
// 寻找第一个包含链表节点引用的桶
do {} while (index < t.length && (next = t[index++]) == null);
}
}
public final boolean hasNext() {
return next != null;
}
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e)。next) == null && (t = table) != null) {
// 寻找下一个包含链表节点引用的桶
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
//省略部分代码
}
如上面的源码,遍历所有的键时,首先要获取键集合KeySet对象,然后再通过 KeySet 的迭代器KeyIterator进行遍历。KeyIterator 类继承自HashIterator类,核心逻辑也封装在 HashIterator 类中。HashIterator 的逻辑并不复杂,在初始化时,HashIterator 先从桶数组中找到包含链表节点引用的桶。然后对这个桶指向的链表进行遍历。遍历完成后,再继续寻找下一个包含链表节点引用的桶,找到继续遍历。找不到,则结束遍历。
以上就是青岛IT培训给大家做的内容详解,更多关于UI的学习,请继续关注青岛IT培训
最新开班时间
- 北京
- 上海
- 广州
- 深圳
- 南京
- 成都
- 武汉
- 西安
- 青岛
- 天津
- 杭州
- 重庆
- 厦门
- 哈尔滨
- 济南
- 福州
- 沈阳
- 合肥
- 郑州
- 长春
- 苏州
- 大连
- 长沙
- 昆明
- 温州
- 太原
- 南昌
- 无锡
- 石家庄
- 南宁
- 中山
- 兰州
- 佛山
- 珠海
- 宁波
- 贵阳
- 保定
- 呼和浩特
- 东莞
- 洛阳
- 潍坊
- 烟台
- 运城