JDK1.7中的hashMap源码分析

JDK1.7中的hashMap 重要属性

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16


//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;


static final float DEFAULT_LOAD_FACTOR = 0.75f;


static final Entry[] EMPTY_TABLE = {};


transient Entry[] table = (Entry[]) EMPTY_TABLE;


transient int size;


// If table == EMPTY_TABLE then this is the initial capacity at which the
// table will be created when inflated.
//要调整大小的下一个大小值（容量负载因子）。 @serial 如果 table == EMPTY_TABLE 那么这是膨胀时将创建表的初始容量
int threshold;


//哈希表的负载因子。
final float loadFactor;


//该 HashMap 被结构修改的次数该字段用于在 HashMap 的 Collection-views 上创建迭代器快速失败。
transient int modCount;


static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;


//哈希因子，用于计算哈希值
    transient int hashSeed = 0;

构造方法

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


public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}


public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}


public HashMap(Map m) {
    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                  DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
    inflateTable(threshold);

    putAllForCreate(m);
}

看看构造方法，将传入的初始化大小和负载因子赋给内部变量，接收Map集合时，额外进行了扩充内部容器，和赋值操作。

PUT方法

public V put(K key, V value) {
    //如果内部的容器是空的话进行扩容（默认就是空）
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

在put之前，首先判断内部容器是不是空，如果为空，则进行扩容，此时的threshold值为16，在构造方法里，进行了初始化默认值16

扩容方法

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

这里的重点代码就是Integer.highestoneBit((number - 1) << 1)，这到底是在干什么，我们进去看看

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

OH MY GOD! 多么优美的代码！说实话，看到这种代码之后，涌现心头的除了惊叹，佩服之外还有一丝丝害怕，怕看不懂这些代码，这一次就来搞明白这到底是在干嘛。

我们先拿16举例传进去

i	16	0001 0000
(i >> 1)		0000 1000
i \|=(i >> 1)		0001 1000
i		0001 1000
(i >> 2)		0000 0110
i\|= (i >> 2)		0001 1110
…
i		0001 1111
i>>>1		0000 1111
i-i>>>1	16	0001 0000

我们再拿11举例

i	11	0000 1011
(i >> 1)		0000 0101
i \|=(i >> 1)		0000 1111
i		0000 1111
(i >> 2)		0000 0011
i\|= (i >> 2)		0000 1111
…
i		0000 1111
i>>>1		0000 0111
i-i>>>1	8	0000 1000

通过测试，我们找到了规律，这个方法取的是数最大位的值。换句话说，就是取的小于等于此数的最大的2的幂次数。

那我们传进去的又是什么呢？

(number - 1) << 1

i	11	0000 1011
i-1	10	0000 1010
i-1<<1	20	0001 0100
highestOneBit	16	0001 0000

i	16	0001 0000
i-1	15	0000 1111
i-1<<1	30	0001 1110
highestOneBit	16	0001 0000

通过测试，我们发现如果我们传的不是2的幂，那么我们进过这种操作后，最高位往前挪一位，再进行highestOneBit操作，得到大于数字的最小2的幂次数，

如果我们传的值本来就是2的幂次数，我们进行操作，最高位不变，仍然得到大于等于数值的最小二的幂次数。这样的写法满足了所有的可能性。

好了，我们回到扩容方法，可以分析出，我们传入的容量大小并不是HashMap实际的容量大小，而是进过计算后，大于传入数值的最小2的幂次数。

然后根据需要初始化哈希因子。为什么要初始化哈希因子，我们以后再说。

扩容之后，判断key是否为null，对是null的key进行单独处理，我们放后面讲，先看普遍情况

int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry e = table[i]; e != null; e = e.next) {
    Object k;
    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
        V oldValue = e.value;
        e.value = value;
        e.recordAccess(this);
        return oldValue;
    }
}

modCount++;
addEntry(hash, key, value, i);

根据key的值，计算哈希值。

哈希计算方法

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

先取出哈希种子，如果哈希种子不是0,同时k是String，进行单独的哈希计算，我们看h的变化情况。

在扩容的时候就调用初始化哈希种子方法

final boolean initHashSeedAsNeeded(int capacity) {    boolean currentAltHashing = hashSeed != 0;    boolean useAltHashing = sun.misc.VM.isBooted() &&            (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);    boolean switching = currentAltHashing ^ useAltHashing;    if (switching) {        hashSeed = useAltHashing            ? sun.misc.Hashing.randomHashSeed(this)            : 0;    }    return switching;}

首先currentAltHashing默认为false，然后useAltHashing 这个值，判断capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD 这两个值的大小。

ALTERNATIVE_HASHING_THRESHOLD 此值只在内部类的静态方法里进行修改

private static class Holder {        static final int ALTERNATIVE_HASHING_THRESHOLD;    static {        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);        }        ALTERNATIVE_HASHING_THRESHOLD = threshold;    }}

重点赋值方法取jdk.map.althashing.threshold这个属性，在不进行配置的情况下最后的结果ALTERNATIVE_HASHING_THRESHOLD还是默认值。

所以说，我们如果不进行配置的话，hash值的算法是不会更换哈希种子的。

我们看到hashMap里计算hash的方法，取出Object的hashcode值之后还进行了复杂的计算，目的就是为了保证各个位的位置上具有有限的冲突（值一样）

思考一下，为什么要这样做？

回到put方法，我们在取得hash值之后，进行计算数组的下标。

