HashMap解决hash冲突的方法

put 方法：

 

    public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
	    //put方法通过调用key的hashcode()并以下面的hash算法计算后得到一个hash码
        int hash = hash(key);
        //再通过这个hash码与HashMap中的Entry数组长度来计算得到位置值i
		int i = indexFor(hash, table.length);//在length不发生变化的情况下i的值是相同的,所以在存入的两个不同key的hashcode()方法一致的时候得到的i值是一致的
        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;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }
	
	final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }

        h ^= k.hashCode();

        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
	
    static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
		//HashMap在初始化的时候默认会把Entry数组的长度设置为16或者设置为大于或等于指定大小的2的N次幂 
		//indexFor的方法很简单 return hash&length-1 ; 则 length-1 用二进制表示 一定是 011111....,
		//任何数比 length 小在按位与运算中都会得到这个数本身
		//如果hash=length则hash&length-1返回0
		
        return h & (length-1);
    }

 

  put方法通过调用key的hashcode()并以算法计算后得到一个hash码,再通过这个hash码与HashMap中的Entry数组长度来计算得到位置值i,HashMap在初始化的时候默认会把Entry数组的长度设置为16或者设置为大于或等于指定大小的2的N次幂 indexFor的方法很简单 return hash&length-1 ; 则 length-1 用二进制表示 一定是 011111....,任何数比 length 小在按位与运算中都会得到这个数本身,如果hash=length则hash&length-1返回0在length不发生变化的情况下i的值是相同的,所以在存入的两个不同key的hashcode()方法一致的时候得到的i值是一致的,然后是循环,主要是处理key完全一致或者用equals方法比对一致的情况,如果不一致的话则调用addEntry方法,处理的关键来了

 

 void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

 

   void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

 

在addEntry中用到了在HashMap内部声明的一种数据结构Entry,Entry中有个next属性的类型是这个类本身,所以我认为Entry是单向链表的一种实现,在调用addEntry的过程中,如果两个key的hashcode()方法的返回值一致,则会取到数组同一个位置上这时候HashMap的实现是把旧的Entry(先put进map的key-value)取出来放到新的Entry的next属性上,然后把新的Entry放在旧的Entry的位置上,这样就解决了hashcode的冲突问题,调用HashMap的get方法无法取出旧的Entry对应的value,只能通过entrySet()方法取出所有的Entry才能取到

 

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