HashMap源码的初步了解

清疚 2023-07-09 02:06 9阅读 0赞

JDK1.8

首先我们初始化HashMap对象，这里一共有3个构造函数

//初始化一个HashMap对象，定义初始化容量为2，加载因子为1f
            Map<Integer,String> map = new HashMap<Integer,String>(2,1f);
    
            //初始化一个HashMap对象，定义初始化容量为4，加载因子为默认值0.75f
            Map<Integer,String> map2 = new HashMap<Integer,String>(4);
    
            //初始化一个HashMap对象，定义初始化容量为默认值16，加载因子为默认值0.75f
            Map<Integer,String> map3 = new HashMap<Integer,String>();

这里面的属性，initialCapacity 和 loadFactor 我们等会介绍，我们先来看构造函数内部干了啥

内部主要是tableSizeFor()函数，其返回了大于initialCapacity的，且最接近2的幂次方的数，用来初始化扩容阈值threshold

static final int tableSizeFor(int cap) {
            int n = cap - 1;
            n |= n >>> 1;
            n |= n >>> 2;
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        }

这里有用到 [按位或运算符][Link 1]， “ |= ”，这里不了解该运算符的，可以点超链接查看，这里我也简单举个例子介绍下

例如初始化hashMap时，成员变量initialCapacity值为5，那么该方法运算步骤如下图

int n = cap - 1;	//将原值-1，得到 n=4
    //以下均用二进制来表示	
    值为4:				0000	0100
    右移动1位			0000	0010
    位或运算新值	                0000	0110
    右移动2位			0000	0001
    位或运算新值		        0000	0111
    右移动4位			0000	0000	
    位或运算新值		        0000	0111
    右移动8位			0000	0000
    位或运算新值		        0000	0111	
    右移动16位			0000	0000
    位或运算新值		        0000	0111
    
    最终n值为 7 ,而后 7+1 = 8 ，8是最接近的2的幂次方，返回

到此，hashMap的初始化过程结束了，他初始化了下次扩容阈值threshold为8，加载因子

接下来，我们看put函数

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

这里，注意一点他并不是直接操作key.hashCode()，而是在hash(key)方法内部，将hash二进制右移动了16位后，新值的hash值

**这里为什么要向右移动，主要是为了消除低位值，以避免计算出来的hash都聚集在某一区间**

具体的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)
                //step.1 当Node数组不存在时，构造一个新Node数组
                n = (tab = resize()).length;
            if ((p = tab[i = (n - 1) & hash]) == null)
                //step.2 当该key的混淆hash值对应的Node节点不存在时，创建一个新节点
                tab[i] = newNode(hash, key, value, null);
            else {
                //step.3  当该key的混淆hash值对应的Node节点存在时
                Node<K,V> e; K k;
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    // step.4 当该key的混淆hash值相同，且KEY的真实hash值相同，将原节点Node-p，赋        值给临时节点Node-e
                    e = p;
                else if (p instanceof TreeNode)
                    //step.4  如果原节点Node-P，已经是二叉树结点，进行二叉树的putTreeVal()
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else {
                    //step.5 如果当前节点Node-p已经大于默认链表长度8，则将链表转化成二叉树
                    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;
                    }
                }
                //step.6 当节点Node-e有值，则将新value更新
                if (e != null) { // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;
           //step.7 当key的数量大于扩容阈值时，进行扩容resize()
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;
        }

这里在最后说一下，hashMap放置key的具体步骤，我们知道在step.1中，他初始化了一个Node数组，但是这个KEY要放到数组的第几个坑位，这是怎么判定的？用个例子解释下

p = tab[i = (n - 1) & hash]

十进制： 77824  初始化容量initical n为：2
    
    原hash: 		 0000 0000 0000 0001 0011 0000 0000 0001		
    右移16位混淆：	 0000 0000 0000 0000 0000 0000 0000 0001
    异或运算：	 0000 0000 0000 0001 0011 0000 0000 0000
    (n-1)            0000 0000 0000 0000 0000 0000 0000 0001
    按位与运算结果:	 0000 0000 0000 0000 0000 0000 0000 0000
    十进制结果为： 0 ，即0下标数组位，放置于Node[0]中

concurrentHashMap线程安全的原因：他对要修改的节点Node进行了synchronized，同步块锁

[Link 1]: https://baike.baidu.com/item/%E6%8C%89%E4%BD%8D%E6%88%96/548283?fr=aladdin