一、参数说明
//HashMap初始容量16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// HashMap最大容量，必须为2的幂 （默认:1 << 30）
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认装载因子0.75f （默认:0.75f）
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//hash表为空情况
static final Entry<?,?>[] EMPTY_TABLE = {};
//hash表
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
// HashMap长度
transient int size;
//临界值 当HashMap中元素超过这个值，会触发HashMap扩容
int threshold;
//hash表装载因子
final float loadFactor;
//记录HashMap的修改次数 put()和get() 等方法会进行++操作
transient int modCount;
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
//jdk1.8已经移除
transient int hashSeed = 0;
二、内部类说明
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
//这里相当于把新插入的数据插入链表头部
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 Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}
public final String toString() {
return getKey() + "=" + getValue();
}
void recordAccess(HashMap<K,V> m) {
}
void recordRemoval(HashMap<K,V> m) {
}
}
三、方法
1、put()方法
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
//初始化表
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//如果hash值相同 key也相同就覆盖
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
//添加新的数据
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;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, 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++;
}
2、resize()方法
// 扩容方法 newCapacity 新的hash表长度
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
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);
}
//重新计算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;
if (switching) {
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
return switching;
}
//在新的hash表中转移旧的数据
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;
//重新计算hash值
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
//链表中数据倒序
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
3、get()方法
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
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;
}
三、死循环问题
众所周知，HashMap是线程不安全的，JDK1.7中HashMap扩容时会导致死循环问题，这里我们看下
假设扩容前 HahsMap结构如下，并且不需要重新移动hash位置
image.png
假设有线程t1和t2，t1和t2同时创建扩容的数组，t1快速完成了扩容表以及元素迁移，
但是还未进行table = newTable这一步骤,t2执行刚进入循环链表,执行到
Entry<K,V> next = e.next这句（此时e 指向c ，next= e.next指向b）
t1结构如下
image.png
然后t2开始迁移链表元素,t2初始结构如下
image.png
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
//重新计算hash值
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
//链表中数据倒序
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
执行第一遍for循环
next = b;
e.next = newTable[i];
newTable[i] = c;
e = next =b;
t1、t2结构如下
image.png
继续第二次循环
next = b.next = c （因为t1已经完成链表倒序 b的next指向c）;
e.next = c;
newTable[i] = b;
e = next =c ;
t1、t2结构如下
image.png
继续第三次循环
next = c.next = null
e.next = newTable[i] = b; (这一点很重要，相当于c的next又指向了b)
newTable[i] = c;
e = null ;
因为e为null，所以循环结束 最终链表结构如下
image.png
假设我们在扩容之后进行get请求，并且这个请求get的key最终计算落到桶1，并且这个key不存在链表中，就会在b和c之间无限循环，导致系统崩溃。
其实这个问题就是典型的单向链表死循环问题，如果我们把链表末尾节点的next指向其他节点，就会造成无限循环情况。
内容参考 https://www.jianshu.com/p/1e9cf0ac07f4
网友评论