HashMap源码分析之Hash冲突的解决

版本：jdk.18 src
HashMap是java中实现hash算法的数据结构，hash算法是将给定对象经过hash算法，转化成一串数字。hash算法的实现有很多种，设计一个hash算法需靠考虑比较重要的一点是其计算的效率。
我们都知道，Java中的Object对象中有equals、hashCode、clone等方法，其他所有对象均继承Object方法。我们来看String对象是如何实现的hashCode方法。

    public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

上面的代码是String对象中的hashCode方法，这里我们以一个例子计算，来看看它是如何工作的。

String s = "a";
System.out.println("a的hash值："+s.hashCode());

>>Console输出:1的hash值：97

来看ASCII表
HashMap源码分析之Hash冲突的解决
从表中查的‘a’的ASCII码正好为97.

	for (int i = 0; i < value.length; i++) {
		h = 31 * h + val[i];
	}

源码中这句循环，正是计算的核心，由于这里只有一个字符’1’，h的初始值为0，所以循环只循环一次，计算得

h = 31 * 0 + val[0];

val[0]为a的ASCII的值。

下面再计算一个例子’Aa’

String s = "Aa";
System.out.println("1的hash值："+s.hashCode());

>>Console输出:Aa的hash值：2112

这个值也不难看出是由

31*65+97

得到的

那么有没有可能两个字符串算出来的hashCode值相等呢？
下面计算

String s2 = "BB";
System.out.println("BB的hash值："+s2.hashCode());
	
>>Console输出:BB的hash值：2112

这就显示Aa和BB是hash冲突的。
这时我们执行如下操作会发生什么事情？

String Aa = "Aa";
System.out.println("Aa的hash值："+Aa.hashCode());

String BB = "BB";
System.out.println("BB的hash值："+BB.hashCode());

HashMap<String, Integer> map = new HashMap<String, Integer>();
map.put(Aa,1);
map.put(BB,2);

HashMap通过计算Key的hashCode值，这里就会引起hash冲突，HashMap如何解决Hash冲突？这里一步一步来看源码。
首先是HashMap的put方法

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

先看hash(key)

   static final int hash(Object key) {
       int h;
       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
   }

关键方法key.hashCode()，这里由于传进来的key是String类型，所以会调用String类型的hashCode方法来计算hashCode值，然后进行了一次亦或运算。
接着看putVal

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
        	//初始化tab，这里也会为HashMap做扩容
            n = (tab = resize()).length;
            //如果hash槽本来就是null，就直接添加
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            //如果没有Hash冲突
            if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //如果有Hash冲突，先看p是不是TreeNode类型。（这是个红黑树，为了查找快，下面会说原因）
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
           	//如果有冲突，也不是TreeNode，就新建一个链表节点追加，并判断容量。
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

核心代码添加了注释，HashMap设计的巧妙之处在与，当有Hash冲突时，会在该冲突点创建一个链表，每个链表节点保存冲突的Hash的Key Value值，这样即使出现冲突，也能根据Key的字面值取到value。倘若有1万个冲突，那链表长度为1万，这样的查找效率是o(n)，所以当冲突数量超过一定阈值jdk是8个，也就是源码中的TREEIFY_THRESHOLD字段，那么会将链表转换成一个TreeNode，树的查找效率就要高了。可以看到jdk的设计思想很巧妙。
这里还有两个重要的方法：resize()和treeifyBin()，下一章继续。

HashMap源码分析之Hash冲突的解决

相关推荐