HashMap 是 Java 中最常用的数据结构之一，它基于哈希表实现， 具有快速查找和插入的特性。
存储数据
当向 HashMap 中插入一个键值对时，HashMap 会根据键的哈希值计算出该键值对应该存储的位置（ 称为索引） 。 如果该索引处没有其他键值对， 则直接将该键值对存储在该位置。 如果该索引处已经有其他键值对， 则将该键值对存储在该索引处的链表中。
获取数据
当从 HashMap 中获取一个值时，HashMap 会根据键的哈希值计算出该键值对应该存储的位置。 如果该索引处有该键值对， 则直接返回该值。 如果该索引处没有该键值对， 则在该索引处的链表中查找该键值对。
扩容条件
当 HashMap 中的元素数量超过其容量（capacity） 的负载因子（ load factor）时，HashMap 会自动扩容。负载因子是一个介于 0 和 1 之间的数字，它表示 HashMap 中已使用的空间与总空间的比例。默认情况下， HashMap 的负载因子为 0.75。
当 HashMap 扩容时，它会创建一个新的、更大的数组，并将原有的元素重新哈希到新的数组中。
HashMap 源码示例
public class HashMap<K, V> {
private static final int DEFAULT_INITIAL_CAPACITY = 16;
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
private Entry<K, V>[] table;
private int size;
private float loadFactor;
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0) {
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
}
if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
}
this.loadFactor = loadFactor;
this.table = new Entry[initialCapacity];
}
public V put(K key, V value) {
if (key == null) {
throw new NullPointerException("Key cannot be null");
}
if (value == null) {
throw new NullPointerException("Value cannot be null");
}
int hash = hash(key);
int index = hash % table.length;
Entry<K, V> e = table[index];
while (e != null) {
if (e.key.equals(key)) {
V oldValue = e.value;
e.value = value;
return oldValue;
}
e = e.next;
}
addEntry(key, value, index);
return null;
}
public V get(K key) {
if (key == null) {
throw new NullPointerException("Key cannot be null");
}
int hash = hash(key);
int index = hash % table.length;
Entry<K, V> e = table[index];
while (e != null) {
if (e.key.equals(key)) {
return e.value;
}
e = e.next;
}
return null;
}
private void addEntry(K key, V value, int index) {
Entry<K, V> e = new Entry<>(key, value, table[index]);
table[index] = e;
size++;
if (size > table.length * loadFactor) {
resize(table.length * 2);
}
}
private void resize(int newCapacity) {
Entry<K, V>[] newTable = new Entry[newCapacity];
for (Entry<K, V> e : table) {
while (e != null) {
int index = e.hash % newCapacity;
Entry<K, V> next = e.next;
e.next = newTable[index];
newTable[index] = e;
e = next;
}
}
table = newTable;
}private int hash(K key) {
int h = key.hashCode();
return h ^ (h >>> 16);
}
private static class Entry<K, V> {
final K key;
V value;
Entry<K, V> next;
Entry(K key, V value, Entry<K, V> next) {
this.key = key;
this.value = value;
this.next = next;
}
}
}
HashMap 的扩容过程如下：
检查是否需要扩容： 当 HashMap 中的元素数量超过其容量（capacity） 的负载因子（ load factor）时，HashMap 会自动扩容。
创建新的数组： HashMap 会创建一个新的、更大的数组，新数组的容量是原数组容量的两倍。
重新哈希元素： HashMap 会将原数组中的所有元素重新哈希到新的数组中。
更新引用： HashMap 会将原数组的引用更新为新数组的引用。
示例：
假设我们有一个 HashMap，其容量为 16，负载因子为 0.75。当 HashMap 中的元素数量超过 12（16 * 0.75）时，HashMap 会自动扩容。
扩容过程如下：
创建一个新的数组，容量为 32。
将原数组中的所有元素重新哈希到新的数组中。
将原数组的引用更新为新数组的引用。
扩容后，HashMap 的容量变为 32，负载因子变为 0.375（12 / 32）。
代码示例：
public class HashMap<K, V> {
// ...
//resize() 方法就是 HashMap 的扩容方法。它会创建一个新的数组，将原数组中的元素重新哈希到新的数组中， 然后更新原数组的引用。
private void resize(int newCapacity) {
Entry<K, V>[] newTable = new Entry[newCapacity];
for (Entry<K, V> e : table) {
while (e != null) {
int index = e.hash % newCapacity;
Entry<K, V> next = e.next;
e.next = newTable[index];
newTable[index] = e;
e = next;
}
}
table = newTable;
}
// ...
}
怎么解决hash冲突的？
解决哈希冲突的方法有以下几种：
开放寻址法： 当哈希函数将一个元素哈希到一个已经被占用的索引时， 开放寻址法会在这个索引附近寻找下一个可用的索引。 开放寻址法有以下几种变种：
线性探测：从冲突索引开始，依次检查下一个索引， 直到找到一个可用的索引。
二次探测：从冲突索引开始，以一定的步长（ 例如 2、4、8 等）依次检查下一个索引，直到找到一个可用的索引。
双重哈希：使用两个不同的哈希函数来计算索引， 如果第一个哈希函数冲突， 则使用第二个哈希函数来计算索引。
拉链法： 当哈希函数将一个元素哈希到一个已经被占用的索引时， 拉链法会在该索引处创建一个链表， 并将该元素添加到链表中。
再哈希法： 当哈希函数产生太多的冲突时，再哈希法会使用一个新的哈希函数来重新哈希所有元素。 示例： 假设我们有一个哈希表，其容量为 16，并使用开放寻址法来解决哈希冲突。当我们将元素 "apple" 和 "banana" 插入到哈希表中时，它们都被哈希到索引 5。
开放寻址法：
线性探测：我们将依次检查索引 6、7、8 等，直到找到一个可用的索引。
二次探测：我们将以步长 2 依次检查索引 7、9、11 等，直到找到一个可用的索引。
双重哈希：我们将使用两个不同的哈希函数来计算索引， 如果第一个哈希函数冲突， 则使用第二个哈希函数来计算索引。
拉链法：
我们将在索引 5 处创建一个链表，并将元素 "apple" 和 "banana" 添加到链表中。
再哈希法：
我们将使用一个新的哈希函数来重新哈希所有元素， 并将元素 "apple" 和 "banana" 插入到新的索引中。
