HashMap

哈希表

对于一个元素，如何在容器中找到相同的元素？不同的容器的时间复杂度：

数据结构	查找时间复杂度
数组（无序）	O(n)
链表	O(n)
二叉搜索树	O(log n)
哈希表	O(1)（理想情况）

哈希表在存储元素时，计算hashCode值，并取容器的模放在指定的位置

hash("Tom")  → 1
hash("Jack") → 5
hash("Lucy") → 2

index:   1    2    5
         |    |    |
       Tom  Lucy  Jack

不同的元素计算得打的hashCode值可能相同，此时将在相同位置的链表后面。

查询元素时计算hashCode值，如果指定位置有元素，则再比较equals方法，如果hashCode和equals都相同，说明为相同的元素。

HashMap底层

HashMap底层依赖于哈希表

           put(key, value)
                  │
          hashCode()
                  │
          定位数组下标
                  │
        ┌─────────┴─────────┐
        │                   │
     没元素              有元素
        │                   │
     直接放           equals 比较
                          │
            ┌─────────────┴─────────────┐
            │                           │
        相同（true）              不同（false）
            │                           │
         覆盖值                  链表追加
                                    │
                              ≥8 → 红黑树