1 概述
HashMap 是 Java Collection Framework的重要成员,也是Map接口最常用的实现类,其存储结构对应为数据结构-散列表,也被称为哈希表存储。
2 散列表
散列表的英文叫“Hash Table”,我们平时也叫它“哈希表”或者“Hash 表”,散列表用的就是数组支持按照下标随机访问的时候,时间复杂度是 O(1) 的特性。我们通过散列函数把元素的键值映射为下标,然后将数据存储在数组中对应下标的位置
image2.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链表法使用链表法来存储数据
imageHashMap使用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;
}
}
}
小结
image6 向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;
}
网友评论