> For the complete documentation index, see [llms.txt](https://yangsx95.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://yangsx95.gitbook.io/notes/programming-language/java/ji-he/map/hashmap.md).

# HashMap

![image-20220303195122934](/files/wWTdNCkGrN6dc89TbmwD)

![image-20220303195144762](/files/jg1V52BdvVvEOgOYP4Kg)

![image-20220303204913944](/files/kVh2PC3yX9KDnXHwekf8)

HashMap采用Hash表存储数据，由数组+链表的结构生成。数组的位置由key的hashcode的方法生成，每个数组位置存储一个`Entry`对象。因为数组的位置是由hashcode通过特定的算法生成的，所以会发生hash冲突。

当发生hash冲突时，将会把新的元素对象通过链表的方式连接到目标数组元素的首部/尾部（jdk1.7采用头插法，jdk1.8采用尾插法），当链表的长度大于8时，链表将会转换为红黑树。

## 源码解析

### 主要的属性

使用hash表存储，容器是一个数组：

![image-20220303205821623](/files/BVv9XU09SBd4LexEmzsY)

实际添加的元素数量由size属性记录：

![image-20220303212020870](/files/8oO78rs7CYp3dOT36UnK)

数组的默认容量：

![image-20220303212151067](/files/zmmpzPnPYysA5QNYRGpK)

数组的最大容量：

![image-20220303212233878](/files/YpN8ZbsSXgDSy7pKOSMt)

当向数组中不断的添加元素时，超过`threshold`扩容边界，就会发生扩容：

![image-20220303212554036](/files/s9MY4jqBFabd6qWxR8op)

而扩容边界是由扩容因子决定，`threshold = 当前数组的容量 * loadFactor` ：

![image-20220303212800177](/files/ocDkb36e8v7odMzenZqu)

默认的扩容因子值为 `0.75`，如果是一个`16`容量的数组，当用了`12`个容量位置时（`16 * 0.75 = 12`），就会触发扩容操作。

![image-20220303212835564](/files/1xCWuAzk5ATmMGPo0jMR)

**实际扩容时，将会按照二倍扩容的方式对数组进行扩容。**

### 构造器

![image-20220303211421278](/files/BnqDM4Rbj7jfwX0eYtzA)

分别指定`初始容量`以及`扩容因子`，如果不传则使用默认值`16`以及`0.75`。

其中边界值`threshold`的大小生成是通过如下方法决定的，他始终会返回一个`2^n`的数：

![image-20220303214347562](/files/uWp526zTMih39BiaDkly)

### put方法

![image-20220303214453686](/files/VOJ9Fl3IJDkjNZ6yyCrH)

其中，使用key计算目标的hash值（使用key的hashCode右移16位）：

![image-20220303215322600](/files/kvM2kMLt4KAYsfrWaKwH)

然后调用putVal方法，其中，`putVal`方法的具体逻辑如下：

```java
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
  Node<K,V>[] tab; Node<K,V> p; int n, i;
  // 如果hash表（也就是数组table）为空，先初始化hash表
  // resize方法会对 table 成员变量进行初始化
  // 最后获取新的hash表的容量n
  if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
  
  // 计算目标key在数组中的位置索引 i 变量， (n - 1) & hash，等效于 hash % length
  // 取出 i 位置的元素 p
  // 如果 p == null，说明没有发生hash冲突
  // 则创建一个Node对象，并放入到数组中
  if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
  
  // 否则发生了hash冲突
  else {
    Node<K,V> e; K k;
    // 如果原位置的p，这个节点的key与新添加的key的值相同
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
      e = p;
    // 如果原位置的p，这个节点类型是 TreeNode，说明p处在红黑树中，将目标元素放入到红黑树中
    else if (p instanceof TreeNode)
      e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    // 如果原位置的p，这个节点类型是链表
    else {
      // 从头至尾遍历链表
      // 如果遍历到尾部没有发现key相同的情况，就创建一个Node，将其添加到链表的最后（尾插法）
      //        插入完成后，判断当前链表的长度，如果当前链表的长度大于 TREEIFY_THRESHOLD - 1
      //        则触发链表转换红黑树的操作
      //        因为到达了链表结尾，所以e对象一定为null
      // 但如果这个过程中发现了目标key与当前key相同的情况
      //        结束循环，获取与之相同的这个节点e
      //        此时e一定不为null
      for (int binCount = 0; ; ++binCount) {
        if ((e = p.next) == null) {
          p.next = newNode(hash, key, value, null);
          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            treeifyBin(tab, hash);
          break;
        }
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
          break;
        p = e;
      }
    }
    
    // 如果e不为空，就代表存在相同key的情况
    // 将这个对象的值替换为新的value，并返回旧的value
    if (e != null) { // existing mapping for key
      V oldValue = e.value;
      if (!onlyIfAbsent || oldValue == null)
        e.value = value;
      afterNodeAccess(e);
      return oldValue;
    }
  }
  ++modCount;
  if (++size > threshold)
    resize();
  afterNodeInsertion(evict);
  return null;
}
```

### resize 数组的扩容

```java
final Node<K,V>[] resize() {
  Node<K,V>[] oldTab = table;
  int oldCap = (oldTab == null) ? 0 : oldTab.length;
  int oldThr = threshold;
  int newCap, newThr = 0;
  if (oldCap > 0) {
    if (oldCap >= MAXIMUM_CAPACITY) {
      threshold = Integer.MAX_VALUE;
      return oldTab;
    }
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
             oldCap >= DEFAULT_INITIAL_CAPACITY)
      newThr = oldThr << 1; // double threshold
  }
  else if (oldThr > 0) // initial capacity was placed in threshold
    newCap = oldThr;
  else {               // zero initial threshold signifies using defaults
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  }
  if (newThr == 0) {
    float ft = (float)newCap * loadFactor;
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
              (int)ft : Integer.MAX_VALUE);
  }
  threshold = newThr;
  @SuppressWarnings({"rawtypes","unchecked"})
  Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  table = newTab;
  if (oldTab != null) {
    for (int j = 0; j < oldCap; ++j) {
      Node<K,V> e;
      if ((e = oldTab[j]) != null) {
        oldTab[j] = null;
        if (e.next == null)
          newTab[e.hash & (newCap - 1)] = e;
        else if (e instanceof TreeNode)
          ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        else { // preserve order
          Node<K,V> loHead = null, loTail = null;
          Node<K,V> hiHead = null, hiTail = null;
          Node<K,V> next;
          do {
            next = e.next;
            if ((e.hash & oldCap) == 0) {
              if (loTail == null)
                loHead = e;
              else
                loTail.next = e;
              loTail = e;
            }
            else {
              if (hiTail == null)
                hiHead = e;
              else
                hiTail.next = e;
              hiTail = e;
            }
          } while ((e = next) != null);
          if (loTail != null) {
            loTail.next = null;
            newTab[j] = loHead;
          }
          if (hiTail != null) {
            hiTail.next = null;
            newTab[j + oldCap] = hiHead;
          }
        }
      }
    }
  }
  return newTab;
}
```

## 加载因子为什么是 0.75

如果扩容因子为1： 只有到16位置都满了之后才会发生扩容。虽然这时候空间利用率极大，但是会很容易发生hash碰撞，特别是剩余的空间不多时，这时候查询效率就会越低。

如果扩容因子为0.5：这时碰撞的概率极低，所以产生链表的概率也低，查询效率极高，但是空间利用率极低。

0.75是对时间与空间的成本上的折中。

## 主数组的长度为什么必须为2的n次方？

1. 确定目标key在数组的位置上是使用 `(length - 1) & hash`的方式产生的，等效于`length % hash`，而如果length的长度不是2的次幂，则这个等效就不会成立
2. 为了防止hash冲突

   ![image-20220303225229365](/files/Ra8aCWjIerXsYq0586s9)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://yangsx95.gitbook.io/notes/programming-language/java/ji-he/map/hashmap.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.