共计 4531 个字符，预计需要花费 12 分钟才能阅读完成。
前言
讲讲 hashMap，简单的东西你还真不一定理解，真心的觉得需要有一篇文章把它给讲明白，这样就再也不怕面试被问到了。
**HashMap 介绍
HashMap 初始化
HashMap 扩容机制
HashMap 数据结构
HashMap 哈希冲突的解决
HashMap 使用 **
一、HashMap 介绍
他是基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。此实现假定哈希函数将元素适当地分布在各桶之间，可为基本操作（get 和 put）提供稳定的性能。另外，HashMap 是非线程安全的，而 Hashtable 是线程安全的。HashMap 是继承了 AbstractMap 类, 实现了 Map，Cloneable, Serializable 接口.
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable二、HashMap 初始化
重要参数说明
// 初始化的容量大小
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;HashMap 初始化的时候就做两件事, 初始化了容量 (比作一个桶) 的大小为 16 和负载因子为 0.75
public HashMap() {
// 初始化桶大小 DEFAULT_INITIAL_CAPACITY=16
// 负载因子 DEFAULT_LOAD_FACTOR=0.75
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
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.75
this.loadFactor = loadFactor;
// 初始化桶大小 16
threshold = initialCapacity;
init();}三、HashMap 扩容机制
负载因子可以理解为饱满度，负载因子越大，占用的的空间越小，但是查询的效率越低。负载因子越小，占用空间越大，但是会提高查询效率。这是由数据结构决定的，下面讲。
HashMap 的实际容量就是因子 * 容量，其默认值是 16×0.75=12；这个很重要，对效率有一定影响！当存入 HashMap 的对象超过这个容量时，HashMap 就会就需要 resize（扩容 2 倍后重排）。
private void inflateTable(int toSize) {
// 最接近且大于 toSize 的 2 的冪数
int capacity = roundUpToPowerOf2(toSize);
// 定义最大的实际容量，超过这个值就需要扩容
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
// 定义 Entry 数组，放 put 数据
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
// 最接近且大于 number 的 2 的冪数, 例如 number 为 3 返回结果是 4，number 为 4 返回结果为 4
private static int roundUpToPowerOf2(int number) {
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
// 添加元素，并判断是否需要扩容
void addEntry(int hash, K key, V value, int bucketIndex) {
//size 为当前数组大小，threshold 为实际最大容量, 如果大于就扩容
if ((size >= threshold) && (null != table[bucketIndex])) {resize(2 * table.length);// 扩容
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
// 添加
createEntry(hash, key, value, bucketIndex);
}
// 扩容
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;
}
}
}因为重新创建新的数据，重新计算元素的存储位置非常的影响性能，所以最好预估元素的多少，在创建 HashMap 的时候定义它的大小，最好为 2 的冪数，这样可以更好的利用空降。
四、HashMap 数据结构
HashMap 是一个散列桶（数组和链表），它存储的内容是键值对 key-value 映射，数组和链表的数据结构，能在查询和修改方面继承了数组的线性查询和链表的寻址修改。（横排表示数组，纵排表示链表）
五、HashMap 数据碰撞的解决
因为哈希值有哈希冲突的存在，所以不同的 key 可能有相同的哈希值。这个是后就需要通过链表结构来解决问题了。正常情况，当我们 put 存储一个 key-value 数据的时候，HashMap 会计根据 key 的哈希值计算应该在桶中保存的位置，判断该位置是否有数据，如果有数据，需要判断 hash 和 key 时候相等，如果相等，新的值替换老的值，并返回老的值。（这个不是“碰撞”，这中情况 key 是一样的）public V put(K key, V value) {if (table == EMPTY_TABLE) {inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
// 计算哈希
int hash = hash(key);
// 计算桶中的位置
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 判断哈希和 key 是否一样
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { // 一样
// 哈希一样，key 也一样
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// i 位置数据为空；或者数据不为空，hash 不一样；或者哈希一样，key 不一样
modCount++;
// 添加
addEntry(hash, key, value, i);
return null;
}i 位置数据为空；或者数据不为空，hash 不一样；或者哈希一样（哈希碰撞），key 不一样，走下面流程：
下面源码中，bucketIndex 为新的数据在数组中的位置，如果这个位置没有数据，会保存新数据，并且它在链表中的下一数据是 null（e 为 null），如果这个位置已经有数据，会在这个位置保存新的数据，它在链表中的下一个数据是老的数据(e)。
void createEntry(int hash, K key, V value, int bucketIndex) {
// 获取当前位置的数据 e，有可能是 null
Entry<K,V> e = table[bucketIndex];
// 当前位置保存新的数据，历史数据 e 为新数据的链表相联的数据
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}假如哈希值不一样，会产生碰撞吗？答案是肯定的.
首先我们看一下，hashMap 中数据在桶中位置计算方式
static int indexFor(int h, int length) {// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}“与”运算扩展：
参加运算的两个数据，按二进制位进行“与”运算。
运算规则：0&0=0;0&1=0;1&0=0;1&1=1;
即：两位同时为“1”，结果才为“1”，否则为 0
** 举例说明：
1&(16-1)=1
17&(16-1)=1**
所以我们可以理解，当桶的容量是固定的时候，负载因子越大，最大实际容量就会越大，需要保存的数据就越多。“碰撞”的情况出现的情况就会更多，增加了 HashMap 中链表结构中的数据，降低查询的效率。增加了空间利用率。
相反，当负载因子越小的时候，桶的实际容量就会越小，可以存的数据越少，碰撞情况减少，减少链表数据，增加查询效率。降低了空间利用率。
六、HashMap 的简单使用
搞定~
喜欢的小伙伴记得关注一下~ 可以免费领取学习资料~
