JAVA集合：HashMap深度解析（版本对比）

正文

请到「今天看啥」查看全文

new IllegalArgumentException( "Illegal load factor: " + loadFactor); this .loadFactor = loadFactor; threshold = initialCapacity; init(); }

• init方法，模板方法，如果有子类需要扩展可以自行实现

void init() {
}

主要方法

• hash方法

final int hash(Object k) {
    int h = hashSeed;
    //默认0，如果不是0，并且key是String类型，才使用新的hash算法（避免碰
    //撞的优化？）
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }
    h ^= k.hashCode();
    //把高位的值移到低位参与运算，使高位值的变化会影响到hash结果
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

• 根据hash值确定在table中的位置，length为2的倍数 HashMap的扩容是基于2的倍数来扩容的，从这里可以看出，对于indexFor方法而言，其具体实现就是通过一个计算出来的code值和数组长度-1做位运算，那么对于2^N来说，长度减一转换成二进制之后就是全一（长度16，len-1=15,二进制就是1111），所以这种设定的好处就是说，对于计算出来的code值得每一位都会影响到我们索引位置的确定，其目的就是为了能让数据更好的散列到不同的桶中。

static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
}

put方法

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {  
    //如果表没有初始化，则以阈值threshold的容量初始化表
        inflateTable(threshold);
    }
    if (key == null)   
    //如果key值为null，调用putForNullKey方法，所以hashmap可以插入key和value为null的值
        return putForNullKey(value);
    //计算key的hash值
    int hash = hash(key); 
    //计算hash值对应表的位置，即表下标
    int i = indexFor(hash, table.length); 
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
        //如果hash值相等并且（key值相等或者key的equals方法相等），
        //则覆盖，返回旧的value
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    //修改字数+1
    modCount++; 
    //如果没找到key没找到，则插入
    addEntry(hash, key, value, i);  
    return null;
}

• 初始化表方法， 表容量必须是2的倍数 （roundUpToPowerOf2）

private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    int capacity = roundUpToPowerOf2(toSize);

    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}

• 获取大于或等于给定值的最小的2的倍数

private static int roundUpToPowerOf2(int number) {
    // assert number >= 0 : "number must be non-negative";
    return number >= MAXIMUM_CAPACITY
            ? MAXIMUM_CAPACITY
            : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}

• highestOneBit：返回小于给定值的最大的2的倍数

public static int highestOneBit(int i) {
    // HD, Figure 3-1
    i |= (i >>  1); //其余位不管，把最高位的1覆盖到第二位，使前2位都是1
    i |= (i >>  2); //同样的，把第3、4位置1，使前4位都是1
    i |= (i >>  4); //...
    i |= (i >>  8); //...
    i |= (i >> 16); //最高位以及低位都是1
    return i - (i >>> 1);   //返回最高位为1，其余位全为0的值
}

• initHashSeedAsNeeded方法控制transfer扩容时是否重新hash

final boolean initHashSeedAsNeeded(int capacity) {
        //hashSeed默认0，currentAltHashing为false
        boolean currentAltHashing = hashSeed != 0;
        //参照上面的Holder类的静态块，jdk.map.althashing.threshold默认-1，Holder.ALTERNATIVE_HASHING_THRESHOLD为Integer.MAX_VALUE，如果jdk.map.althashing.threshold设置了其他非负数，可以改变Holder.ALTERNATIVE_HASHING_THRESHOLD的值，如果不超过Integer.MAX_VALUE，则useAltHashing为true
        boolean useAltHashing = sun.misc.VM.isBooted() &&
                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        boolean switching = currentAltHashing ^ useAltHashing;
        if (switching) {    //改变hashSeed的值，使hashSeed!=0，rehash时String类型会使用新hash算法
            hashSeed = useAltHashing
                ? sun.misc.Hashing.randomHashSeed(this)
                : 0;
        }
        return switching;
    }

• HashMap把key为null的key-value键值对放入table[0]中

private V putForNullKey(V value) {
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }

• 插入新的key-value键值对

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;   //null的hash值为0
            bucketIndex = indexFor(hash, table.length);
        }

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

• 头插法 ，即把新的Entry插入到table[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++;
}

get方法

public V get(Object key) {
    if (key == null)
        return getForNullKey(); //如果key为null，直接去table[0]中找
    Entry<K,V> entry = getEntry(key);

    return null == entry ? null : entry.getValue();
}

private V getForNullKey() {
    if (size == 0) {
        return null;
    }
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}

• getEntry方法比较简单，先找hash值在表中的位置，再循环链表查找Entry，如果存在，返回Entry，否则返回null

final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }

    int hash = (key == null) ? 0

请到「今天看啥」查看全文