正文
HashMap源码详解（JDK7版本）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
一、内部属性
内部属性源码：
//内部数组的默认初始容量，作为hashmap的初始容量，是2的4次方，2的n次方的作用是减少hash冲突
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 //默认的最大容量
static final int MAXIMUM_CAPACITY = 1 << 30; //默认负载因子，当容器使用率达到这个75%的时候就扩容
static final float DEFAULT_LOAD_FACTOR = 0.75f; /**
*当数组表还没扩容的时候，一个共享的空表对象
*/
static final Entry<?,?>[] EMPTY_TABLE = {}; //内部数组表，用来装entry，大小只能是2的n次方。
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE; //存储的键值对的个数
transient int size; /**
* 扩容的临界点，如果当前容量达到该值，则需要扩容了。
* 如果当前数组容量为0时（空数组），则该值作为初始化内部数组的初始容量
*/
int threshold; //由构造函数传入的指定负载因子
final float loadFactor; //Hash的修改次数
transient int modCount; //threshold的最大值
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE; //计算hash值时候用，初始是0
transient int hashSeed = 0; //含有所有entry节点的一个set集合
private transient Set<Map.Entry<K,V>> entrySet = null; private static final long serialVersionUID = 362498820763181265L;
内部类Entry源码分析：
/**
* 内部类
* hashmap中每一个键值对都是存在Entry对象中，entry还存储了自己的hash值等信息
* Entry被储存在hashmap的内部数组中。
* @param <K> 键值名key
* @param <V> 键值value
*/
static class Entry<K,V> implements Map.Entry<K,V> {
//键值名
final K key;
//键值
V value;
//数组中每一项可能存储多个entry，而这些entry就是已链表的形式被存储，此next指向下一个entry
Entry<K,V> next;
//本entry的hash值
int hash; //初始化节点
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
//获取节点的key
public final K getKey() {
return key;
} //获取节点的value
public final V getValue() {
return value;
} //设置新value，并返回旧的value
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
} //判断传入节点与此结点的“key”和“value”是否相等。都相等则返回true
public final boolean equals(Object o) {
//如果传入对象不是Entry，则返回false
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
} //根据key和value的值生成hashCode
public final int hashCode() {
return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
} public final String toString() {
return getKey() + "=" + getValue();
} //每当相同key的value被覆盖时被调用一次，在HashMap的子类LinkedHashMap中实现了这个方法
void recordAccess(HashMap<K,V> m) {
} //每移除一个entry就被调用一次，在HashMap的子类LinkedHashMap中实现了这个方法；
void recordRemoval(HashMap<K,V> m) {
}
}
二、构造方法
构造源码分析：
/**
* 生成一个空HashMap，传入容量与负载因子
* @param initialCapacity 初始容量
* @param loadFactor 负载因子
*/
public HashMap(int initialCapacity, float loadFactor) {
//初始容量不能小于0
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//初始容量不能大于默认的最大容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY; //负载因子不能小于0，且不能为“NaN”（NaN（“不是一个数字（Not a Number）”的缩写））
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
//将传入的负载因子赋值给属性
this.loadFactor = loadFactor; //此时并不会创建容器，因为没有 传具体值
// 没下次扩容大小
/**
* 此时并不会创建容器，因为没有传具体值。
* 当下次传具体值的时候，才会“根据这次的初始容量”，创建一个内部数组。
* 所以此次的初始容量只是作为下一次扩容（新建）的容量。
*/
threshold = initialCapacity; //该方法只在LinkedHashMap中有实现，主要在构造函数初始化和clone、readObject中有调用。
init();
} /**
* 生成一个空hashmap，传入初始容量，负载因子使用默认值（0.75）
* @param initialCapacity 初始容量
*/
public HashMap(int initialCapacity) {
//生成空数组，并指定扩容值
this(initialCapacity, DEFAULT_LOAD_FACTOR);
} /**
* 生成一个空hashmap，初始容量和负载因子全部使用默认值。
*/
public HashMap() {
//生成空数组，并指定扩容值
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
} /**
* 根据已有map对象生成一个hashmap，初始容量与传入的map相关，负载因子使用默认值
* @param m Map对象
*/
public HashMap(Map<? extends K, ? extends V> m) {
//生成空数组，并指定扩容值
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); //由于此时数组为空，所以使用“扩容临界值”新建一个数组
inflateTable(threshold); //将传入map的键值对添加到初始数组中
putAllForCreate(m);
}
相关private方法源码分析：
/**
* 只在LinkedHashMap中有实现，主要在构造函数初始化和clone、readObject中有调用。
*/
void init() {
} /**
* 新建一个空的内部数组
* @param toSize 新数组容量
*/
private void inflateTable(int toSize) {
//内部数组的大小必须是2的n次方，所以要找到“大于”toSize的“最小的2的n次方”。
int capacity = roundUpToPowerOf2(toSize); //下次扩容临界值
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); table = new Entry[capacity]; //根据数组长度初始化hashseed
initHashSeedAsNeeded(capacity);
} /**
* 找到number的最小的2的n次方
* @param number
* @return
*/
private static int roundUpToPowerOf2(int number) { return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
} /**
* 根据内部数组长度初始化hashseed
* @param capacity 内部数组长度
* @return hashSeed是否初始化
*/
final boolean initHashSeedAsNeeded(int capacity) {
boolean currentAltHashing = hashSeed != 0;
boolean useAltHashing = sun.misc.VM.isBooted() && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean switching = currentAltHashing ^ useAltHashing; //为true则赋初始化值
if (switching) {
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
return switching;
} /**
* 静态内部类，提供一些静态常量
*/
private static class Holder { /**
* 容量阈值，初始化hashSeed的时候会用到该值
*/
static final int ALTERNATIVE_HASHING_THRESHOLD; static {
//获取系统变量jdk.map.althashing.threshold
String altThreshold = java.security.AccessController.doPrivileged(
new sun.security.action.GetPropertyAction(
"jdk.map.althashing.threshold")); int threshold;
try {
threshold = (null != altThreshold)
? Integer.parseInt(altThreshold)
: ALTERNATIVE_HASHING_THRESHOLD_DEFAULT; // jdk.map.althashing.threshold系统变量默认为-1，如果为-1，则将阈值设为Integer.MAX_VALUE
if (threshold == -1) {
threshold = Integer.MAX_VALUE;
}
//阈值需要为正数
if (threshold < 0) {
throw new IllegalArgumentException("value must be positive integer.");
}
} catch(IllegalArgumentException failed) {
throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
} ALTERNATIVE_HASHING_THRESHOLD = threshold;
}
} /**
* 添加指定map里面的所有键值对
* @param m
*/
private void putAllForCreate(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
putForCreate(e.getKey(), e.getValue());
} /**
* 添加键值对
* @param key 键值名
* @param value 键值
*/
private void putForCreate(K key, V value) {
//如果key为null，则hash值为0，否则根据key计算hash值
int hash = null == key ? 0 : hash(key); //根据hash值和数组的长度找到：该key所属entry在table中的位置i
int i = indexFor(hash, table.length); /**
* 数组中每一项存的都是一个链表，
* 先找到i位置，然后循环该位置上的每一个entry，
* 如果发现存在key与传入key相等，则替换其value。然后结束侧方法。
* 如果没有找到相同的key，则继续执行下一条指令，将此键值对存入链表头
*/
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
e.value = value;
return;
}
} //将该键值对存入指定下标的链表头中
createEntry(hash, key, value, i);
} /**
* 根据传入的key生成hash值
* @param k 键值名
* @return hash值
*/
final int hash(Object k) {
int h = hashSeed; //如果key是字符串类型，就使用stringHash32来生成hash值
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
} //一次散列
h ^= k.hashCode(); //二次散列
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
} /**
* 返回hash值的索引，采用除模取余法，h & (length-1)操作 等价于 hash % length操作， 但&操作性能更优
*/
/**
* 根据key的hash值与数组长度，找到该key在table数组中的下标
* @param h hash值
* @param length 数组长度
* @return 下标
*/
static int indexFor(int h, int length) {
//除模取余,相当于hash % length，&速度更快
return h & (length-1);
} /**
* 将键值对与他的hash值作为一个entry，插入table的指定下标中的链表头中
* @param hash hash值
* @param key 键值名
* @param value 键值
* @param bucketIndex 被插入的下标
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
三、存储
public方法源码分析：
/**
* 存入一个键值对，如果key重复，则更新value
* @param key 键值名
* @param value 键值
* @return 如果存的是新key则返回null，如果覆盖了旧键值对，则返回旧value
*/
public V put(K key, V value) {
//如果数组为空，则新建数组
if (table == EMPTY_TABLE) {
inflateTable(threshold);
} //如果key为null，则把value放在table[0]中
if (key == null)
return putForNullKey(value); //生成key所对应的hash值
int hash = hash(key); //根据hash值和数组的长度找到：该key所属entry在table中的位置i
int i = indexFor(hash, table.length); /**
* 数组中每一项存的都是一个链表，
* 先找到i位置，然后循环该位置上的每一个entry，
* 如果发现存在key与传入key相等，则替换其value。然后结束侧方法。
* 如果没有找到相同的key，则继续执行下一条指令，将此键值对存入链表头
*/
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
} //map操作次数加一
modCount++; //查看是否需要扩容，并将该键值对存入指定下标的链表头中
addEntry(hash, key, value, i); //如果是新存入的键值对，则返回null
return null;
} /**
* 将传入map的所有键值对存入本map
* @param m 传入map
*/
public void putAll(Map<? extends K, ? extends V> m) {
//传入数组的键值对数
int numKeysToBeAdded = m.size();
if (numKeysToBeAdded == 0)
return; //如果本地数组为空，则新建本地数组
if (table == EMPTY_TABLE) {
//从当前扩容临界值和传入数组的容量中选择大的一方作为初始数组容量
inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold));
} //如果传入map的键值对数比“下一次扩容后的内部数组大小”还大，则对数组进行扩容。（因为当前数组即使扩容后也装不下它）
if (numKeysToBeAdded > threshold) {
//确定新内部数组所需容量
int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
//不能大于最大容量
if (targetCapacity > MAXIMUM_CAPACITY)
targetCapacity = MAXIMUM_CAPACITY;
//当前数组长度
int newCapacity = table.length;
//从当前数组长度开始增加，每次增加一个“2次方”，直到大于所需容量为止
while (newCapacity < targetCapacity)
newCapacity <<= 1; //如果发现内部数组长度需要增加，则扩容内部数组
if (newCapacity > table.length)
resize(newCapacity);
} //遍历传入map，将键值对存入内部数组
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
相关private源码分析：
/**
* 如果key为null，则将其value存入table[0]的链表中
* @param value 键值
* @return 如果覆盖了旧value，则返回value，否则返回null
*/
private V putForNullKey(V value) {
//迭代table[0]中的链表里的每一个entry
for (Entry<K, V> e = table[0]; e != null; e = e.next) {
//如果找到key为null的entry，则覆盖其value，并返回旧value
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
} //操作次数加一
modCount++; //查看是否需要扩容，然后将entry插入table的指定下标中的链表头中
addEntry(0, null, value, 0);
return null;
} /**
* 查看是否需要扩容，然后添加新节点
* @param hash key的hash值
* @param key 结点内key
* @param value 结点内value
* @param bucketIndex 结点所在的table下标
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
//如果当前键值对数量达到了临界值，或目标table下标不存在，则扩容table
if ((size >= threshold) && (null != table[bucketIndex])) {
//容量扩容一倍
resize(2 * table.length);
//由于数组扩容了，重新计算hash值
hash = (null != key) ? hash(key) : 0;
//重新计算存储位置
bucketIndex = indexFor(hash, table.length);
} //将键值对与他的hash值作为一个entry，插入table的指定下标中的链表头中
createEntry(hash, key, value, bucketIndex);
} /**
* 对数组扩容，即创建一个新数组，并将旧数组里的东西重新存入新数组
* @param newCapacity 新数组容量
*/
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length; //如果当前数组容量已经达到最大值了，则将扩容的临界值设置为Integer.MAX_VALUE(Integer.MAX_VALUE是容量的临界点)
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
} //创建一个扩容后的新数组
Entry[] newTable = new Entry[newCapacity]; //将当前数组中的键值对存入新数组
transfer(newTable, initHashSeedAsNeeded(newCapacity)); //用新数组替换旧数组
table = newTable; //计算下一个扩容临界点
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
} /**
* 将现有数组中的内容重新通过hash计算存入新数组
* @param newTable 新数组
* @param rehash
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length; //遍历现有数组中的每一个单链表的头entry
for (Entry<K,V> e : table) {
//查找链表里的每一个entry
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
} //根据新的数组长度，重新计算此entry所在下标i
int i = indexFor(e.hash, newCapacity); //将entry放入下标i处链表的头部（将新数组此处的原有链表存入entry的next指针）
e.next = newTable[i]; //将链表存回下标i
newTable[i] = e; //查看下一个entry
e = next;
}
}
}
四、提取
public方法源码分析：
/**
* 返回此hashmap中存储的键值对个数
* @return 键值对个数
*/
public int size() {
return size;
} /**
* 根据key找到对应value
* @param key 键值名
* @return 键值value
*/
public V get(Object key) {
//如果key为null，则从table[0]中取value
if (key == null)
return getForNullKey(); //如果key不为null，则先根据key，找到其entry
Entry<K,V> entry = getEntry(key); //返回entry节点里的value值
return null == entry ? null : entry.getValue();
} /**
* 返回一个set集合，里面装的都是hashmap的value。
* 因为map中的key不能重复，set集合中的值也不能重复，所以可以装入set。
*
* 在hashmap的父类AbstractMap中，定义了Set<K> keySet = null;
* 如果keySet为null，则返回内部类KeySet。
* @return 含有所有key的set集合
*/
public Set<K> keySet() {
Set<K> ks = keySet;
return (ks != null ? ks : (keySet = new KeySet()));
} /**
* 返回一个Collection集合，里面装的都是hashmap的value。
* 因为map中的value可以重复，所以装入Collection。
*
* 在hashmap的父类AbstractMap中，定义了Collection<V> values = null;
* 如果values为null，则返回内部类Values。
*/
public Collection<V> values() {
Collection<V> vs = values;
return (vs != null ? vs : (values = new Values()));
} /**
* 返回一个set集合，里面装的是所有的entry结点
* （相当于把map集合转化成set集合）
* @return 含有所有entry的set集合
*/
public Set<Map.Entry<K,V>> entrySet() {
return entrySet0();
} /**
* 生成一个新的hashmap对象，新hashmap中数组也是新生成的，
* 但数组中的entry节点还是引用就hashmap中的元素。
* 所以对目前已有的节点进行修改会导致：原对象和clone对象都发生改变。
* 但进行新增或删除就不会影响对方，因为这相当于是对数组做出的改变，clone对象新生成了一个数组。
* @return clone出的hashmap
*/
public Object clone() {
HashMap<K,V> result = null;
try {
result = (HashMap<K,V>)super.clone();
} catch (CloneNotSupportedException e) {
}
if (result.table != EMPTY_TABLE) {
result.inflateTable(Math.min(
(int) Math.min(
size * Math.min(1 / loadFactor, 4.0f), HashMap.MAXIMUM_CAPACITY),
table.length));
}
result.entrySet = null;
result.modCount = 0;
result.size = 0;
result.init();
result.putAllForCreate(this); return result;
}
相关private源码分析：
/**
* 查找key为null的value
* （如果key为null，则hash值为0，并被保存在table[0]中）
* @return 对应value
*/
private V getForNullKey() {
if (size == 0) {
return null;
}
//查找table[0]处的链表，如果找到entry的key为null，就返回其value
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
} /**
* 根据key值查找所属entry节点
* @param key 键值名
* @return entry节点
*/
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
} //如果key为null，则其hash值为0，否则计算hash值
int hash = (key == null) ? 0 : hash(key); //根据hash值找到table下标，然后迭代该下标中的链表里的每一个entry节点
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
//如果找到该节点则返回该节点
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
} /**
* 内部类，生成一个set集合，里面装有此hashmap的所有key。
*/
private final class KeySet extends AbstractSet<K> {
public Iterator<K> iterator() {
return newKeyIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsKey(o);
}
public boolean remove(Object o) {
return HashMap.this.removeEntryForKey(o) != null;
}
public void clear() {
HashMap.this.clear();
}
} /**
* 内部类，生成一个Collection集合，里面装有此hashmap的所有value
*/
private final class Values extends AbstractCollection<V> {
public Iterator<V> iterator() {
return newValueIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsValue(o);
}
public void clear( ) {
HashMap.this.clear();
}
} /**
* 如果entrySet为null，则返回一个含有所有entry节点的一个set集合
* @return 含有所有entry节点的一个set集合
*/
private Set<Map.Entry<K,V>> entrySet0() {
Set<Map.Entry<K,V>> es = entrySet;
return es != null ? es : (entrySet = new EntrySet());
} /**
* 内部类，含有所有entry节点的一个set集合
*/
private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
//返回迭代器
public Iterator<Map.Entry<K,V>> iterator() {
return newEntryIterator();
} //查找传入entry是否存在
public boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<K,V> e = (Map.Entry<K,V>) o;
Entry<K,V> candidate = getEntry(e.getKey());
return candidate != null && candidate.equals(e);
} //删除
public boolean remove(Object o) {
return removeMapping(o) != null;
} //返回键值对数
public int size() {
return size;
} //清空
public void clear() {
HashMap.this.clear();
}
} /**
* 删除指定entry节点
* @param o 需要被删除的节点
* @return 如果删除失败返回null，删除成功
*/
final Entry<K,V> removeMapping(Object o) {
if (size == 0 || !(o instanceof Map.Entry))
return null; Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
Object key = entry.getKey();
int hash = (key == null) ? 0 : hash(key);
//得到数组索引
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
//开始遍历该单链表
while (e != null) {
Entry<K,V> next = e.next;
//找到节点
if (e.hash == hash && e.equals(entry)) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
} return e;
}
五、判断：
public方法源码分析：
/**
* 判断hashmap是否为空
* @return true为空，false为非空
*/
public boolean isEmpty() {
return size == 0;
} /**
* 判断指定key是否存在
* @param key 键值名
* @return 存在则返回true
*/
public boolean containsKey(Object key) {
return getEntry(key) != null;
} /**
* 判断是否含有指定value
* @param value 键值
* @return 含有则返回true
*/
public boolean containsValue(Object value) {
//如果value为null，则判断是否含有value为null的键值对
if (value == null)
return containsNullValue(); Entry[] tab = table;
//遍历table，找到每条链表
for (int i = 0; i < tab.length ; i++)
//遍历每条单链表，查看每一个entry的value是否为传入值
for (Entry e = tab[i] ; e != null ; e = e.next)
if (value.equals(e.value))
return true;
return false;
}
相关private源码分析：
/**
* 判断是否含有value为null的键值对
* @return 含有则返回true
*/
private boolean containsNullValue() {
Entry[] tab = table;
for (int i = 0; i < tab.length ; i++)
for (Entry e = tab[i] ; e != null ; e = e.next)
if (e.value == null)
return true;
return false;
}
六、删除
public方法源码分析：
/**
* 根据key删除entry节点
* @param key 被删除的entry的key值
* @return 被删除的节点的value，删除失败则返回null
*/
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
} /**
* 删除hashmap中的所有元素
*/
public void clear() {
modCount++;
//将table中的每一个元素都设置成null
Arrays.fill(table, null);
size = 0;
}
相关private源码分析：
/**
* 根据key删除entry节点
* @param key 被删除的entry的key值
* @return 被删除的节点，删除失败则返回null
*/
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
//计算key的hash值
int hash = (key == null) ? 0 : hash(key);
//计算所属下标
int i = indexFor(hash, table.length); //找到下标所存储的单链表的头节点
Entry<K,V> prev = table[i];
Entry<K,V> e = prev; //迭代单链表找到要删除的节点
while (e != null) {
Entry<K,V> next = e.next;
Object k; if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
} return e;
}
七、内部迭代器相关源码分析：
// 返回各种迭代器对象
Iterator<K> newKeyIterator() {
return new KeyIterator();
}
Iterator<V> newValueIterator() {
return new ValueIterator();
}
Iterator<Map.Entry<K,V>> newEntryIterator() {
return new EntryIterator();
}
//ValueIterator迭代器
private final class ValueIterator extends HashIterator<V> {
public V next() {
return nextEntry().value;
}
}
//KeyIterator迭代器
private final class KeyIterator extends HashIterator<K> {
public K next() {
return nextEntry().getKey();
}
}
//KeyIterator迭代器
private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
public Map.Entry<K,V> next() {
return nextEntry();
}
}
/**
* 所有迭代器的抽象父类
* @param <E> 存储的数据的类型
*/
private abstract class HashIterator<E> implements Iterator<E> {
//指向下一个节点
Entry<K,V> next;
//
int expectedModCount; // 用于判断快速失败行为
//当前table下标
int index;
//当前entry节点
Entry<K,V> current;
//构造函数，
/**
* 构造函数
* 使expectedModCount = modCount相等
*/
HashIterator() {
expectedModCount = modCount;
if (size > 0) {
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
}
public final boolean hasNext() {
return next != null;
}
final Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if ((next = e.next) == null) {
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
public void remove() {
if (current == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Object k = current.key;
current = null;
HashMap.this.removeEntryForKey(k);
expectedModCount = modCount;
}
}
// 返回各种迭代器对象
Iterator<K> newKeyIterator() {
return new KeyIterator();
}
Iterator<V> newValueIterator() {
return new ValueIterator();
}
Iterator<Map.Entry<K,V>> newEntryIterator() {
return new EntryIterator();
} //ValueIterator迭代器
private final class ValueIterator extends HashIterator<V> {
public V next() {
return nextEntry().value;
}
}
//KeyIterator迭代器
private final class KeyIterator extends HashIterator<K> {
public K next() {
return nextEntry().getKey();
}
}
//KeyIterator迭代器
private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
public Map.Entry<K,V> next() {
return nextEntry();
}
} /**
* 所有迭代器的抽象父类
* @param <E> 存储的数据的类型
*/
private abstract class HashIterator<E> implements Iterator<E> {
//指向下一个节点
Entry<K,V> next;
//
int expectedModCount; // 用于判断快速失败行为
//当前table下标
int index;
//当前entry节点
Entry<K,V> current; //构造函数， /**
* 构造函数
* 使expectedModCount = modCount相等
*/
HashIterator() {
expectedModCount = modCount;
if (size > 0) {
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
} public final boolean hasNext() {
return next != null;
} final Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException(); if ((next = e.next) == null) {
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
} public void remove() {
if (current == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Object k = current.key;
current = null;
HashMap.this.removeEntryForKey(k);
expectedModCount = modCount;
}
}
