参考 & 阅读
-
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 机制
- HashMap非线程安全, 而HashTable使用
示例:
// 但是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有关.
