写在前面
感兴趣的看官,可以看看我的其他文章:
1、从公司代码看Notification
2、Java反射实践:从反射中理解class
3、从公司项目配置看Gradle
上一篇博客,我们分析了ArrayList的源码实现,ArrayList吊起来观察一番之后,那么下一个被吊起来的肯定就是HashMap了。作为以key/value存储方式的集合,HashMap可以说起到了极大的作用。因此关于HashMap,我们将着重使用比较大的篇幅。
接下来会用到的几个常量static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
static final int MAXIMUM_CAPACITY = 1 << 30;
static final int MAXIMUM_CAPACITY = 1 << 30;
先简单过一下,HashMap的思路
我们put的key/value会被封装成一个叫做Entry的内部类。这个Entry由一个变量名为table数组管理。我们每次put会通过一系列的计算,计算一个table数组的index下标用于放Entry,如果出现hash冲突使用链表法解决。get时,可以理解是一个反向的put过程。
put(K key, V value)
1、初始化
if (table == EMPTY_TABLE) {
//threshold变量在初始化的时候使用DEFAULT_INITIAL_CAPACITY(16)初始化
inflateTable(threshold);
}
private void inflateTable(int toSize) {
//计算我们table数组应该有多大(初始化是16)
int capacity = roundUpToPowerOf2(toSize);
//重新给threshold赋值:数组容量*0.75
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
//初始化数组
table = new Entry[capacity];
//根据注释:应用于推迟初始化(暂时不做深究)
initHashSeedAsNeeded(capacity);
}
走到这一步,相当于我们的第一次put的初始化过程完成。那么接着让我们看下一步操作。
2、key为null
当然这一步的前面还有一个key为null的情况。因为实在是太直白,就不单独展开,代码如下:
if (key == null)
return putForNullKey(value);
private V putForNullKey(V value) {
//在0位置上的Entry链上遍历,如果已存在key为null的Entry,替换value,并返回老的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++;
//0位置如果没有存在Entry,直接正常add我们这个key为null的Entry
addEntry(0, null, value, 0);
return null;
}
这里我们可以得到一个信息,key为null的Entry会放在table[0]的位置上。
3、index下标计算
走到这一步,我们所要做的就是先计算我们这个key/value应该放在table的那个位置。也就是说,在真正包装成Entry之前,我们需要确定这个Entry的应该再哪个坑里。
计算hash值的hash方法如下:
//这个方法,的确是没有太怎么看明白是怎么计算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();
//注释翻译:该函数确保在每个数组位置上仅以恒定倍数不同的散列码,具有有限数量的冲突(在默认加载因子下约为8)。
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
计算完hash之后,就是通过hash计算我们Entry应该在那个下标中:
//这俩个参数一个是上文计算的hash,一个是table的length
static int indexFor(int h, int length) {
return h & (length-1);
}
走到这一步我们Entry该放在哪个位置已经明确了,这里有很多位运算...根据效果来看,这样的计算方式保证了,Entry更少的冲突。
4、插入Entry
既然上诉2的过程已经确定了插入位置,那么毫无疑问,我们该插入这个
Entry了。
1、重复key处理
既然插入,那么势必有可能遇到重复问题,比如说,我们插入同一个key。这里就是一个比较常见的问题,Map可不可以使用重复key,或者Map怎样处理重复key的问题。
//如果index有存在的Entry,很简单for循环遍历这条链
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))) {
//直接替换value,并且返回老的value
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
因此关于key重复的问题,我们就可以得到答案。Map的操作是替换旧的value并返回老的value。
2、扩容
上诉步骤我们处理的key重复的问题。那么接下来,就是Map的扩容过程。这里会用到一个变量threshold,我们知道初始化table之后,这个变量 = 数组长度*0.75。记住这个值,它就是扩容的阈值。
扩容的
void addEntry(int hash, K key, V value, int bucketIndex) {
//当前put进来的size>=threshold并且index下标不为空
if ((size >= threshold) && (null != table[bucketIndex])) {
//扩容2倍
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
//重新计算index
bucketIndex = indexFor(hash, table.length);
}
//不属于扩容的范畴
createEntry(hash, key, value, bucketIndex);
}
3、创建并添加
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++;
}
首先获取index下标下的Entry,我们明白这里的e有可能为空。(而这里没有对null这种情况进行判断,也就是说这里为不为空都无所谓)
拿到e之后,进行new Entry()把e,以及hash,key,value传了进来。
这里我们看一个e,放在了哪里?
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
//我们重复的Entry直接被放在了next上。
next = n;
key = k;
hash = h;
}
//省略部分内容
}
这里说明一个什么问题?那就是当hash冲突之后,我们的Entry是在链表的头还是尾。根据代码来看,很明显是在链表的头,这也说明了,为什么e为null这种情况没有做特别处理。
我们对put的分析就到此为止,既然分析了put,那么接下来就是get。
get(Object key)
1、处理key为null的情况
if (key == null)
return getForNullKey();
private V getForNullKey() {
//如果当前size为0,可以就没有对应的value
if (size == 0) {
return null;
}
//上文中我们分析到,put,key为null的value时,是放在table[0]上,那么取的时候,肯定也是去table[0]上去取。
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
关于key为null的情况,其实我们也能看出,比较简单明了。接下来就是key不为null的情况。
2、key不为null
final Entry<K,V> getEntry(Object key) {
//判空
if (size == 0) {
return null;
}
//通过key计算一个hash值。这里的key为null的判断,其实多此一举。
int hash = (key == null) ? 0 : hash(key);
//反向计算index,也就是对应这个key的Entry在数组的哪个下标中。
//因为我们put的时候知道,有可能index是会重复的。因此这里使用了一个循环去遍历这条链。如果hash相同,且key相同,那么就是我们要找的value,返回即可。
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
代码思路比较的明确,其实就是一个反向的put过程。我们先通过key计算hash,然后计算对应Entry在数组中的index,然后遍历对应链,找出匹配的value即可。
get方法我们可以看出,是比较简单的。
尾声
分析完put/get其实基本上HashMap就梳理完毕。
这里我们进行一点总结:
- 1、put时,key可以为空。并且放在table[0]的这个位置
- 2、扩容策略是,size>=当前容量*0.75并且当前table[index]不为null。扩容大小为2倍。
- 3、JDK1.7的HashMap使用链表法解决冲突,并且新插入的Entry是在链表的表头。
本菜开源的一个自己写的Demo,这个项目拆解并组合了很多业务。目的在于遇到类似业务,可以快速的ctrl+c/v。希望能给Androider们有所帮助,水平有限,见谅见谅…
https://github.com/zhiaixinyang/PersonalCollect
这是一个主推面试踩坑的公众号!
因为身边的同学从事互联网相关职业的比较多,并且大家闲时聊天时总会吐槽找工作有很多坑,所以打算把身边同学找工作的经验,统统收集起来。提供给想从事这方面同学,希望圈内好友可以共同进步,共同少踩坑。