Java 容器KV（一）- HashMap(1.7版本)
2019-08-22 本文已影响0人
贪睡的企鹅
1 概述
HashMap 是 Java Collection Framework的重要成员，也是Map接口最常用的实现类，其存储结构对应为数据结构-散列表，也被称为哈希表存储。
2 散列表
散列表的英文叫“Hash Table”，我们平时也叫它“哈希表”或者“Hash 表”，散列表用的就是数组支持按照下标随机访问的时候，时间复杂度是 O(1) 的特性。我们通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置
image
2.1 散列冲突（Hash冲突）
再好的散列函数也无法避免散列冲突。那究竟该如何解决散列冲突问题呢？我们常用的散列冲突解决方法有两类，开放寻址法（open addressing）和链表法（chaining）
2.1.1 开放寻址法
开放寻址法的核心思想是，如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入
image
从图中可以看出，散列表的大小为 10，在元素 x 插入散列表之前，已经 6 个元素插入到散列表中。x 经过 Hash 算法之后，被散列到位置下标为 7 的位置，但是这个位置已经有数据了，所以就产生了冲突。于是我们就顺序地往后一个一个找，看有没有空闲的位置，遍历到尾部都没有找到空闲的位置，于是我们再从表头开始找，直到找到空闲位置 2，于是将其插入到这个位置。
2.1.2 链表法
在散列表中，每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。
image
当插入的时候，我们只需要通过散列函数计算出对应的散列槽位，将其插入到对应链表中即可，所以插入的时间复杂度是 O(1)。当查找、删除一个元素时，我们同样通过散列函数计算出对应的槽，然后遍历链表查找或者删除。
3 HashMap存储结构
HashMap链表法使用链表法来存储数据
image
HashMap使用Entry<K,V>[]来表示哈希表。
/**
* 哈希表，存储数据类型为Entry，长度必须始终是2的幂。
*/
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
Entry类定义
static class Entry<K,V> implements Map.Entry<K,V> {
final K key; // 键值对的键
V value; // 键值对的值
Entry<K,V> next; // 下一个节点
final int hash; // hash(key.hashCode())方法的返回值
Entry(int h, K k, V v, Entry<K,V> n) { // Entry 的构造函数
value = v;
next = n;
key = k;
hash = h;
}
/**
* 添加时调用，作为子类模板方法
*/
void recordAccess(HashMap<K,V> m) {
}
/**
* 删除时调用，作为子类模板方法
*/
void recordRemoval(HashMap<K,V> m) {
}
...省略代码
}
5 HashMap内部核心属性
/**
* 默认的初始容量为16
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 最大的容量为2的30次方
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默认的装载因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 空的哈希表
*/
static final Entry<?,?>[] EMPTY_TABLE = {};
/**
* 哈希表（桶），存储数据类型为Entry，长度必须始终是2的幂。
*/
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
/**
* Map中存储Entry数量
*/
transient int size;
/**
* 进行下一次扩容Entry结构数组元素的数量的阀值 计算公式=(capacity * loadFactor).
* 扩容阀值
*/
int threshold;
/**
* 装载因子
*/
final float loadFactor;
/**
* 数据修改次数
*/
transient int modCount;
4 HashMap构造函数
在JDK1.7中HashMap构造函数中并不会构建哈希表，其动作会放在第一次put动作时创建。
/**
* 用指定的初始容量和默认装载因子实例化一个空的哈希表
* @param initialCapacity 初始值
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 用默认初始容量,默认装载因子实例化一个空的哈希表
*/
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
/**
* 用指定的初始容量,装载因子实例化一个空的哈希表
* @param initialCapacity 初始值
* @param 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);
/** 设置装载因子（默认0.75f） **/
this.loadFactor = loadFactor;
/** 设置扩容阀值 **/
threshold = initialCapacity;
/** jdk1.7中hashMap的init方法是空实现，并没有创建存储Entry结构数组**/
init();
}
/**
* 子类实现模板方法
*/
void init() {
}
5 向Map添加一个key-value
向Map添加一个key-value,如果key存在返回于Map中，则会覆盖value并返回原始值。
-
1 第一次put时哈希表并为创建,调用inflateTable(threshold)构建哈希表
-
2 如果添加key为null，调用putForNullKey处理，放入哈希表数组table[0]位置
-
3 计算key hash值，并计算hash对应哈希表桶位置i。
-
4 判断table[i]是否存在元素Entry，如果存在则从Entry开始，作为链表的头部元素，向后遍历查找key&hash相同元素Entry(用来表示插入的key-value以存在于Map中）如果找到则覆盖Entry.value，并调用Entry对象recordAccess，返回原始值
-
5 创建一个Entry，next指向的原始table[bucketIndex]，存储到哈希表table[bucketIndex]指定下标位置,作为链表的新头部元素
/**
* 向Map添加一个key-value结构,如果key存在返回于Map中，会覆盖value返回原始值
*/
public V put(K key, V value) {
/** 1 第一次put时哈希表并为创建,调用inflateTable(threshold)构建哈希表 **/
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
/** 2 如果添加key为null，调用putForNullKey处理，放入哈希表数组table[0]位置 **/
if (key == null)
return putForNullKey(value);
/** 3 计算key hash值，并计算hash值映射哈希表下标位置。 **/
int hash = hash(key);
int i = indexFor(hash, table.length);
/**
* 4 判断table[i]是否存在元素Entry，如果存在则从Entry开始，作为链表的头部元素，
* 向后遍历查找key&hash相同元素Entry(用来表示插入的key-value以存在于Map中）
* 如果找到则覆盖Entry.value，并调用recordAccess，返回原始值
*/
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;
}
}
/** 修改次数+1 **/
modCount++;
/**
* 5 创建一个Entry，next指向的原始table[bucketIndex]，存储到哈希表table[bucketIndex]指定下标位置,作为链表的新头部元素
* 该方法支持扩容 **/
addEntry(hash, key, value, i);
return null;
}
static class Entry<K,V> implements Map.Entry<K,V> {
/**
* 添加时调用，作为子类模板方法
*/
void recordAccess(HashMap<K,V> m) {
}
5.1 构建哈希表
private void inflateTable(int toSize) {
/** 用来返回大于等于最接近toSize的2的冪数 **/
int capacity = roundUpToPowerOf2(toSize);
/** 设置扩容阀值 **/
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
/** 构建哈希表 **/
table = new Entry[capacity];
/** 初始化哈希掩码值。我们推迟初始化，直到真正需要它。**/
initHashSeedAsNeeded(capacity);
}
/**
* 用来返回大于等于最接近number的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;
}
/**
* 初始化哈希掩码值。我们推迟初始化，直到真正需要它。
*/
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;
}
5.2 向Map添加一个key-value(key为Null)
将key为null键值放入放入哈希表数组table[0]位置
/**
* 将key为null键值放入放入哈希表数组table[0]位置
*/
private V putForNullKey(V value) {
/**
* 判断table[0]是否存在元素Entry，
* 如果存在则从Entry开始，作为链表的头部元素，向后遍历查找key=null元素Entry(用来表示插入的key-value以存在于Map中).
* 如果找到则覆盖Entry.value,并返回原始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;
}
}
/** 修改次数+1 **/
modCount++;
/** 创建一个Entry，next指向的原始table[bucketIndex]，存储到哈希表table[bucketIndex]指定下标位置,作为链表的新头部元素
* 该方法支持扩容 **/
addEntry(0, null, value, 0);
return null;
}
4.3 addEntry
addEntry可以清楚地了解到 链的产生时机。HashMap 总是将新的Entry对象添加到bucketIndex处，若bucketIndex处已经有了Entry对象，那么新添加的Entry对象将指向原有的Entry对象，并形成一条新的以它为链头的Entry链；但是，若bucketIndex处原先没有Entry对象，那么新添加的Entry对象将指向 null，也就生成了一条长度为 1 的全新的Entry链了。HashMap 永远都是在链表的表头添加新元素。此外，若HashMap中元素的个数超过极限值 threshold，其将进行扩容操作，一般情况下，容量将扩大至原来的两倍
/**
* 创建一个Entry，next指向的原始table[bucketIndex]，存储到哈希表table[bucketIndex]指定下标位置,作为链表的新头部元素
* 该方法支持扩容
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
/** 判断是否进行扩容 **/
if ((size >= threshold) && (null != table[bucketIndex])) {
/** 扩容处理 **/
resize(2 * table.length);
/** 重新计算key hash值 **/
hash = (null != key) ? hash(key) : 0;
/** 计算hash值映射哈希表下标位置**/
bucketIndex = indexFor(hash, table.length);
}
/** 创建一个Entry，next指向的原始table[bucketIndex]，存储到table[bucketIndex]位置，作为链表的新头部元素**/
createEntry(hash, key, value, bucketIndex);
}
/**
* 创建一个Entry，next指向的原始table[bucketIndex]，存储到table[bucketIndex]位置，作为链表的新头部元素
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
/** 获取原始table[bucketIndex]**/
Entry<K,V> e = table[bucketIndex];
/** 创建一个Entry，next指向的原始table[bucketIndex]，存储到table[bucketIndex]位置，作为链表的新头部元素**/
table[bucketIndex] = new Entry<>(hash, key, value, e);
/** 数量+1 **/
size++;
}
4.4 扩容
随着HashMap中元素的数量越来越多，发生碰撞的概率将越来越大，所产生的子链长度就会越来越长，这样势必会影响HashMap的存取速度。为了保证HashMap的效率，系统必须要在某个临界点进行扩容处理，该临界点就是HashMap中元素的数量在数值上等于threshold（table数组长度*加载因子）。但是，不得不说，扩容是一个非常耗时的过程，因为它需要重新计算这些元素在新table数组中的位置并进行复制处理。所以，如果我们能够提前预知HashMap 中元素的个数，那么在构造HashMap时预设元素的个数能够有效的提高HashMap的性能。
/**
* 扩容
*/
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
/** 创建2倍大小的新数组 **/
Entry[] newTable = new Entry[newCapacity];
/** 将旧数组的链表转移到新数组，就是这个方法导致的hashMap不安全 **/
transfer(newTable, initHashSeedAsNeeded(newCapacity));
/** 设置新的Entry数组**/
table = newTable;
/** 重新计算扩容阀值**/
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
/**
* 将旧数组的链表转移到新数组，就是这个方法导致的hashMap不安全
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
/** 遍历原始table中所有Entry **/
for (Entry<K,V> e : table) {
/** 遍历table数组中每一个Entry对应的链表中所有Entry **/
while(null != e) {
Entry<K,V> next = e.next;
/** 是否重新计算hash **/
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
/** 计算hash值映射哈希表下标位置 **/
int i = indexFor(e.hash, newCapacity);
/** 将当前Entry.next指向的原始table[i]，存储到table[i]位置,作为链表的新头部元素**/
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
小结
image
6 向Map删除指定的key
1 从Map获取删除指定的key对应Entry，并将Entry从哈希表中剔除
2 调用Entry.recordRemoval,这里是空实现，可以给子类扩展
/**
* 从Map删除指定的key
*/
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
/**
* 从Map获取删除指定的key对应Entry，并将Entry从存储结构中剔除
*/
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
/** 计算key hash值 **/
int hash = (key == null) ? 0 : hash(key);
/** 计算hash值映射哈希表下标位置 **/
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
/** 从Map获取删除指定的key对应Entry，并将Entry从哈希表中剔除,并调用e.recordRemoval **/
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;
}
static class Entry<K,V> implements Map.Entry<K,V> {
/**
* 删除时调用，作为子类模板方法
*/
void recordRemoval(HashMap<K,V> m) {
}
7 获取Map中key对应值value
HashMa读取就显得比较。只需通过key的hash值定位到哈希表下标位置，然后查找并返回该key对应的value即可
针对键为NULL的键值对，HashMap 提供了专门的处理：getForNullKey()
/**
* 获取key对应值value
*/
public V get(Object key) {
/** 获取key为null，调用getForNullKey获取value **/
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
/**
* 获取key为null对应值value，key为NULL对应Entry，存储在哈希表数组第一个下标位置
*/
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是否存储在Map
*/
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
/**
* 获取key存储在哈希表中对象Entry
*/
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
/** 获取key对应的hash **/
int hash = (key == null) ? 0 : hash(key);
/** 计算hash值映射哈希表下标位置Entry，如果存在则从Entry开始，作为链表的头部元素，向后遍历查找key相同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;
}
