Java HahMap 详解

参考 & 阅读

• skywang12345 - Java 集合系列10之 HashMap详细介绍(源码解析)和使用示例
  讲解十分到位, 其中评论也有重要信息.
• 高爽|Coder - HashMap深度解析

一些特点

• 容量大小为2的幂
  优点在后面有解释
• 与HashTable的一些区别
  • HashMap非线程安全, 而HashTable使用synchronized进行了同步, 不过HashTable基本过时了, 需要考虑多线程安全问题的话直接用ConcurrentHashMap就好.
  • HashMap不保证随着时间推移, 其中的元素次序是不变的. 而HashTable维持次序.
  • HashMap的Iterator是fast-fail的
    其实主要是Enumeration和Iterator的区别. 而且fast-fail不是一定被保证的, 即异常不一定会被抛出. 而且也不一定是在多线程环境下, 单线程如果违背了规则, 同样可能抛出异常. 该机制的实现是依靠modCount和expectedModCount. 即对比实际修改次数和预计修改次数.
    更多请阅读:
  • Java提高篇（三四）—–fail-fast机制
  • Java 集合 Fail-Fast 机制 VS Fail-Safe 机制

示例:

// 但是iterator.remove()不会导致这个异常
Set keys = hashMap.keySet();
for (Object key : keys) {
    hashMap.put(someObject, someValue); //it will throw the ConcurrentModificationException here
} 

 Enumeration keys = hashTable.keys();
 while (keys.hasMoreElements()) {
          hashTable.put(someKey, someValue);  //this is ok
}

• HashMap支持null的key和value, 而HashTable都不支持.

HashMap中的容量为何一定是2的幂

HashMap会将初始容量修正为某个2的幂, 即使传进去的不是2的次幂, HashMap也会在内部计算出大于传进去的数字的最小的2的次幂.

容量为2的幂的好处:

• 快速计算余数
  下面是HashMap中的下标计算方法:

 /**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length - 1);
    }

在length为2的幂时, 上述计算其实就是h % length.
有这么一个结论,

(number)base % basex is equivilent to the last x digits of (number)base.

来源: stackoverflow.
以2进制为例来理解这句话. 对于n = 2 ^ k, 不考虑负数的情况下, x % n的结果落在[0, n-1]. 而2的幂的二进制有个特点, 就是二进制表达中只有一个1. 而且对其减去数字1的时候, 原来位置的1变成0, 而后面的全部0, 都会变成1. 比如说:
8的二进制表示1000
8 - 1 = 7, 二进制表示为0111.
0111和任何数进行&运算, 都是[0, n -1]这个范围, 所以其实对于2的幂2 ^ r来说, 取余结果仅决定于最后(从右开始数)的r个二进制位.
而位运算速度快于%运算, 所以当大小满足2的幂时, 就可以这样来快速计算模.

至于为什么这么计算是正确的? 可以参考以下例子理解:
下面的数都是二进制

计算 1110 % 100
1110 = 1000 + 100 + 10
很明显1000 = 100 < 1 (左移一位), 即1000是100的整数倍, 所以不会对余数产生什么影响.
同理, 100也是一样, 所以最终余数只和10有关.