HashMap 1.7 源码分析

图示

测试代码:

public class MapMain {
    public static void main(String[] args) {
        HashMap map = new HashMap<>();
 
        map.put("hello", "world");
        map.get("hello");
    }
}

1.成员变量

先来看下默认的成员变量

public class HashMap
    extends AbstractMap
    implements Map, Cloneable, Serializable
{
 
    //默认初始化的数组的长度 是16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 
    //数组的最大长度
    static final int MAXIMUM_CAPACITY = 1 << 30;
 
    //hashMap默认的负载因子   
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
 
    //hashMap的数组  可以看到默认是个空数组
    static final Entry[] EMPTY_TABLE = {};
 
    
    transient Entry[] table = (Entry[]) EMPTY_TABLE;
 
    //hashMap元素的个数
    transient int size;
 
    //阈值 = 数组长度 * 0.75 
    int threshold;
 
    //负载因子
    final float loadFactor;
 
    //修改的次数  fast failed 在iteraotr遍历的时候
    transient int modCount;
 
    //rehash的时候可能会使用  基本不会用
    static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
    
    
    
    
    ------------------------------------------------------------------------
    static class Entry implements Map.Entry {
        //hashMap的key
        final K key;
        //hashMap的value
        V value;
        //链表的指针指向下一个元素
        Entry next;
        //可以的hash值  存在这里  在rehash的时候就不用再次计算了
        int hash;

2.默认的构造方法

public HashMap() {
        //16 0.75
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }
 
 
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        //赋值负载因子   
        this.loadFactor = loadFactor;
        //构造方法里面的阈值等于初始化的容量
        threshold = initialCapacity;
       
        init();
    }
        
    //HashMap的init是空的实现  LinkedHashMap才会有实现
    void init() {
    }

3.put方法

然后再看来下put方法

public V put(K key, V value) {
        //如果是空数组 就进去  我们可以看到默认是空的
        if (table == EMPTY_TABLE) {
            //上面看到空构造方法的阈值是默认的容量  16
            inflateTable(threshold);
        }
        //null值特殊处理 放到数组[0] 位置
        if (key == null)
            return putForNullKey(value);
        //计算hash值  可以忽略不看   
        // 简单的说就是让0和1  组成的值尽量在下面取余得到的位置更加的散列
        int hash = hash(key);
        //计算数组下标
        //h & (length-1)    使用按位&实现   索引值肯定不会超过 lengh -1   
        //length是16 
        //  1100 1010
        //& 0000 1111  
        //= 0000 1010      
        // 从这我们可以看到  数组长度越大  hash参与 & 的位数越多  散列性也就越强  
        int i = indexFor(hash, table.length);
        
        //处理key重复的场景  遍历这个单链表
        
        for (Entry e = table[i]; e != null; e = e.next) {
            Object k;
            //如果hash key相同  并且equal   hashMap就认为他们相等
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                //返回旧值使用
                V oldValue = e.value;
                //使用新值进行覆盖
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
 
        modCount++;
        //正常key不相同的进入这里
        addEntry(hash, key, value, i);
        return null;
    }

3.1 inflateTable

 //默认是16
    private void inflateTable(int toSize) {
        // Find a power of 2 >= toSize
        //找到最小的 大于等于toSize的2的次方的数字
        int capacity = roundUpToPowerOf2(toSize);
        //给阈值赋值为  0.75 * 数组的容量   当然不能超过最大值 MAXIMUM_CAPACITY
        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        //常见hashMap的数组
        table = new Entry[capacity];
        //可以先忽略
        initHashSeedAsNeeded(capacity);
    }

roundUpToPowerOf2方法

    private static int roundUpToPowerOf2(int number) {
        // assert number >= 0 : "number must be non-negative";
        //判断是否大于最大值 
        int rounded = number >= MAXIMUM_CAPACITY
                ? MAXIMUM_CAPACITY
                 //highestOneBit 找出离number最近的小于等于它的2的次方数  如果是0 就返回1
                : (rounded = Integer.highestOneBit(number)) != 0
                    ? 
                        //最近的小于等于它的2的次方数 二进制有1   就返回它的二倍  
                        //也就是最近的大于等于它的2的次方数
                        // 否则返回原值
                        ( (Integer.bitCount(number) > 1) ? rounded << 1 : rounded )
                    : 1;
 
        return rounded;
    }
 
//转化为二进制数的1的个数  16 -> 0001 0000 ->1    10 -> 0000 1010 -> 2
Integer.bitCount

highestOneBit

找出小于等于i的最大的2次方的数   
   public static int highestOneBit(int i) {
        // HD, Figure 3-1
        //往后相邻的弄成1
        i |= (i >>  1);
        //4个1
        i |= (i >>  2);
        //8个1
        i |= (i >>  4);
        //16个1
        i |= (i >>  8);
        //32个1
        i |= (i >> 16);
        return i - (i >>> 1);
    }
 
 
   10——>  1010
   i |= (i >>  1);
    1010
|   0101
---------
    1111
        
i |= (i >>  2);
    1111
|   0111
---------
    1111
 
同理可得
最后得1111
i - (i >>> 1);
1111 - 0111 = 1000  =  十进制就是  8

注意 1+2+4+16 刚好是int有符号整形表示数字的位数

3.2 putForNullKey

key 为 null 特殊处理

 private V putForNullKey(V value) {
       //如果存在就覆盖value
        for (Entry e = table[0]; e != null; e = e.next) {
            //如果key为null
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        //直接放到数组0的位置
        //这个方法后面再看  使用头插法  放入单链表
        addEntry(0, null, value, 0);
        return null;
    }

4.addEntry

    void addEntry(int hash, K key, V value, int bucketIndex) {
        //如果size大于等会扩容的阈值   并且当前要添加元素的数组已经有元素了 才会进行扩容
        if ((size >= threshold) && (null != table[bucketIndex])) {
            //扩容  可以看到新的容量是以前的2倍
            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 e = table[bucketIndex];
        //使用头插法插入新的元素   
        //新元素的next属性就是上面的e  就得数组的链表的头部    
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

5.resize

再来看下扩容的代码

 //newCapacity = 2 * oldCapacity
    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
        //创建新的数组
        Entry[] newTable = new Entry[newCapacity];
        //转移元素
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        //重新计算阈值
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

initHashSeedAsNeeded

如果这个值是true会重新计算hash值

是false则使用先前计算好的(在entry成员属性hash)

简单的描述下逻辑:

"jdk.map.althashing.threshold" 只有在被赋值的时候才有可能返回true 因为默认的是Int的最大值

final boolean initHashSeedAsNeeded(int capacity) {
        boolean currentAltHashing = hashSeed != 0;
        //sun.misc.VM.isBooted()  为
        //capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD  表示容量大于需要rehash的阈值
        boolean useAltHashing = sun.misc.VM.isBooted() &&
                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        //currentAltHashing  默认是true
        // ^  相同为真  不同为false
        //表示只有useAltHashing 为true的时候才会返回true
        boolean switching = currentAltHashing ^ useAltHashing;
        if (switching) {
            hashSeed = useAltHashing
                ? sun.misc.Hashing.randomHashSeed(this)
                : 0;
        }
        return switching;
    }
 
    //Holder.ALTERNATIVE_HASHING_THRESHOLD  默认是int类型的最大值  也就返回false
 
    private static class Holder {
 
        /**
         * Table capacity above which to switch to use alternative hashing.
         */
        static final int ALTERNATIVE_HASHING_THRESHOLD;
 
        static {
            //从jvm参数中获取jdk.map.althashing.threshold的值   rehash的阈值
            String altThreshold = java.security.AccessController.doPrivileged(
                new sun.security.action.GetPropertyAction(
                    "jdk.map.althashing.threshold"));
 
            int threshold;
            
            try {
                threshold = (null != altThreshold)
                        ? Integer.parseInt(altThreshold)
                        : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;
 
                // disable alternative hashing if -1
                if (threshold == -1) {
                    threshold = Integer.MAX_VALUE;
                }
 
                if (threshold < 0) {
                    throw new IllegalArgumentException("value must be positive integer.");
                }
            } catch(IllegalArgumentException failed) {
                throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
            }
            
            //不赋值就是int的最大值
            ALTERNATIVE_HASHING_THRESHOLD = threshold;
        }
    }

使用debug 啥也不指定 默认为true

transfer方法

//newTable  新的数组
    void transfer(Entry[] newTable  新的数组, boolean rehash) {
        int newCapacity = newTable.length;
        //遍历数组
        for (Entry e : table) {
            //遍历单链表   使用头插法进行迁移
            while(null != e) {
                Entry next = e.next;
                //是否重新计算hash值
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

扩容图示:

新的位置是 原位置 或者 原位置 + oldTable.length

使用的是头插法进行扩容 链表元素顺序会反转

6.循环链表

多线程会出现扩容 出现循环链表 形成死循环

transfer(Entry[] newTable, boolean rehash)

转移所有的 Entry 从当前 table 到新 table，被多个线程调用时可能会出现循环链表，线程不安全。

假设 table 中的某个位置如下图所示（有三个 Entry），thread1 和 thread2 都刚刚执行完 这个位置的第一次 while 循环的 Entry next = e.next;

thread1 执行完 while 循环

thread2 执行完第一次 while 循环

thread2 执行完第二次 while 循环

thread2 执行完第三次 while 循环

微信公众号:  后端小白养成记

欢迎关注: