一、Map
Map 是 Key-Value 对映射的抽象接口，该映射不包括重复的键，即一个键对应一个值。
二、HashMap概述
HashMap 是 Java Collection Framework 的重要成员，也是Map族(如下图所示)中我们最为常用的一种。简单地说，HashMap 是基于哈希表的 Map 接口的实现，以 Key-Value 的形式存在，即存储的对象是 Entry (同时包含了 Key 和 Value) 。在HashMap中，其会根据hash算法来计算key-value的存储位置并进行快速存取。特别地，HashMap最多只允许一条Entry的key为Null(多条会覆盖)，但允许多条Entry的值为Null。此外，HashMap 是 Map 的一个非同步的实现。
image.png
同样地，HashSet 也是 Java Collection Framework 的重要成员，是 Set 接口的常用实现类，但其与 HashMap 有很多相似之处。对于 HashSet 而言，其采用 Hash 算法决定元素在Set中的存储位置，这样可以保证元素的快速存取；对于 HashMap 而言，其将 key-value 当成一个整体(Entry 对象)来处理，其也采用同样的 Hash 算法去决定 key-value 的存储位置从而保证键值对的快速存取。虽然 HashMap 和 HashSet 实现的接口规范不同，但是它们底层的 Hash 存储机制完全相同。实际上，HashSet 本身就是在 HashMap 的基础上实现的。因此，通过对 HashMap 的数据结构、实现原理、源码实现三个方面了解，我们不但可以进一步掌握其底层的 Hash 存储机制，也有助于对 HashSet 的了解。
必须指出的是，虽然容器号称存储的是 Java 对象，但实际上并不会真正将 Java 对象放入容器中，只是在容器中保留这些对象的引用。也就是说，Java 容器实际上包含的是引用变量，而这些引用变量指向了我们要实际保存的 Java 对象。
Hash的原理
Hash其实就是散列，就是把任意长度的输入，通过散列算法变成固定长度的输出，由于是不定到定长，所以这种变换是一种压缩映射，输出值的值域远远小于输入值的值域，所以不同的输入可能会有相同的输出，这就是Hash碰撞。
哈希表
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。
三、HashMap 在JDK中的定义
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
...
}
四、HashMap详细介绍
1. HashMap 的数据结构
HashMap底层是一个数组结构，数组中的每一项都是链表（JDK1.8变为红黑树)。简单的说HashMap的存储结构是由数组和链表共同完成的。所以说HashMap是一个链表数组。
image.png
2. JDK1.8源码中链表的数据结构
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
...
}
Node(原来是Entry)为HashMap的内部类，实现了 Map.Entry 接口，其包含了键key、值value、下一个节点next，以及hash值四个属性。事实上，Node 是构成哈希表的基石，是哈希表所存储的元素的具体形式。
3. HashMap基本原理
- 计算key的hashcode，即调用hashcode()函数取得key的hashcode值。经过二次Hash处理得到Hash值。
- 用Hash值对数组的长度求余，得到对应的下标。
- 用所求的下标找到数组的相应位置的链表，进行插入、删除、查询等操作。
下面是源码中的进行二次hash的函数
// JDK1.8源码
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
4、HashMap概念介绍
image.png
5、HashMap中的Hash计算和碰撞问题
HashMap的hash计算时先计算hashCode(),然后进行二次hash。代码如下：
// 计算二次Hash
int hash = hash(key.hashCode());
// 通过Hash找数组索引
int i = indexFor(hash, table.length);
//非JDK1.8源码
static int hash(int h) {
// 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);
}
//非JDK1.8源码
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
6、解决冲突的方法
- 开放地址法（线性探测再散列，二次探测再散列，伪随机探测再散）
- 链地址法
- 再哈希法
- 建立公共溢出区
HashMap就是用的链地址法
7、HashMap的put()解析
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
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;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
步骤如下：
- 首先判断是否为key是否为空，为空就单独调用putForNullKey函数。
代码如下：
private V putForNullKey(V 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;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
如果key为null，则默认存储到table[0]的位置。遍历在table[0]位置存储的链表，寻找链表中key为null的节点Entry。如果找到，则更新该节点的value值，并且函数返回旧值。若没找到key为null的节点Entry，则插入新的节点。
- 计算key的hashcode,并且进行二次hash，通过indexFor(hash, table.length);找到Entry数组的索引i。
- 遍历以table[i]为头结点的链表。如果发现节点的hash和key的值都相等的节点，替换为新的value，然后返回旧的value。
- 众所周知，HashMap不是线程安全的，但在某些容错能力较好的应用中，如果你不想仅仅因为1%的可能性而去承受hashTable的同步开销，HashMap使用了Fail-Fast机制来处理这个问题，你会发现modCount在源码中是这样声明的。
volatile关键字声明了modCount，代表了多线程环境下访问modCount，根据JVM规范，只要modCount改变了，其他线程将读到最新的值。其实在Hashmap中modCount只是在迭代的时候起到关键作用。
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() {
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() {
// 这里就是关键
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 = modCount;
}
}
使用Iterator开始迭代时，会将modCount的赋值给expectedModCount，在迭代过程中，通过每次比较两者是否相等来判断HashMap是否在内部或被其它线程修改，如果modCount和expectedModCount值不一样，证明有其他线程在修改HashMap的结构，会抛出异常。
所以HashMap的put、remove等操作都有modCount++的计算。
- 如果没有找到key的hash相同的节点，就增加新的节点addEntry(),代码如下：
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}
新添加的节点都增加到头节点，然后新的头节点的next指向旧的老节点。
- 如果HashMap大小超过临界值，就要重新设置大小，扩容。
8、HashMap的get()解析
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
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.equals(k)))
return e.value;
}
return null;
}
和put原理类似，不在赘述。
9、HashMap的size()解析
每次新增加Entry的时候，size就递增。删除的时候就递减。
10、HashMap的reSize()解析
当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);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
从代码可以看出，如果大小超过最大容量就返回。否则就new 一个新的Entry数组，长度为旧的Entry数组长度的两倍。然后将旧的Entry[]复制到新的Entry[].代码如下：
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
参考自
https://blog.csdn.net/justloveyou_/article/details/62893086
https://www.jianshu.com/p/8b372f3a195d/
https://www.jianshu.com/p/4e3f3b53282f
网友评论