内容简介：JAVA集合：HashMap深度解析（版本对比）
关于 JAVA 的集合框架近期也会逐渐同步跟新出来，欢迎小伙伴们多提意见
今天先为JAVA集合系列源码开一个头，也尝试着用不同的方式，不同的角度去阅读源码，去学习源码中的一些思想。HashMap作为最常使用的集合之一;JDK1.7之前，有很大的争议，一方面是数据量变大之后的查询效率问题，还有就是线程安全问题。本文将从JDK1.7和1.8两个不同版本的源码入手，去探寻一下HashMap是如何被优化的，以及线程安全问题的出现情况。
jdk1.7
HashMap在1.7中和1.6的主要区别：
- 加入了jdk.map.althashing.threshold这个jdk的参数用来控制是否在扩容时使用String类型的新hash算法。
- 把1.6的构造方法中对表的初始化挪到了put方法中。
- 1.6中的tranfer方法对旧表的节点进行置null操作（存在多线程问题），1.7中去掉了。
定义
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
HashMap继承自AbstractMap，实现了Map，Cloneable，和Serializable。既然实现了Serializable接口,也就是说可以实现序列化，在下面的成员变量介绍中可以看到，table[]使用了transient来修饰的，这个对于大多数集合框架中的类来说都有这种机制。查阅了相关资料和结合网上各路大神的解释，这里总结一下：
-
减少不必要的空值序列化
table 以及 elementData中存储的数据的数量通常情况下是要小于数组长度的（扩容机制），这个在数据越来越多的情况下更为明显（数据变多，伴随着冲突概率变大，同时也伴随着扩容）。如果使用默认的序列化，那些没有数据的位置也会被存储，就会产生很多不必要的浪费。 -
不同虚拟机的兼容问题
由于不同的虚拟机对于相同hashCode产生的Code值可能是不一样的，如果使用默认的序列化，那么反序列化后，元素的位置和之前的是保持一致的，可是由于hashCode的值不一样了，那么定位到的桶的下标就会不同，这很明显不是我们想看到的
所在HashMap的序列化 并没有使用默认的序列化方法，而采用自定义的序列化方法，通过重写writeObject方法来完成。
成员变量
- 默认初始容量16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
- 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
- 默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
- 空表实例
static final Entry<?,?>[] EMPTY_TABLE = {};
- table，一个Entry数组
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
- size，map中key-value的总数
transient int size;
- 阈值，当map中key-value的总数达到这个值时，进行扩容
int threshold;
- 负载因子
final float loadFactor;
- 被修改的次数(fial-fast机制)
transient int modCount;
- alternative hashing（如果使用了String类型的一种新hash算法）的默认阈值
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
- 控制是否重新hash，默认为0，后面会详细说明
transient int hashSeed = 0;
- 内部类，VM启动之后初始化
jdk.map.althashing.threshold
JDK中的参数，默认-1，如果设置为1，则强制使用String类型的新hash算法
private static class Holder {
/**
* Table capacity above which to switch to use alternative hashing.
*/
static final int ALTERNATIVE_HASHING_THRESHOLD;
static {
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;
// disable alternative hashing if -1
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;
}
}
内部结构
从上图可以看出，HashMap是基于数组+链表的方式实现的。来看Entry这个内部类：
- Entry，4个属性（key，value，next节点，hash值）
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
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;
}
public final int hashCode() {
return (key==null ? 0 : key.hashCode()) ^
(value==null ? 0 : value.hashCode());
}
public final String toString() {
return getKey() + "=" + getValue();
}
/**
* This method is invoked whenever the value in an entry is
* overwritten by an invocation of put(k,v) for a key k that's already
* in the HashMap.
*/
void recordAccess(HashMap<K,V> m) {
}
/**
* This method is invoked whenever the entry is
* removed from the table.
*/
void recordRemoval(HashMap<K,V> m) {
}
}
构造函数
- 无参构造函数，默认初始容量16，负载因子0.75
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
- 一个参数构造函数，默认负载因子0.75
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
- 两个参数构造函数，设置容量和负载因子
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;
threshold = initialCapacity;
init();
}
- init方法，模板方法，如果有子类需要扩展可以自行实现
void init() {
}
主要方法
- hash方法
final int hash(Object k) {
int h = hashSeed;
//默认0，如果不是0，并且key是String类型，才使用新的hash算法（避免碰
//撞的优化？）
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
//把高位的值移到低位参与运算，使高位值的变化会影响到hash结果
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
- 根据hash值确定在table中的位置，length为2的倍数 HashMap的扩容是基于2的倍数来扩容的，从这里可以看出，对于indexFor方法而言，其具体实现就是通过一个计算出来的code值和数组长度-1做位运算，那么对于2^N来说，长度减一转换成二进制之后就是全一（长度16，len-1=15,二进制就是1111），所以这种设定的好处就是说，对于计算出来的code值得每一位都会影响到我们索引位置的确定，其目的就是为了能让数据更好的散列到不同的桶中。
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
put方法
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
//如果表没有初始化，则以阈值threshold的容量初始化表
inflateTable(threshold);
}
if (key == null)
//如果key值为null，调用putForNullKey方法，所以hashmap可以插入key和value为null的值
return putForNullKey(value);
//计算key的hash值
int hash = hash(key);
//计算hash值对应表的位置，即表下标
int i = indexFor(hash, table.length);
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))) {
//如果hash值相等并且（key值相等或者key的equals方法相等），
//则覆盖，返回旧的value
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
//修改字数+1
modCount++;
//如果没找到key没找到，则插入
addEntry(hash, key, value, i);
return null;
}
- 初始化表方法， 表容量必须是2的倍数 （roundUpToPowerOf2）
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
- 获取大于或等于给定值的最小的2的倍数
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
- highestOneBit：返回小于给定值的最大的2的倍数
public static int highestOneBit(int i) {
// HD, Figure 3-1
i |= (i >> 1); //其余位不管，把最高位的1覆盖到第二位，使前2位都是1
i |= (i >> 2); //同样的，把第3、4位置1，使前4位都是1
i |= (i >> 4); //...
i |= (i >> 8); //...
i |= (i >> 16); //最高位以及低位都是1
return i - (i >>> 1); //返回最高位为1，其余位全为0的值
}
- initHashSeedAsNeeded方法控制transfer扩容时是否重新hash
final boolean initHashSeedAsNeeded(int capacity) {
//hashSeed默认0，currentAltHashing为false
boolean currentAltHashing = hashSeed != 0;
//参照上面的Holder类的静态块，jdk.map.althashing.threshold默认-1，Holder.ALTERNATIVE_HASHING_THRESHOLD为Integer.MAX_VALUE，如果jdk.map.althashing.threshold设置了其他非负数，可以改变Holder.ALTERNATIVE_HASHING_THRESHOLD的值，如果不超过Integer.MAX_VALUE，则useAltHashing为true
boolean useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean switching = currentAltHashing ^ useAltHashing;
if (switching) { //改变hashSeed的值，使hashSeed!=0，rehash时String类型会使用新hash算法
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
return switching;
}
- HashMap把key为null的key-value键值对放入table[0]中
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
- 插入新的key-value键值对
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length); //如果键值对数量达到了阈值，则扩容
hash = (null != key) ? hash(key) : 0; //null的hash值为0
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
-
头插法，即把新的Entry插入到table[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++;
}
get方法
public V get(Object key) {
if (key == null)
return getForNullKey(); //如果key为null，直接去table[0]中找
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
private V getForNullKey() {
if (size == 0) {
return null;
}
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
- getEntry方法比较简单，先找hash值在表中的位置，再循环链表查找Entry，如果存在，返回Entry，否则返回null
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
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;
}
- remove方法
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
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) //如果相等，说明需要删除的是头节点，头节点直接等于next
table[i] = next;
else
prev.next = next; //如果不是头节点，前一个的next等于下一个节点，删除当前节点
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
resize方法，扩容（重点）
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) { //如果容量已经达到MAXIMUM_CAPACITY，不扩容
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
//initHashSeedAsNeeded方法决定是否重新计算String类型的hash值
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
- transfer方法，把旧表的所有节点转移到新表中
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
/**
*重新计算hash值在新表中的位置（旧表中一条链表中的数据
*最多会分成两条存在新表中，即oldTable[index]中的节点会存到
*newTable[index]和newTable[index+oldTable.length]中）
*/
int i = indexFor(e.hash, newCapacity);
//头插法插入到新表中
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
jdk1.8
1.8的HashMap相比于1.7有了很多变化
- Entry结构变成了Node结构， hash变量加上了final声明 ，即不可以进行rehash了
- 插入节点的方式从 头插法 变成了 尾插法
- 引入了 红黑树
- tableSizeFor方法、hash算法等等
定义
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
成员变量
- 默认初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
- 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
- 默认负载因子 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
- 链表转红黑树的阈值 8
static final int TREEIFY_THRESHOLD = 8;
- 红黑树转链表的阈值 6
static final int UNTREEIFY_THRESHOLD = 6;
- 链表转红黑树所需要的最小表容量64，即当链表的长度达到转红黑树的临界值8的时候，如果表容量小于64，此时并不会把链表转成红黑树，而会对表进行扩容操作，减小链表的长度
static final int MIN_TREEIFY_CAPACITY = 64;
- table，Node数组
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;
- 节点总数
transient int size;
- 修改次数
transient int modCount;
- 扩容阈值
int threshold;
- 负载因子
final float loadFactor;
结构
- Node结构，实现了Entry，hash值声明为final，不再可变，即1.7中的rehash操作不存在了
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
构造函数
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
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);
}
- 参数为Map的构造方法，先计算需要的容量大小，然后调用putVal方法插入节点
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
- tableSizeFor方法，给定初始化表容量值，返回表的实际初始化容量（必须是2的倍数），这个方法相比与1.7有了优化，更简洁。
static final int tableSizeFor(int cap) {
int n = cap - 1; //先进行-1操作，当cap已经是2的倍数时，最后+1，返回该数本身
n |= n >>> 1; //右移1位，再进行或操作，然后赋值给n，使最高位的1的下一位也变成1
n |= n >>> 2; //右移2位，使最高2位的1右移覆盖后2位的值，即最高4位均为1
n |= n >>> 4; //右移4位...
n |= n >>> 8; //右移8位...
n |= n >>> 16; //右移16位...
//如果cap<=0，返回1，如果>MAXIMUM_CAPACITY,返回MAXIMUM_CAPACITY，否则，最后的n+1操作返回大于等于cap的最小的2的倍数
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
主要方法
- hash算法进行了简化，直接把高16位移下来进行或运算
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* onlyIfAbsent 如果是true，不存在才插入，存在则不改变原有的值
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
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为null或者length为0，调用resize扩容方法（没有单独的///初始化方法了）
n = (tab = resize()).length;
//i = (n - 1) & //hash]计算hash值对应表中的位置，如果链表头为null，直接插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//如果key存在，赋值给e，后面统一判断是否插入
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果是树节点，调用putTreeVal方法
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//循环tab[i = (n - 1) & //hash]上的链表，binCount记录链表的长度，用来判断是否转化为树结//构
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {//如果key没找到，直接插入
p.next = newNode(hash, key, value, null);
// -1 for 1st，如果长度达到了8，就转化为树结构
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) {
// key存在，如果onlyIfAbsent为false，替换value，如果onlyIfAbsen//t 为true，原有值为null，也会替换，否则不变更原有值
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); //LinkedHashMap重写使用
return oldValue;
}
}
++modCount; //修改次数+1
if (++size > threshold) //如果size达到了扩容的阈值，则进行扩容操作
resize();
afterNodeInsertion(evict); //LinkedHashMap重写用的
return null;
}
get方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
- getNode方法很简单，(n - 1) & hash计算key值对应的table下标，找到链表，先判断头节点，然后循环查找，如果头节点是树节点，调用树节点的getTreeNode方法
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 && // 先判断第一个节点
((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方法
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
/**
* Implements Map.remove and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to match if matchValue, else ignored
* @param matchValue if true only remove if value is equal //如果是true，value也要相等
* @param movable if false do not move other nodes while removing
* @return the node, or null if none
*/
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {//找到对应的头节点
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 TreeNode) //如果是树，调用树的getTreeNode方法
node = ((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 != null && value.equals(v)))) { //matchValue为true时，value也要相等才删除节点
if (node instanceof TreeNode) //树节点的删除
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p) //如果是头节点，把头节点的下个节点赋值给头节点
tab[index] = node.next;
else //把当前节点的next节点赋值给上一个节点的next（删除当前节点）
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node); //空方法，LinkedHashMap重写用
return node;
}
}
return null;
}
resize方法（扩容）
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) { //如果旧表已经初始化过了
if (oldCap >= MAXIMUM_CAPACITY) { //达到上限，不再扩容
threshold = Integer.MAX_VALUE;
return oldTab;
}
//如果容量大于等于16，并且*2小于上限，扩容2倍，新表容量=旧表*2，新阈值=旧阈值*2
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // 初始化表，有参构造函数中把需要初始化的容量赋值给了threshold
newCap = oldThr;
else { // 如果没有给定容量，默认初始化16，阈值16*0.75=12
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;
/**
* 如果旧表里有值，需要把旧表里的值重新计算放到新表里
* hash & (oldCap*2-1)计算新表中的位置，只可能得到两种结果（把新表分成两个小表）
* hash & (oldCap-1) 放在前面的表里 和 hash & (oldCap-1) + oldCap 放在后面的表里
* hash & oldCap == 0 就是第一种结果， !=0 就是第二种结果
*/
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null) //头节点是null，直接赋值
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode) //树节点处理
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
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;
}
else { //分配到后面表里的放在一个链表里
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) { //放到新表里
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
多线程安全问题
HashMap不是线程安全的
- JDK1.7中 ，当两个线程同时进行插入操作时，同时执行到createEntry方法时，获取到了同一个头节点e，第二个线程会覆盖掉第一个线程的插入操作，使第一个线程插入的数据丢失。 JDK1.8中的尾插法 同样会有这样的问题，两个线程获取到相同的节点，然后把新键值对赋值给这个节点的next，后面的赋值操作覆盖掉前面的。
- JDK1.7和JDK1.8中 对map进行扩容时，由于节点的next会变化，造成实际有key值，但是读操作返回null的情况。
- 1.7中，当两个线程同时进行扩容操作时，可能会造成 链表的死循环 ，形成过程：
- 现在有个map：
- 线程1进行扩容操作，执行transfer方法，赋值完节点e和next之后阻塞了。
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
- 线程2进行扩容操作并完成了扩容，创建了newTable2。
- 此时，节点e和next的连接情况如上图所示，线程1如果继续执行，执行过程如下：
int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e;
e = next; Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; ```java  ```java e = next; Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e;
e = next;
- 此时链表形成了死循环。
- 1.8中的transfer方法有了变化，不会造成死循环。
总结
- HashMap的结构，主要方法
- 1.7和1.8的区别
- 关于红黑树部分后面补充
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
- Scala 中的集合（二）：集合性能比较
- Scala 中的集合（二）：集合性能比较
- 《面试知识，工作可待：集合篇》：Java 集合面试知识大全
- 如何对集合对象求合计，然后追加在该集合对象中
- MongoDB指南---14、特殊的索引和集合：固定集合、TTL索引、全文本索引
- Python 集合相关操作
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
