Java集合类源码之Map——HashMap
2017-03-01 本文已影响161人
丁木木木木木
主要内容：
- HashMap数据结构
- 继承关系、关键属性、构造函数
- 插入元素
- 计算散列码
- 查找元素
- 扩容
- fail-fast机制
HashMap概述
- 基于哈希表的Map接口的实现，以Key-Value键值对的形式存储数据，key和value都允许null值。
- 非线程安全，创建线程安全的HashMap可以使用
Collections.synchronizedMap。
Map map = Collections.synchronizedMap(new HashMap());
HashMap数据结构
HashMap的底层基于数组和链表实现。由Entry<K,V>类型的数组存储数据，而Entry是HashMap 的内部类，实现了Map的Entry接口，定义了键key、值value、哈希值hash以及指向下一个节点的指针next。
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();
}
//当向HashMap增加元素时回调这个方法
void recordAccess(HashMap<K,V> m) {
}
//当HashMap删除元素时回调这个方法
void recordRemoval(HashMap<K,V> m) {
}
}
为什么？像ArrayList和LinkedList查询数据，需要遍历数组。而HashMap采用hash算法将key键值映射成散列码，由散列码来决定存储的位置，对应到数组的下标。但是问题来了，hash算法算出来的散列码可能相同，即hash冲突。为了解决这个问题，HashMap采用链表的形式，将相同散列值的元素存储在一个链表中。
源码分析
继承关系
HashMap继承关系.png
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
- 继承AbstractMap抽象类，实现Map接口
- 实现java.io.Serialization接口，支持序列化
- 实现Cloneable接口，支持对象克隆，浅复制
关键属性
//默认初始值16，必须是2的n次方？？？
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量为2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//空数组
static final Entry<?,?>[] EMPTY_TABLE = {};
//Entry类型的数组，以键值对形式存储
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
//已存储元素的个数
transient int size;
//下次扩容的临界值，size>=threshold时会进行扩容，threshold=capacity * loadFactor
int threshold;
//加载因子
final float loadFactor;
//被修改的次数，实现fail fast机制
transient int modCount;
loadFactor表示HashMap中元素填满的程度。加载因子越大，说明数组中占的坑越多，冲突也就越多，查找效率降低；反之的话，冲突减少，查询效率提高，但是空间占用率也降低了。
构造函数
//使用指定的扩容临界值threshold以及加载因子loadFactory构造空HashMap
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();//未实现，供子类来实现
}
//使用指定threshold和默认加载因子构造空的HashMap
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//使用默认初始容量threshold和默认加载因子构造空的HashMap
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
//构造一个指定map的HashMap，使用默认加载因子
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);//获取初始容量以及threshold，并初始化数组
putAllForCreate(m);
}
插入
根据key值计算hash值，然后计算出对应在数组中的位置。如果数组在该位置上有元素的话，这个位置上的元素将以链表的形式存在，新创建的Entry放在链表头部，如果查找到相同键值的元素，用新值代替旧值并返回旧值。如果数组这个位置上没有元素的话，直接将元素放在放在该位置上。
public V put(K key, V value) {
if (table == EMPTY_TABLE) {//若为空数组，初始化数组
inflateTable(threshold);
}
if (key == null)//若key为null值
return putForNullKey(value);
int hash = hash(key);//若key不是null值，计算hash值
int i = indexFor(hash, table.length);//得出hash对应数组中的位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) {//对数组i位置上的元素进行遍历
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;
}
}
modCount++;//修改次数加1
addEntry(hash, key, value, i);//将键值对加入到数组索引为i的位置上
return null;
}
- 如果数组是空数组的话，调用
inflateTable(int toSize)进行数组初始化。根据传入的threshold计算一个大于它的最小的2的n次方的初始容量，并初始化数组。
private void inflateTable(int toSize) {
//得到一个大于toSize的最小的2的n次幂，作为初始容量
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
创建节点
介绍几个创建Entry的方法。
-
putForNullKey(V value)：如果键值是null值，hash值是0，对象存储在数组索引为0的位置上，即table[0]。
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {//如果存在key为null的键值对存在的话覆盖旧值
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);//不存在key为null的键值对，新建
return null;
}
-
addEntry(int hash, K key, V value, int bucketIndex)：根据计算出的hash值、key-value放在数组bucketIndex的位置处。
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {//长度大于临界值threshold
resize(2 * table.length);//数组长度扩充到原来的2倍
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处的Entry
table[bucketIndex] = new Entry<>(hash, key, value, e);//将新建的Entry放在数组bucketIndex位置处，并让它指向旧的Entry
size++;
}
计算散列码
put方法中重要的还有计算hash值以及计算对应到数组索引的方法。
-
hash(Object k)：根据key键值的hashCode计算hash值。看不太懂！！！！
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
-
indexFor(int h, int length)：根据hash值和数组长度计算索引。h&(length-1)相当于h%length取模运算，length为2的n次方时，length-1得到的二进制数每位上值都为1，&运算后值不变。保证了散列的均匀性，也提高了效率。这是为什么HashMap容量必须是2的n次幂的原因。
static int indexFor(int h, int length) {
return h & (length-1);
}
查找
对key为null值进行特殊处理，在table[0]位置处查找key为null的元素对应的值；否则的话根据key值计算出hash，并得出对应数组上的位置index，遍历table[index]上的链表比较key值。
public V get(Object key) {
if (key == null)//key为null，查找对应的值
return getForNullKey();
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) {//table[0]处查找
if (e.key == null)
return e.value;
}
return null;
}
扩容
当HashMap中元素越来越多时，hash冲突也越明显，为了提高查询速度，需要扩容数组的长度。resize(int newCapacity)在addEntry(int hash, K key, V value, int bucketIndex)添加新元素方法中调用。数组大小扩大一倍，然后重新计算每个元素在数组中的位置，非常耗性能。所以如果提前知道HashMap的容量，构造HashMap的时候传入初始容量。
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;
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;
}
}
}
fail-fast机制
- 概念：多个线程对同一集合的对象进行修改时，会产生fail-fast，只能用来检测错误。
- 例子：因为HashMap非线程安全，如果在使用迭代器的过程中对HashMap进行了修改(涉及到修改元素的个数)，会抛出
ConcurrentModificationException异常。 - 实现：主要通过
modCount来实现这个机制，每次对HashMap进行修改都会增加这个值。迭代器初始化时将这个值赋值给expectedModCount，遍历和删除元素时都会将两者进行比较，不同则抛出异常，快速失败。