1.7的JDK，组成结构是数组+链表，存放的是Entry对象，那么我们put进去之后是怎么找到数组的下标，然后进行链表的组合呢？

数组的下标是有范围的，0—length-1，而hash值是变化不定的，我们需要一个算法来根据hash值算出指定的这些数。

下标算法

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

简简单单的一行代码，体现了无穷的智慧，令人佩服。

首先我们要知道这个下标的两个限制

不能越界
几率相同

第一个很容易理解，数组的下标不能越界，第二个我们的Entry在放入数组时，要保证放到哪个下标的几率是完全相同的，这样才能保证hashMap中的数组不会有一列链表的长度比别的链表更容易变长。

那么我们来跟踪一下这个算法

h（哈希值完全随机）	0101 1111
length （数组长度 2的倍数）	0000 1000
length-1	0000 0111
结果	0000 0111

h（哈希值完全随机）	1010 1010
length （数组长度 2的倍数）	0000 1000
length-1	0000 0111
结果	0000 0010

根据测试，我们可以看出，length-1导致数值都为连续的1，这样哈希的值就起到了决定性的作用，例如数组长度为8, 那么length-1就为[0000-0111],变化范围就是【0000-0000】到【0000-0111】0-7的范围，完全随机！

所以这就是为什么数组的长度必须为2的幂次数的原因！

Entry对象

hashMap存入的实际是Entry对象，而Entry对象包含了一个向后的指针。

进入实际插入操作。

for (Entry e = table[i]; e != null; e = e.next) {    Object k;    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {        V oldValue = e.value;        e.value = value;        e.recordAccess(this);        return oldValue;    }}modCount++;addEntry(hash, key, value, i);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);    }void createEntry(int hash, K key, V value, int bucketIndex) {        Entry e = table[bucketIndex];        table[bucketIndex] = new Entry<>(hash, key, value, e);        size++;    }

取到数组下标后，找到对应的数组的Entry对象，遍历这个链表，如果重复，则返回老数据，新数据覆盖，修改数+1，如果没有，则进行新增操作，先判断是不是需要扩容了，扩容我们等会讲，先看新增，首先取出这个数组下标的对象，然后新建个对象替换原对象的位置，再指向原对象

图解

插入新数据后

新数据就通过头插法的形式插入到数组中了

key为null时的添加

private V putForNullKey(V value) {    for (Entry 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为null时，默认放在数组第一个下标，hash值默认为0

扩容方法

if ((size >= threshold) && (null != table[bucketIndex])) {    resize(2 * table.length);    hash = (null != key) ? hash(key) : 0;    bucketIndex = indexFor(hash, table.length);}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);    }void transfer(Entry[] newTable, boolean rehash) {        int newCapacity = newTable.length;        for (Entry e : table) {            while(null != e) {                Entry next = e.next;                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;            }        }    }

首先判断hashMap中存放的Entry对象的数量是否大于扩容的阈值，其次是当前数组下标的值不能为null。

然后创建新的数组，大小为原数组的两倍，initHashSeedAsNeeded（newCapacity）之前我们讲过，没配置jdk属性的话默认为false，然后遍历老数组的下标，取到首节点e，定义变量next，重新计算新数组的下标

数组大小-1（15）	0000 1111
哈希值	0101 0101
下标	0000 0101

数组大小-1（15）	0000 1111
哈希值	0100 0101
下标	0000 0101

数组大小-1（31）	0001 1111
哈希值	0101 0101
下标	0001 0101

数组大小-1（31）	0001 1111
哈希值	0100 0101
下标	0000 0101

我们可以看到，在数组大小翻倍的情况下，哈希值在数组大小-1高位的值的变化直接影响到了最后下标的值，变化情况为原下标或者原下标+原数组的长度。

图解扩容后链表的排列情况

扩容前，e遍历到A

假设下标没变e.next=newTable[i];

newTable[i] = e;(此时newTable[i]就是A)

e=next

一次移动后的结果

第二次移动e.next=newTable[i]

newTable[i] = e;(此时newTable[i]就是B)

e=next

上面两个图next指向b了是我的错误，应该指向c的，别迷了。

两次移动后

我们可以看到扩容之后如果下标不变的话，ABC的顺序会发生转变。

多线程扩容可能造成的循环链表情况

假设情景，两个线程在同时进入扩容方法后，进入循环遍历，此时同时执行Entry next = e.next;而此后，第二个线程没有拿到时间片进入等待状态。

此时内存场景

线程一已经完成扩容，而线程二还停留在第一个循环中，此时线程二执行。

e.next = newTable[i];newTable[i] = e;

e = next;

e.next = newTable[i];newTable[i] = e;

e = next;

e.next = newTable[i];newTable[i] = e;

已经出现循环链表的情况了

为什么会出现这种情况？归根结底还是头插法在扩容的时候导致E和NEXT颠倒造成的。

为什么扩容不直接移动第一个链表节点呢？

因为扩容的目的不是为了让数组变大，而是为了让链表变短，让节点更可能的分散。

modCount

我们进入class文件查看真实的代码

首先取得了一个迭代器，返回了一个KeyIterator

next方法

keyIterator继承HashIterator

我们在进行迭代器遍历的时候，不可以使用hashMap的remove方法，因为hashMap的remove方法不会改变这个迭代器内部属性expectedModCount，

当迭代器进行二次遍历的时候就会因为两个值的不同抛出异常，快速失败。

我们应该使用迭代器自己的remove方法。

JDK1.7中的hashMap源码分析

Java相关栏目本月热门文章