我一直有个疑问，为什么 hashmap 能够实现 O(1) 的查找复杂度。。纵使其存储了一些键值对 < key,value>，那也只能保证你找到了 key 值之后，能够在 O(1) 事件内查询到 value 值。。而我的疑问是，怎么保证 key 值的查找也在 O(1) 事件内完成。而这也是整个 hashmap 中最关键的问题。

    一、理解：

    jdk 的源码：

    1. public V get(Object key) {  
    2.     if (key == null)  
    3.         return getForNullKey();  
    4.     int hash = hash(key.hashCode());  
    5.     for (Entry<K,V> e = table[indexFor(hash, table.length)];  
    6.          e != null;  
    7.          e = e.next) {  
    8.         Object k;  
    9.         if (e.hash == hash && ((k = e.key) == key || key.equals(k)))  
    10.             return e.value;  
    11.     }  
    12.     return null;  
    13. }

    通过阅读 jdk 的源码，我对该问题的理解如下：
    我们知道 hashmap 在存储键值对时借助了 “数组 + 链表” 的方式。

    java中hashmap容器实现查找O(1)时间复杂度的思考 - 图1

    我们对一个键值对的查询，是分为四步的。

    1. 先根据 key 值计算出 hash 值以及 h 值（h 值是 java 实现中处理得到的更优的 index 索引值）
    2. 查找 table 数组中的 h 位置，得到相应的键值对链表
    3. 根据 key 值，遍历键值对链表，找到相应的键值对，
    4. 从键值对中取出 value 值。

    只有以上四步都能在 O(1) 时间内完成，hashmap 才能拥有 O(1) 的时间复杂度。易知，步骤 1（计算）、步骤 2（数组的查找）和步骤 4（从键值对中取 value 值）都可以在 O(1) 时间内完成。那么，步骤 3 中链表的长度决定了整个 hashmap 容器的查找效率，这也是 hashmap 容器设计的关键。必须采用优秀的 hash 算法以减少 “冲突”，使得链表的长度尽可能短，理想状态下链表长度都为 1。

    二、结论：

    1. hashmap 容器 O(1) 的查找时间复杂度只是其理想的状态，而这种理想状态需要由 java 设计者去保证
    2. 在由设计者保证了链表长度尽可能短的前提下，由于利用了数组结构，使得 key 的查找在 O(1) 时间内完成
    3. 可以将 hashmap 分成两部分来看待，hash 和 map。map 只是实现了键值对的存储，也就是以上查询步骤的第 4 步。而其整个 O(1) 的查找复杂度很大程度上是由 hash 来保证的。
    4. hashmap 对 hash 的使用体现出一些设计哲学，如：通过 key.hashCode() 将普通的 object 对象转换为 int 值，从而可以将其视为数组下标，利用数组 O(1) 的查找性能。
      https://blog.csdn.net/u014633283/article/details/48549155?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.nonecase&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.nonecase