阅读jdk1.7的HashMap源码
麦兜 / 2020-04-17 / Java / 阅读量 315

首先一开头作者们已经注释了HashMap多线程执行是不安全的不同步的,如果非要用线程去操作HashMap

而且确保同步需要线程加锁或者Map m = Collections.synchronizedMap(new HashMap(...));


HashMap底层是数组+链表,实例化不并不会马上去初始化数组,而是有添加数据时才会初始化为2次幂大小容量的数组。详见PUT函数的代码

public static int highestOneBit(int i) {
    // HD, Figure 3-1
    i |= (i >>  1);
    i |= (i >>  2);
    i |= (i >>  4);
    i |= (i >>  8);
    i |= (i >> 16);
    return i - (i >>> 1);
}
Integer.highestOneBit 用于找一个接近n又小于等于n的二次幂数字 原理很简单,把二进制的低位都填充1
然后用高位减去低位即可获得2次幂的数。(2的次幂的数 二进制仅有一个1其他为数位都为0)
比如 5为二进制为101

i:101 i>>1:010

        101    
|       010
       -----
        111
 后面可以自己动手算算。

inflateTable 方法作用于计算出一个大于等于n的二次幂数字,所以在inflateTable里面调用Integer.highestOneBit(n-1)<<1。n-1是因为防止二次幂的数再次被<<1。 比如16 刚好满足,但是<<1过后得到结果为32。

默认数组容量为16也就是2的4次幂,数组只能开大于等于n的二次幂和小于等2^30的容量,这跟求数组Index有关,因为逻辑与运算比求余运算快的多。

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16


/**
* 哈希种子 如果为0就不用启动备用的hash值
*/
transient int hashSeed = 0;

final boolean initHashSeedAsNeeded(int capacity) {
        // 如果hashSeed != 0,表示当前正在使用备用哈希
        boolean currentAltHashing = hashSeed != 0;
        // 如果vm启动了且map的容量大于阈值,使用备用哈希
        boolean useAltHashing = sun.misc.VM.isBooted() &&
                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        // 异或操作,如果两值同时为false,或同时为true,都算是false。
        boolean switching = currentAltHashing ^ useAltHashing;
        if (switching) {
            // 把hashSeed设置成随机值
            hashSeed = useAltHashing
                    ? sun.misc.Hashing.randomHashSeed(this)
                    : 0;
        }
        return switching;
    }

indexFor(计算下标)

static int indexFor(int h, int length) {
    return h & (length-1);
}

h为哈希值
length为数组长度 (一定是2次幂的数 二进制仅有一个1其他为数位都为0)
&运算比%运算快,所以这就是为什么数组规定要为二次幂。
以初始长度16为例,16-1=15。2进制表示是 00000000 00000000 00001111,和某个哈希值做“与”操作如下,结果就是截取了最低的四位值。
    10100101 11000100 00100101
&    00000000 00000000 00001111
----------------------------------
    00000000 00000000 00000101    //高位全部归零,只保留末四位
而101的十进制为5 数组长度为16是符合的。

Hash(扰动函数

如果只是用indexFor去直接计算index值会导致碰撞很严重。

所以用Hash这个方法去混合原始哈希码的高位和低位,以此来加大低位的随机性,而且混合后的低位掺杂了高位的部分特征,这样高位的信息也被变相保留下来。

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);
}

PUT

HashMap的Key和Value都是可以为null,null的Key存在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;
}

HashMap的put不会每次都创建新的结点,因为key和value这样键值对应只需要更新value就行了。

e.hash == hash && ((k = e.key) == key || key.equals(k)) //需要更新的条件

更新完后它会返回旧的值,新添加的则返回null.
 int threshold; //临界值  初始值为initialCapacity 也就是初始化的数组容量,之后会改成新数组                           //size*DEFAULT_LOAD_FACTOR

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);
}

//当数量大于等于数组容量时还有当前table不能为空就会创建新的数组
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++;
}
//链表插头法 例如节点3 先先让新节点指向table[index] 然后再把table[index]赋值为新节点。

1

2

DEL

final Entry<K,V> removeEntryForKey(Object key) {
    if (size == 0) {
        return null;
    }
    int hash = (key == null) ? 0 : hash(key);
    int i = indexFor(hash, table.length);
    Entry<K,V> prev = table[i];
    Entry<K,V> e = prev;

    while (e != null) {
        Entry<K,V> next = e.next;
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {
            modCount++;
            size--;
            if (prev == e)
                table[i] = next;
            else
                prev.next = next;
            e.recordRemoval(this);
            return e;
        }
        prev = e;
        e = next;
    }

    return e;
}


//当链表只有一个就指向当前结点的next,否者指向当前table[index]的next 

resize

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {  //正如注释所说 如果数组为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);
}

/**
 * Transfers all entries from current table to newTable.
 */
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {     //newCapacity>=ALTERNATIVE_HASHING_THRESHOLD 才会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;
        }
    }
}

//链表在转移后会逆序

线程安全问题

1、也就是数组扩容需要重新赋值的时候(transfer函数)多线程会让结点的next乱指,造成闭环

get方法去遍历链表的时候就会死循环。

2、多线程put时可能导致元素丢失 原因:当多个线程同时执行addEntry(hash,key ,value,i)时,如果产生哈希碰撞,导致两个线程得到同样的bucketIndex去存储,就可能会发生元素覆盖丢失的情况。

1 + 1 =
快来做第一个评论的人吧~