wen JDK1.7 – HashMap源码解析
目录
- 数据结构
- 成员变量
- 构造方法
- 初始化数组
- 添加元素（put）
- 数组扩容
- 获取元素（get）
- 删除元素（remove）
- modCount
- 并发安全问题
- 总结
数据结构
JDK1.7的HashMap数据结构为数组+链表
成员变量
//默认数组容量为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大数组容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//空数组
static final Entry<?,?>[] EMPTY_TABLE = {};
//存放元素的数组
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
//元素个数
transient int size;
//阈值，数组扩充的条件，阈值 = 数组容量 * 加载因子
int threshold;
//加载因子
final float loadFactor;
//HashMap修改次数
transient int modCount;
//
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
//hash种子，使hash算法更加复杂，让hash值更散列
transient int hashSeed = 0;
//
private transient Set<Map.Entry<K,V>> entrySet = null;
//序列化ID
private static final long serialVersionUID = 362498820763181265L;
构造方法
- 4种构造方法，其中第一个构造方法为重点方法，第二和第三的构造方法本质上为第一种构造方法。
- initialCapacity：初始数组容量（当前的值不一定是数组的真实容量），loadFactor：加载因子
- 前三个构造方法，并未对数组做初始化，它们是对加载因子（loadFactor）和阈值（threshold）进行初始化，此时当前的阈值为指定的数组容量，并不是数组容量 * 加载因子所计算后的值 或者 最大数组容量+1。（因为指定的数组容量不一定是数组的真实容量）
- 数组容量必须为2的n次幂，需要通过计算后得出
- 在第一次添加元素时开始初始化数组
/*
有参构造方法 -- 重点
initialCapacity：初始数组容量
loadFactor：加载因子
*/
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();
}
/*
有参构造方法
initialCapacity：初始数组容量
*/
public HashMap(int initialCapacity) {
//调用两个参数的构造器，初始数组容量指定，加载因子默认
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/*
无参构造方法
*/
public HashMap() {
//调用两个参数的构造器，初始数组容量默认，加载因子默认
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
/*
有参构造方法
m：Map对象
*/
public HashMap(Map<? extends K, ? extends V> m) {
/*
(m.size() / DEFAULT_LOAD_FACTOR) + 1
-- (m.size() / DEFAULT_LOAD_FACTOR)取到m中的数组容量
-- +1的操作是为了减少扩容的次数，假如计算出的数组容量正好为16时，
则添加一个新的元素很可能产生扩容操作（考虑扩容的2个必要条件）。
如果提前把计算出的数组容量+1，则添加一个新的元素产生扩容操作的可能性将降低
*/
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);
//将map中的元素移动到HashMap中
putAllForCreate(m);
}
初始化数组
-
在第一次添加元素时，对数组进行初始化
-
阈值(threshold)的值为数组容量 * 加载因子 或 最大数组容量 + 1，两者之间取最小值，通常为数组容量 * 加载因子
-
获取到真正的数组容量
-
Integer.highestOneBit(number)用来计算最大2的n次幂小于或等于number
-
Integer.highestOneBit((number – 1) << 1)中的(number – 1) << 1,
-
减一操作：当number正好为2的n次幂时，如不减一操作向左移一位，通过highestOneBit()计算后结果值会偏大
例如number = 16，number << 1 = 32，通过highestOneBit()计算后结果为32，预期值为16
-
左移一位操作：当number小于2的n次幂时，如不左移一位操作，通过highestOneBit()计算后结果值会偏小
例如number = 15，number – 1 = 14 ，通过highestOneBit()计算后结果为8，预期值为16
-
计算hashSeed(hash种子)，当数组容量大于或等于Integer.MAX_VALUE时，hashSeed才有可能会改变
/*
toSize -- 传入的数组容量
*/
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
/*
计算真正的数组容量，即最小2的n次幂大于或等于toSize
例如 toSize = 15,计算后的结果为16
*/
int capacity = roundUpToPowerOf2(toSize);
//计算阈值，此时阈值为数组容量 * 加载因子 或者 最大数组容量+1
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
//初始化数组
table = new Entry[capacity];
//计算hash种子
initHashSeedAsNeeded(capacity);
}
- 计算最小2的n次幂大于或等于number
private static int roundUpToPowerOf2(int number) {
/*
1.当number大于最大数组容量时，返回最大数组容量
2.number大于1时，返回最小2的n次幂大于或等于number
3.number小于或等于1时，返回1
*/
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
- 计算最大2的n次幂小于或等于i
/*
计算最大2的n次幂小于或等于i
例如 i = 17,计算后的结果为16
通过一次次的右移，将低位（相对）的0或1都变成1
例如：
初始数值：0010 0010 (34)
最后结果：0011 1111 (63)
返回：
i - (i >>> 1) -- 取2的n次幂
0011 1111 - 0001 1111 = 0010 0000 (63 - 31 = 32)
*/
public static int highestOneBit(int i) {
// HD, Figure 3-1
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
return i - (i >>> 1);
}
- 计算hash种子
/*
Holder.ALTERNATIVE_HASHING_THRESHOLD：
1.如果vm启动参数jdk.map.althashing.threshold存在值
则ALTERNATIVE_HASHING_THRESHOLD为该值，否则为Integer.MAX_VALUE;
2.如果jdk.map.althashing.threshold的值为-1，
则ALTERNATIVE_HASHING_THRESHOLD的值也为Integer.MAX_VALUE;
3.如果jdk.map.althashing.threshold的值 < 0,则报异常
hashSeed默认值为0
sun.misc.VM.isBooted()默认值为false，在vm启动时变成true
*/
final boolean initHashSeedAsNeeded(int capacity) {
//如果hashSeed不为0则为true，否则为false
boolean currentAltHashing = hashSeed != 0;
/*
sun.misc.VM.isBooted() 假定永真
判断数组容量是否大于或等于Holder.ALTERNATIVE_HASHING_THRESHOLD
*/
boolean useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
//异或操作，currentAltHashing初始为false，只有useAltHashing为true时，hashSeed才会发生改变
boolean switching = currentAltHashing ^ useAltHashing;
if (switching) {
//重新生成hashSeed
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
return switching;
}
ALTERNATIVE_HASHING_THRESHOLD初始化过程
/**
* 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 {
/*
1.如果vm启动参数jdk.map.althashing.threshold存在值
则ALTERNATIVE_HASHING_THRESHOLD为该值，否则为Integer.MAX_VALUE;
*/
threshold = (null != altThreshold)
? Integer.parseInt(altThreshold)
: ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;
/*
此时threshold的值只能为jdk.map.althashing.threshold
2.如果jdk.map.althashing.threshold的值为-1，
则ALTERNATIVE_HASHING_THRESHOLD的值也为Integer.MAX_VALUE;
*/
if (threshold == -1) {
threshold = Integer.MAX_VALUE;
}
//如果jdk.map.althashing.threshold的值 < 0,则报异常
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
ALTERNATIVE_HASHING_THRESHOLD = threshold;
}
添加元素(put)
-
在第一次添加元素时，会初始化数组，因为table == EMPTY_TABLE，此时table会被初始化
-
允许添加key为null的键值对
-
当key为null时，存储的数组下标为0
-
计算key的hash时，会判断hashSeed是否有更改过以及key的类型是否为String（通常为false），如果为true，则
return sun.misc.Hashing.stringHash32((String) k);,否则获取h ^= k.hashCode(); -
在计算key的hash时，会有一堆的异或操作，这是为了尽可能的避免哈希冲突，因为在获取hash值的时候可能会获取到一致的值从而造成哈希冲突（哈希冲突是无法解决的，只能尽可能的去避免哈希冲突）
-
如果存在key，则会新值会覆盖旧值，如果不存在key，则以头插法的方式添加
public V put(K key, V value) {
//初始化数组
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//存放key为null的键值对
if (key == null)
return putForNullKey(value);
//计算hash值
int hash = hash(key);
//计算数组下标
int i = indexFor(hash, table.length);
//根据计算得出的数组下标所在的数组，遍历其中的链表，判断是否有相同的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;
//这个方法在hashmap中是个装饰（无实际意义），而在linkHashMap有实际意义
e.recordAccess(this);
return oldValue;
}
}
//hashmap修改次数，因为不含有相同的key，意味着需要添加新的键值对，则需要修改hashmap
modCount++;
//添加新的键值对
addEntry(hash, key, value, i);
return null;
}
- 添加key为null的键值对
private V putForNullKey(V value) {
//根据数组下标为0所在的数组，遍历其中的链表，判断是否有key为null
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;
}
}
//hashmap修改次数，因为不存在key为null的键值对，需要添加新的键值对
modCount++;
//添加新的键值对
addEntry(0, null, value, 0);
return null;
}
- 计算hash值
// k -- 传入key
final int hash(Object k) {
int h = hashSeed;
//判断hashSeed是否有更改过以及key的类型是否为String，返回的结果是让hash值更加散列
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
//hash种子和key.hashCode()进行异或操作
h ^= k.hashCode();
/*
一系列的或操作是为了尽可能的避免哈希冲突，因为在获取hash值的时候可能会获取到一致的值从而造成哈希冲突
*/
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
- 计算数组下标
/*
h -- hash,length -- 数组容量
数组下标要满足的条件：
1.要在数组容量范围内，如数组容量16，则其范围为0~15
2.计算的数组下标要随机且均衡，如果不均衡，则会可能产生某一个链表中长度过长，对元素的增删改查的效率降低
*/
static int indexFor(int h, int length) {
/*
为什么这里不用取余操作，用的是与操作呢？
1.与操作的效率不取余操作高
2.由于length的特性行（2的n次幂），h & (length-1)相当于取余操作
h为key的hash值，length为数组容量
假如length为16，则length - 1 = 15，二进制位 0000 1111
假如h的二进制位0010 1001（随机，任意数值），
0010 1001 & 0000 1111 = 0000 1001(9)
假如h的二进制位0101 1101（随机，任意数值），
0101 1101 & 0000 1111 = 0000 1101(13)
此时会发现h无论是什么，跟length - 1进行与操作结果都会在数组容量范围内，
因为length - 1决定了取值范围，h决定了最终值
*/
return h & (length-1);
}
- 添加元素
void addEntry(int hash, K key, V value, int bucketIndex) {
/*
判断数组是否需要扩容
扩容条件：元素个数大于或等于阈值 并且 当前数组下标的数组不为null
*/
if ((size >= threshold) && (null != table[bucketIndex])) {
//数组扩容 -- 新数组容量为原来数组容量的2倍
resize(2 * table.length);
//重新计算hash -- 因为扩容后有可能会改变hash种子(hashSeed)
hash = (null != key) ? hash(key) : 0;
//计算新的数组下标 -- 扩容后数组下标可能发生变化
bucketIndex = indexFor(hash, table.length);
}
//创建节点
createEntry(hash, key, value, bucketIndex);
}
- 创建元素节点
/*
Entry为元素对象
hash -- 元素的hash
key -- 元素的key
value -- 元素的value
e -- 下一个元素对象
*/
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++;
}
数组扩容
-
扩容条件：元素个数大于或等于阈值 并且 当前数组下标的数组不为null
-
扩容后，新数组容量为原来的2倍
-
扩容后，链表中的元素顺序由正序变成反序，如正序为1，2，3；扩容后为3，2，1；
-
在多线程环境中，HashMap扩容有可能会产生循环链表，在添加元素时，会造成死循环，因为在添加元素之前会遍历key是否存在
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);
}
- 元素转移
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;
//判断是否需要rahash，通常是不需要的，达成条件困难
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
/*
1.重新计算数组下标，在扩容后，数组下标可能会改变或不改变
2.数组下标不改变则为原来的值
3.数组下标改变则为原来的值 + 旧数组容量
4.如原来数组容量为16，原来的数组下标值为2，
则计算出新的数组下标只可能是2或则18这两种可能性
*/
int i = indexFor(e.hash, newCapacity);
//链表操作
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
获取元素（get）
- 判断key是否为null，如果是则调用
getForNullKey(),否则调用getEntry(key) - key == null,遍历数组下标为0的链表
- key != null,计算所在的数组下标后，遍历链表
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
- 获取key == null的键值对
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;
}
- 获取key != 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）
- 计算key的hash值
- 计算数组下标
- 遍历链表，若key存在则删除，不存在返回null
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)))) {
//key存在，意味着需要修改hashmap
modCount++;
size--;
//删除元素
if (prev == e)
table[i] = next;
else
prev.next = next;
//在hashmap中无实际意义
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
modCount
- fast-fail快速失败容错机制
- 在进行迭代时，首先
expectedModCount = modCount;,如果途中有修改modcount的操作，如删除指定元素就会报异常，因为modCount已经改变，而expectedModCount没有改变
private abstract class HashIterator<E> implements Iterator<E> {
Entry<K,V> next; // next entry to return
int expectedModCount; // For fast-fail
int index; // current slot
Entry<K,V> current; // current entry
HashIterator() {
//获得modCount值
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
}
public final boolean hasNext() {
return next != null;
}
final Entry<K,V> nextEntry() {
//如果发现modCount != expectedModCount则会报异常
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值
expectedModCount = modCount;
}
}
-
在遍历hashmap时，使用删除
hashMap.remove(key);指定元素会报
java.util.ConcurrentModificationException异常，因为此时expectedcount != modcount
public class Test {
public static void main(String[] args) {
HashMap hashMap = new HashMap();
hashMap.put("1", "2");
hashMap.put("2", "4");
Iterator iterator = hashMap.keySet().iterator();
while (iterator.hasNext()) {
String key = (String) iterator.next();
if (key.equals("1")) {
//删除指定元素
hashMap.remove(key);
}
}
}
}
/*
异常信息
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.HashMap$HashIterator.nextNode(HashMap.java:1445)
at java.util.HashMap$KeyIterator.next(HashMap.java:1469)
at com.xu.test.Test.main(Test.java:13)
Process finished with exit code 1
*/
- 在遍历hashmap时，使用
iterator.remove();删除指定元素则不会报异常，因为在迭代器中的remove()方法会修正expectedcount，使得expectedcount再次与modcount相等
public class Test {
public static void main(String[] args) {
HashMap hashMap = new HashMap();
hashMap.put("1", "2");
hashMap.put("2", "4");
Iterator iterator = hashMap.keySet().iterator();
while (iterator.hasNext()) {
String key = (String) iterator.next();
if (key.equals("1")) {
//删除指定元素
iterator.remove();
}
}
}
}
并发安全问题
HashMap（JDk1.7）在多线程并发下是不安全的，如两个线程同时对hashmap进行扩容操作，此时可能会造成循环链表，从而产生死循环
解决方法：
1.明确元素的个数，在创建HashMap时设置特定的数组容量和加载因子，保证HashMap不会进行扩容（不推荐，一般无法明确元素个数）
2.使用HashTable，因为HashTable加了锁，如在put()方法等使用 synchronized 关键字，保证了并发安全（不推荐，效率低）
3.使用ConcurrentHashMap，采用了分段锁机制，即保证并发安全同时效率高（推荐）
总结
-
JDK1.7中HashMap的数据结构为数组+链表，
-
有四种构造方法，第一种是指定数组容量和加载因子的有参构造方法（指定数组容量，指定加载因子意指为该构造方法的参数），第二种是指定数组容量的有参构造方法，第三种是无参构造方法，第四种是指定Map对象参数的有参构造方法（其中第二种和第三种都是调用第一种构造方法）
-
在创建对象时，如果没有指定数组容量和加载因子，则会使用默认的数组容量和默认的加载因子，默认数组容量为16，默认加载因子为0.75
-
HashMap是懒加载机制，在创建对象时，并没有初始化数组，而是初始化阈值和加载因子，此时阈值为指定数组容量，数组在第一次put()时做初始化操作
-
为了保证数组容量为2的n次幂，需要对指定的数组容量进行加工，Integer.highestOneBit(number)用来计算最大2的n次幂小于或等于number。其中number为（指定数组容量 – 1）<< 1。
说明：如果指定数组容量不减一直接进行右移操作，则指定数组容量不为2的n次幂时，计算后结果是符合，但指定数组容量为2的n次幂时，计算后结果是偏大值，所以减一操作是为了防止指定数组容量为2的n次幂，而对于指定数组容量不为2的n次幂再减一对计算后的结果不会造成影响，如15，14，13进行右移操作后结果一致为16
-
在数组初始化时，阈值真正初始化；数组的类型为Entry[]，其中Entry对象有hash，key，value，next属性；计算hashSeed，而hashSeed的作用是使hash算法更加复杂，让hash值更加散列
-
hashSeed默认值为0，改变hashSeed的条件是
boolean switching = currentAltHashing ^ useAltHashing;当switching为true时，hashSeed将会改变值 -
在添加元素时，允许key为null的键值对，其存储的数组下标为0，添加元素的流程：首先根据数组下标遍历链表，如果发现存在对应的key则会更改value，否则进行创建新节点操作，在创建新节点之前，先判断是否需要扩容，接着才是创建新节点，添加新节点采用的是头插法
-
扩容有两个必要条件，其一为当前元素数量大于或等于阈值，其二为当前的数组下标存在Entry对象，如果进行扩容，则新的数组容量 = 旧的数组容量 * 2；在
transfer()方法中实现了旧数组中的元素转移到新数组的操作，**其中涉及了元素是否需要rehash，而这个rehash又与hashSeed有关，一旦hashSeed改变，则元素需要rehash，否则不需要。；**然后就是元素存储的数组下标，因为数组容量为2的n次幂，所以计算出的数组下标只有两种可能，其一为原数组下标，不改变；其二为新数组下标 = 原数组下标 + 旧数组容量； -
扩容后会产生一个问题，即链表中元素的顺序由正序变成反序；在多线程并发下，扩容操作可能会产生循环链表，进一步造成死循环。
解决方法：
1.明确元素的个数，在创建HashMap时设置特定的数组容量和加载因子，保证HashMap不会进行扩容（不推荐，一般无法明确元素个数）
2.使用HashTable，因为HashTable加了锁，如在put()方法等使用 synchronized 关键字，保证了并发安全（不推荐，效率低）
3.使用ConcurrentHashMap，采用了分段锁机制，即保证并发安全同时效率高（推荐）
-
modCount说明：fast-fail快速失败容错机制，其值为HashMap的修改次数，如put()，remove()方法。
