(周期计划-8)常用集合的源码分析:HashMap

写在前面

感兴趣的看官,可以看看我的其他文章:
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


这是一个主推面试踩坑的公众号!

因为身边的同学从事互联网相关职业的比较多,并且大家闲时聊天时总会吐槽找工作有很多坑,所以打算把身边同学找工作的经验,统统收集起来。提供给想从事这方面同学,希望圈内好友可以共同进步,共同少踩坑。

(周期计划-8)常用集合的源码分析:HashMap
个人公众号
上一篇:阿里云服务器可以用来做什么?


下一篇:Gnuradio 实验二