HashMap源码分析

HashMap简介

HashMap允许放入Null,非线程安全,无序,相比于HashTable更快。

1
2
3
4
5
HashMap<String,Integer> map = new HashMap<>();
map.put(null,null);
map.put("1",1);
map.put("2",2;
map.put("3",3);

源码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
//DEFAULT_INITIAL_CAPACITY为1<<4即16
//DEFAULT_LOAD_FACTOR为0.75f
}
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();
}

无参构造函数中设定了默认桶数量为16、默认填充因子为0.75,赋值threshold为initialCapacity

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
//首次调用将初始化桶
}
if (key == null) //存放无key的value,存放在下标为0的桶中
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length); //根据桶数量及hash值计算当前存放在哪个桶
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;
//遍历当前桶中的数据,如果key的hash值相同,key值也相同,则更新value,并返回oldValue
}
}
//新值插入,返回空
modCount++;
addEntry(hash, key, value, i);
return null;
}

put函数调用将初始化桶,并是实现存放无key的value,查找到桶的下标,一直遍历查看是否是更新旧值,更新后返回;若是插入新值,则返回空。

1
2
3
4
5
6
7
8
9
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);
}

判断当前map中键值对数量是否超过threshold(为initialCapacity,构造函数中已赋值),判断当前要放的桶是否为空,满足上两个条件则扩容后存放

1
2
3
4
5
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++;
}

插入新元素时,先找到bucketIndex首元素(上次被插入的数据),新建Entry,放入bucketIndex并指向上次该桶被插入的数据

JDK8中的HashMap

JDK8中采用了红黑树,便于检索到数据(由于我校数据结构教学大纲中无红黑树,目前搞不懂)

附录

无意中接到了百度面试官的电话,超级紧张、说话结巴,面试官说我掌握的东西很XX(不敢吹,怕骄傲);我说自己看的源码很少,百度大佬:不要把源代码看的很高大上,不一定要去看。