HashMap 解决 hash 冲突

HashMap 采用一种所谓的 “Hash 算法” 来决定每个元素的存储位置。当程序执行 map.put(String,Obect)方法 时，系统将调用 key的String 的 hashCode() 方法得到其 hashCode 值——每个 Java 对象都有 hashCode() 方法，都可通过该方法获得它的 hashCode 值。得到这个对象的 hashCode 值之后，系统会根据该 hashCode 值来决定该元素的存储位置。

存储过程：

• 判断当前确定的索引位置是否存在相同 hashcode 和相同 key 的元素，如果存在相同的 hashcode 和相同的 key 的元素，那么新值覆盖原来的旧值，并返回旧值。
• 如果存在相同的 hashcode，那么他们确定的索引位置就相同，这时判断他们的 key 是否相同，如果不相同，这时就是产生了 hash 冲突。
• Hash 冲突后，那么 HashMap 的单个 bucket 里存储的不是一个 Entry，而是一个 Entry 链。
• 系统只能必须按顺序遍历每个 Entry，直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端 (该 Entry 是最早放入该 bucket 中)，那系统必须循环到最后才能找到该元素。

上面程序中用到了一个重要的内部接口：Map.Entry，每个 Map.Entry 其实就是一个 key-value 对。从上面程序中可以看出：当系统决定存储 HashMap 中的 key-value 对时，完全没有考虑 Entry 中的 value，​

​仅仅只是根据 key 来计算并决定每个 Entry 的存储位置​

​。这也说明了前面的结论：我们完全可以把 Map 集合中的 value 当成 key 的附属，当系统决定了 key 的存储位置之后，value 随之保存在那里即可. HashMap 程序经过我改造，我故意的构造出了 hash 冲突现象，因为 HashMap 的初始大小 16, 但是我在 hashmap 里面放了超过 16 个元素，并且我屏蔽了它的 resize() 方法。不让它去扩容。这时 HashMap 的底层数组 Entry[] 。

Hashmap 里面的 bucket 出现了单链表的形式，散列表要解决的一个问题就是散列值的冲突问题，通常是两种方法：链表法和开放地址法。链表法就是将相同 hash 值的对象组织成一个链表放在 hash 值对应的槽位；开放地址法是通过一个探测算法，当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位。java.util.HashMap 采用的链表法的方式，链表是单向链表。形成单链表的核心代码如下：

voidaddEntry(inthash, K key, V value,intbucketIndex) {

Entry e = table[bucketIndex];

table[bucketIndex] =newEntry(hash, key, value, e);

if(size++>= threshold)

resize(2* table.length);      

上面方法的代码很简单，但其中包含了一个设计：系统总是将新添加的 Entry 对象放入 table 数组的 bucketIndex 索引处——如果 bucketIndex 索引处已经有了一个 Entry 对象，那新添加的 Entry 对象指向原有的 Entry 对象 (产生一个 Entry 链)，如果 bucketIndex 索引处没有 Entry 对象，也就是上面程序代码的 e 变量是 null，也就是新放入的 Entry 对象指向 null，也就是没有产生 Entry 链。