HashMap 如何解决hash冲突

在Java编程语言中，最基本的结构就是两种，一种是数组，一种是模拟指针(引用),全部的数据结构均可以用这两个基本结构构造，HashMap也同样。 当程序试图将多个 key-value 放入 HashMap 中时，以以下代码片断为例： java

HashMap<String,Object> m=new HashMap<String,Object>();
m.put("a", "rrr1");
m.put("b", "tt9");
m.put("c", "tt8");
m.put("d", "g7");
m.put("e", "d6");
m.put("f", "d4");
m.put("g", "d4");
m.put("h", "d3");
m.put("i", "d2");
m.put("j", "d1");
m.put("k", "1");
m.put("o", "2");
m.put("p", "3");
m.put("q", "4");
m.put("r", "5");
m.put("s", "6");
m.put("t", "7");
m.put("u", "8");
m.put("v", "9");算法

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

Java代码   数组

   public V put(K key, V value) {  
        if (key == null)  
            return putForNullKey(value);  
        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;  
            //判断当前肯定的索引位置是否存在相同hashcode和相同key的元素，若是存在相同的hashcode和相同的key的元素，那么新值覆盖原来的旧值，并返回旧值。  
            //若是存在相同的hashcode，那么他们肯定的索引位置就相同，这时判断他们的key是否相同，若是不相同，这时就是产生了hash冲突。  
            //Hash冲突后，那么HashMap的单个bucket里存储的不是一个 Entry，而是一个 Entry 链。  
            //系统只能必须按顺序遍历每一个 Entry，直到找到想搜索的 Entry 为止——若是刚好要搜索的 Entry 位于该 Entry 链的最末端（该 Entry 是最先放入该 bucket 中），  
            //那系统必须循环到最后才能找到该元素。  
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
                V oldValue = e.value;  
                e.value = value;  
                return oldValue;  
            }  
        }  
        modCount++;  
        addEntry(hash, key, value, i);  
        return null;  
    }

       上面程序中用到了一个重要的内部接口：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[]   table结构以下:  数据结构

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

Java代码   性能

 void addEntry(int hash, K key, V value, int bucketIndex) {  
        Entry<K,V> e = table[bucketIndex];  
        table[bucketIndex] = new Entry<K,V>(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 链。
spa

       HashMap里面没有出现hash冲突时，没有造成单链表时，hashmap查找元素很快,get()方法可以直接定位到元素，可是出现单链表后，单个 bucket 里存储的不是一个 Entry，而是一个 Entry 链，系统只能必须按顺序遍历每一个 Entry，直到找到想搜索的 Entry 为止——若是刚好要搜索的 Entry 位于该 Entry 链的最末端（该 Entry 是最先放入该 bucket 中），那系统必须循环到最后才能找到该元素。 设计

       当建立 HashMap 时，有一个默认的负载因子（load factor），其默认值为 0.75，这是时间和空间成本上一种折衷：增大负载因子能够减小 Hash 表（就是那个 Entry 数组）所占用的内存空间，但会增长查询数据的时间开销，而查询是最频繁的的操做（HashMap 的 get() 与 put() 方法都要用到查询）；减少负载因子会提升数据查询的性能，但会增长 Hash 表所占用的内存空间。 指针