java(8) HashMap源码

java

系统环境: JDK1.7

HashMap的基本结构:数组 + 链表。主数组不存储实际的数据,存储的是链表首地址。

成员变量

//默认数组的初始化大小为16

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

//最大数组大小

static final int MAXIMUM_CAPACITY = 1 << 30;

//默认负载因子,默认0.75

static final float DEFAULT_LOAD_FACTOR = 0.75f;

//空的数组

static final Entry<?,?>[] EMPTY_TABLE = {};

//存储元素的实体数组

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

//HashMap中元素的个数

transient int size;

//临界值,threshold = 负载因子 * 当前数组容量,实际个数超过临界值时,会进行扩容

int threshold;

//负载因子

final float loadFactor;

transient int modCount;

static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

Entry是HashMap中的一个静态内部类

static class Entry<K,V> implements Map.Entry<K,V> {

final K key;

V value;

Entry<K,V> next; //存储指向下一个Entry的引用,单链表结构

int hash; //对key的hashcode值进行hash运算后得到的值,存储在Entry,避免重复计算

/**

* Creates new entry.

*/

Entry(int h, K k, V v, Entry<K,V> n) {

value = v;

next = n;

key = k;

hash = h;

}

.......

}

构造方法

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(); //init方法在HashMap中没有实际实现,不过在其子类如 linkedHashMap中就会有对应实现

}

public HashMap(int initialCapacity) {

this(initialCapacity, DEFAULT_LOAD_FACTOR);

}

public HashMap() {

this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);

}

public HashMap(Map<? extends K, ? extends V> m) {

this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,

DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);

inflateTable(threshold);

putAllForCreate(m);

}

前三个常规构造器中,没有为数组table分配实际的内存空间,只进行了赋值操作。对于空的HashMap只有在执行put操作的时候才真正构建table数组。

而第4个构造器,则会为数组table分配实际的内存空间。关注最后一个构造方法,跟进inflateTable()

private void inflateTable(int toSize) {

// Find a power of 2 >= toSize

int capacity = roundUpToPowerOf2(toSize); //capacity一定是2的次幂

threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);

//为主干数组table在内存中分配存储空间

table = new Entry[capacity];

initHashSeedAsNeeded(capacity);

}

//通过roundUpToPowerOf2(toSize)可以确保capacity为大于或等于toSize的最接近toSize的二次幂

//比如toSize=13,则capacity=16;to_size=16,capacity=16;to_size=17,capacity=32.,

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;

}

疑问:capacity为什么是2的N次方? 一会儿在解释。

put方法分析

public V put(K key, V value) {  

// 若为第一次put,则先初始化数组

if (table == EMPTY_TABLE) {

inflateTable(threshold);

}

// key为null,放在table[0]即数组第一个的位置

if (key == null)

return putForNullKey(value);

// 根据key计算hash值,具体计算hash的算法我不太懂

int hash = hash(key);

// 根据hash值和表的长度,确定这个元素存放在数组的第几个位置,即求得元素在数组中的位置的索引值

int i = indexFor(hash, table.length);

// 遍历该位置的链表,如果有重复的key,则将value覆盖

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

V oldValue = e.value;

e.value = value;

e.recordAccess(this);

return oldValue;

}

}

// 修改次数+1

modCount++;

// 将新加入的数据挂载到table[i]的位置

addEntry(hash, key, value, i);

return null;

}

private V putForNullKey(V value) {

for (Entry<K,V> e = table[0]; e != null; e = e.next) {

if (e.key == null) { //如果有key为null的对象存在,则覆盖掉

V oldValue = e.value;

e.value = value;

e.recordAccess(this);

return oldValue;

}

}

modCount++;

addEntry(0, null, value, 0); //如果键为null的话,则hash值为0

return null;

}

//根据hashCode和数组的长度,返回元素存储的索引位置

static int indexFor(int h, int length) {

return h & (length-1);

}

这块就能印证之前数组长度为什么要为2的N次方了.

首先,若数组长度为2的N次方,则length必然为偶数,则length-1必然为奇数,在2进制的表示中奇数的最后一位为1,所以与奇数做“&”操作,最后的结果可能为奇数,也可能为偶数。

其次,若length为奇数,则length-1为偶数,偶数在2进制中最后一位为0,那么与偶数做“&”操作,最后的结果只可能是偶数,不可能为奇数,所以在奇数位置的空间不会存储到元素,这样会有二分之一的空间被浪费掉。

综上所述,数组长度取2的N次方,目的是为了能让元素均匀的分布在数组中,减小发生冲突的机会。

//与已存在的链表的key不重复的话,则新增节点

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

}

//新增加的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++;

}

//再来看看需要扩容的情况,当现有的元素个数大于等于临界值的时候需要进行扩容,跟进resize方法

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

}

//细细体会每个Entry的迁移过程

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

e.hash = null == e.key ? 0 : hash(e.key);

}

int i = indexFor(e.hash, newCapacity);

e.next = newTable[i];

newTable[i] = e;

e = next;

}

}

}

其他方法相对简单 就不整理了。

整理自《http://blog.csdn.net/zw0283/article/details/51177547》

 

以上是 java(8) HashMap源码 的全部内容, 来源链接: utcz.com/z/392431.html

回到顶部