HashMap源码剖析(二)

无论是put方法还是get和remove方法,总能看到hash和indexFor两个方法的身影。从这个系列的前两篇文章,我们已经知道调用hash方法是计算针对key获取一个好的散列值,而调用IndexFor方法则可以知道要操作的Entry在hash table里的索引值。hash方法这里不做太多关注,如果有兴趣的同学参考这里

indexFor方法

static int indexFor(int h, int length) {
    return h & (length-1);
}

indexFor方法有两个参数,h是经过hash方法后计算出来的hash值。而length是hash table的长度。

transient Entry<K,V>[] table;
int i = indexFor(hash, table.length);

IndexFor方法的设计有什么考虑?我们知道length总是2的n次方,length减1后转换成2进制每个位上都是1. 比如length是16,那么减1后是15,对应的二进制是1111.这个设计的考虑是:

  • 保证计算得到的索引值总是位于hash table的索引之内
  • 如果(length-1)对应的二进制的某一位是0,那么h对应的二进制相对应的那一位无论是0还是1,与(length-1)做与操作以后,都是0,这明显会增加碰撞机会
  • 假设长度是15,就是14(1110)与h(hash值)进行与操作。那么hash table上索引对应的二进制最后一位是1的(0001, 0011,0101, 1011…)都没办法存储元素。

modCount变量

HashMap不是线程安全的集合类。但在某些容错能力较好的应用中,如果你不想仅仅因为1%的可能性而去承受hashTable的同步开销,则可以考虑利用一下HashMap的Fail-Fast机制. Fail-Fast发生在使用迭代器的过程,无论当前线程还是多线程修改了当前的HashMap,都会抛出ConcurrentModificationException。
这一策略在源码中的实现是通过modCount变量,modCount顾名思义就是修改次数,比如put,remove,但仅仅对HashMap内容的修改则不会增加这个值,那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。在迭代过程中,判断modCount跟expectedModCount是否相等,如果不相等就表示已经有其他线程修改了Map。modCount声明为volatile,保证线程之间修改的可见性

final Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();

Fail-Fast发生在使用迭代器的过程,如上代码。另外我们知道,HashMap循环取得包含的Entry有三种方式:

  • 直接取entry
     Map<String, String> map = new HashMap<String, String>();
     for (Entry<String, String> entry : map.entrySet()) {
         entry.getKey();
         entry.getValue();
     }
  • 调用集合的迭代器
     Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();
     while (iterator.hasNext()) {
         Map.Entry<String, String> entry = iterator.next();
         entry.getKey();
         entry.getValue();
     }
  • 先获取key,然后获取value
Map<String, String> map = new HashMap<String, String>();
     for (String key : map.keySet()) {
         map.get(key);
     }

问题来了,是不是上面三种形式在并发的情况下,都有可能触发Fail-Fast? 测试一下,你会发现,上面三种就会触发。原因是key和entry的迭代器里均调用了nextEntry方法。

private final class KeyIterator extends HashIterator<K> {
    public K next() {
        return nextEntry().getKey();
    }
}

private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
 public Map.Entry<K,V> next() {
 return nextEntry();
 }
}

既然知道使用put(一个新的元素)和remove的时候,modCount会改变,也就是说可能会导致ConcurrentModificationException被抛出。那么在迭代过程中,想加入一个元素或者移除一个元素就没有任何办法?对put来说,如果不借助于外部手段没有好的解决方案。而对remove来说,可以调用Iterator本身的方法remove来删除对象,原因是在移除一个对象后,新的modCount会赋值给expectedModCount,这样在下一次循环判断中,两个变量总是相等。

public void remove() {
    if (current == null)
        throw new IllegalStateException();
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    Object k = current.key;
    current = null;
    HashMap.this.removeEntryForKey(k);
    expectedModCount = modCount;
}

loadFactor变量(负载因子)

loadFactor作为hash table的负载因子,可以在HashMap的构建的时候设定一个具体值。默认是0.75. 通过与当前capacity的乘积来得到什么时候需要对hash table进行扩容。那么也许有人会问个问题,负载因子过大或者过小会有什么影响呢?

  • 过小,如果最终put到HashMap里的元素非常多的情况,会频繁进行扩容,因为扩容总是要重新计算所有元素(Entry)的hash值,并且对既有的元素进行重新分配,所以对性能总是有损失。
  • 过大,也许有人会说,按照你上面解释的逻辑,如果在元素很多的情况下,扩容次数就会少很多。如果从这点考虑是没错的。但是在元素容量一定的前提下,负载因子过大,会更加容易形成链表。这点上可能有点难以理解。举个例子,new一个HashMap,其容量和负载因子都使用默认值,分别为16和0.75. 如果容量超过12(16 * 0.75),HashMap就会进行扩容为原有大小的2倍,也就是32. 假设现在有11个元素,其中这两个元素的h分别为1和17,那么和15(length-1)做与操作后,会得到相同的index,这两个元素分布在同一个链表上。现在把负载因子减小到0.5. 那么在上面的条件下(11个元素)就会扩容成32. 但是h值为1和17的两个元素,就不会形成链表。

HashMap非线程安全

在多线程并发时,当put一些元素到HashMap里,并且在扩容(rehash)的时候,就容易在某个链表上发生死循环。特点是CPU占用率很高。网上关于这方面的分析已经能够很到位了,感兴趣的可以看这里

为什么要重写equals和hashcode

如果你通读这个系列的两篇文章,结合一些源码的学习,这个问题就太简单了。如果你还找不到答案,就当留给你的作业了:)。