深入吃透HashMap原理

HashMap这种数据结构。该数据结构采用数组和链表实现数据存储。然而这两种方式本质上代表了两种极端策略。

数组
数组所占据的空间在内存中是连续分配的，并且由于其对内存资源的占用程度较高而导致空间复杂度较大。然而，在进行二分查找时其时间复杂度较低（为O(1)），这使得它在处理大数据量时表现出色；相对于其他数据结构而言，在实现寻址操作方面较为方便；但插入和删除操作由于涉及较多的数据元素移动而显得相对麻烦。

链表
存储区间分散且内存占用较为经济，在这种情况下虽然空间复杂度较低（约为O(N)），但时间复杂度较高（约为O(N)）。链表的一个显著特点是地址访问较为困难，在这种情况下插入与删除操作相对便捷。

哈希表
有没有办法能够结合这两种特点来实现一种寻址简便且插入删除也快速的数据结构？确实是可以做到这一点。它就是我们今天要介绍的核心数据结构。哈希表（(Hash table）不仅在查找方面非常高效，在存储空间利用上也非常节省，并且操作过程非常直观易懂。就像精心设计的一把双刃剑，在提高效率的同时也不会占据过多资源。

存在多种不同类型的哈希表实现方案，在本节中我们将深入探讨其中一种最为常用的具体实现方式：拉链法。这种技术本质上等价于使用一组动态链接的列表来处理键值对。如图：

通过观察上图可知哈希表由数组与链表构成，在一个长度为16的数组里每个存储位置都对应一个链表的头节点。这些元素是如何分配到数组中的？通常使用hash(key)取模的方法来确定它们的位置例如，在上述示例中可以看到12、28等数值被存储在索引为12的位置

从本质上讲, HashMap实际上就是基于线性数组实现的数据结构。因此,我们可以将其视为一种存储数据的容器,其核心结构是一个线性数组。然而,这确实让人感到困惑,因为一个普通的线性数组是如何通过键值对来实现存取操作的呢？在这里,HashMap进行了相应的优化处理。

在HashMap内部定义了一个静态嵌套类Entry。该类的关键属性包括键值对（key-value）和链表（next）。通过键值对（key-value），我们可以清晰地看到Entry类是HashMap核心数据结构的基础单元。正如前面所述，HashMap的核心是一个线性数组结构。这个数组就是Entry[]类型变量实例化的结果。

    /** * The table, resized as necessary. Length MUST Always be a power of two.
     */
    transient Entry[] table;

2. HashMap的存取机制
   既然 HashMap 基于数组的数据结构（Array-based data structure），那么它为何能够实现随机访问（Random Access）？其中 HashMap 使用了一种高效的算法（Algorithm），具体来说，则采用了以下方法：

/* 存储时 */
计算出key对应的哈希值 hash。
无需深入讨论该实现细节，请理解每个key都会生成一个固定的整数值作为其哈希码。
使用模运算确定索引 index。
将值 value 存入数组中指定位置。

// 取值时:
计算key的哈希值为hash；
对hash执行取模运算以确定索引；
根据索引返回对应的Entry对象。

1）put

疑问：当两个不同的键（key）使用hash函数结合Entry数组长度计算出相同的索引时（即index = hash(key) % Entry[].length），会不会导致覆盖的问题？

public V put(K key, V value) {
if (key == null)
return putForNullKey(value); //null总是放在数组的第一个链表中
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;
//如果key在链表中已存在，则替换为新value
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;
}

addEntry函数用于将键-值对插入到指定桶索引对应的链表中。
首先创建一个新的Entry实例。
然后将该实例附加到当前桶索引对应的表项之后。
特别地，在哈希冲突发生时会进行链表扩展操作。
具体来说，在每次插入操作后会检查当前表项数量是否已达到阈值。
如果超出阈值则会调用resize方法扩大表格空间并重新散列。
此外，在HashMap中还设置了动态扩展机制以适应不断增加的数据量。
当数据量持续扩大时会根据一定规则自动扩展数组大小以确保性能不受影响。

public V retrieves(Object key){
if (key == null || key != null){
return getForNullKey();
}
int hashIndex = hash(key.hashCode());
// 先定位到数组元素
Table.Entry<K, V> entry;
for(entry : table[indexFor(hashIndex, table.length)]){
if(entry.hash == hashIndex &&
((K)V currentEntryKey = entry.key).equals(key) ||
entry.key != null && entry.key.equals(key)){
return entry.value;
}
}
return nullobject();
}

3）null key的存取
null key总是存放在Entry[]数组的第一个元素。

此方法用于将null值插入到指定的数据结构中。
遍历表中的每一个条目。
对于每一个条目：
如果当前条目没有键值域（key）：
将该条目原有的数据字段（value）存储到临时变量oldValue中。
更新该条目所对应的数值字段（value）为新的参数value。
触发该条目所对应的记录访问事件（recordAccess）。
返回临时变量oldValue中的数据字段。
循环结束后：
增加计数器modCount的值。
调用addEntry方法以记录新的数据项（0, null, value, 0）。
返回null作为函数的结果。

    private V getForNullKey() {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
    }

4）计算数组索引值：使用hashcode与table长度的模运算
在HashMap进行存取操作时
需要通过该运算找到对应的Entry位置
即通过该运算得到所需数组索引位置

/**

• Computes the index corresponding to the provided hash value h based on the given array length.
  */
  static int indexFor(int h, int length) {
  return h & (length - 1);
  }

bitwise OR运算的效果类似于mod或者取余操作；即当数组索引一致时，并不能保证hashCode值相同。

5）table初始大小

public HashMap(int initialSize, float loadRatio) {
…
// Calculate the next power of two greater than or equal to the initial capacity
int capacity = 1;
while (capacity < _initialSize) {
capacity <<= 1;
}
this._loadRatio = loadRatio;
threshold = (int)(capacity * loadRatio);
table = new Entry[capacity];
init();
}

注意table初始大小并不是构造函数中的initialCapacity！！

而是 >= initialCapacity的2的n次幂！！！！

————为什么这么设计呢？——

处理哈希冲突的方法主要有以下几种：

1. 开放定址法（包括线性探测再散列、二次探测再散列以及伪随机探测再散列）

2. 再哈希法

3. 链地址法

4. 建立一个公共溢出区

5. 在Java语言中，HashMap主要采用链表法来处理哈希冲突

在哈希表达到默认容量后 进行再散列操作 则需重新分配table的空间 以优化空间利用效率 如果当前哈希表已接近最大负载阈值 此时该算法会将当前哈希表的最大负载阈值设置为Integer.MAX_VALUE并返回 这将导致系统生成一个全新的空闲哈希表 并将原有数据及其映射关系转移至新表格中

/** * Redeploys the contents of this HashMap into a new array with an increased size.
* This method is automatically triggered once the number of keys in the HashMap exceeds
its load threshold.
* When the current HashMap capacity equals MAXIMUM_CAPACITY, it avoids resizing and
instead sets the load threshold to Integer.MAX_VALUE.
* This setup prevents further automatic resizes until more elements are added.
* @param newCapacity specifies desired hashmap size; must be power-of-two value */

       must be greater than current capacity unless current

       capacity is MAXIMUM_CAPACITY (in which case value

       is irrelevant).

*/
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);
}

/**

• 将当前表的所有条目转移到新表中。
  */
  函数transfer接收一个名为newTable的Entry数组参数并执行以下操作：

1. 将当前表的所有条目存储到临时数组src中（src = table）。
2. 计算新容量的新Capacity变量被赋值为newTable.length（计算新容量）。
3. 对于每个索引j（从0开始直到j小于src的长度），执行以下操作：
   a. 获取当前元素e（e = src[j]）。
   b. 如果当前元素e不为空，则将src[j]设为空并将e插入到新表中的适当位置：
   i. 将下一个元素next赋给变量e（e = next）。
   ii. 使用哈希值重新计算目标索引i（i = indexFor(e.hash, newCapacity)）。
   iii. 将下一个元素next赋给变量e（e = next）。
4. 重复上述步骤直到所有元素都被处理完毕。