Java HashMap分析之三:放入元素
现在,有了hash code,来考虑如何计算放入数组的位置。hash code值通常会很大,但是数组的大小有限,默认只有16,大的也不能超过2的30次方。所以,用模运算来保证在数组大小范围内是合理的,比如:index = hash code % array size.不过这有点慢,JDK采用了更快的算法。这个更快的算法源于一个数学规律,就是如果size是2的N次方,那么数X对size的模运算结果等价于X和size-1的按位与运算,也就是 X % size <=> X & (size -1).按位与只消耗一个CPU周期,当然快多了。现在就可理解为什么要故意把数组大小弄成2的N次方了。再回头看一开始计算数组大小的代码,完全理解了。
- int capacity = 1;
- while (capacity < initialCapacity)
- capacity <<= 1;
比如size=16,二进制表示如下:(32位)
0000000000000000000000000010000
size-1=15,表示如下:
0000000000000000000000000001111
假如hash code=4
0000000000000000000000000000100
4 & 15 结果为:
0000000000000000000000000000100
假如hash code=6
0000000000000000000000000000101
6 & 15 结果为:
0000000000000000000000000000101
假如hash code=38
0000000000000000000000000100110
38 & 15 结果为:
0000000000000000000000000000110
通过观察这三个例子,又可以发现一个特点,也就是X & size-1 的结果受到了size的阶数的限制,这里size=16,阶数为4.结果就是只用低4位的1和X按位与,而X的高位没有用到。这会导致重复率相当高。如果用一个算法将X的低位重新计算,比如根据所有位的值进行重新计算,就可以使得hash值分布更均匀。下面的代码揭示了在真正按位与之前,调用了hash函数,进行了一堆位运算。至于为什么用这个算法,我也不知道其来历。
- public V put(K key, V value) {
- if (key == null)
- return putForNullKey(value);
- int hash = hash(key.hashCode());
- int i = indexFor(hash, table.length);
- 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))) {
- V oldValue = e.value;
- e.value = value;
- e.recordAccess(this);
- return oldValue;
- }
- }
- modCount++;
- addEntry(hash, key, value, i);
- return null;
- }
- static int hash(int h) {
- // This function ensures that hashCodes that differ only by
- // constant multiples at each bit position have a bounded
- // number of collisions (approximately 8 at default load factor).
- h ^= (h >>> 20) ^ (h >>> 12);
- return h ^ (h >>> 7) ^ (h >>> 4);
- }
- static int indexFor(int h, int length) {
- return h & (length-1);
- }
- void addEntry(int hash, K key, V value, int bucketIndex) {
- Entry<K,V> e = table[bucketIndex];
- table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
- if (size++ >= threshold)
- resize(2 * table.length);
- }
上面的for循环是查找并替换符合条件的对象,如果找不到,则添加新的对象。查找到的条件(必须都满足)是:
1.hash值相等
2.key的引用相同或者key的值相等。
原文链接:http://blog.csdn.net/sheismylife/article/details/7355282
【编辑推荐】
相关文章
- 单细胞转录组实战01: CellRanger7定量
- 02.Python Dash网页开发:网页有哪些元素组成与数据流
- 关于单个flask接口的微信request合法域名认证(无需借助任何集成环境)
- 预处理指令用法详解(C语言)
- R语言、SPSS基于主成分PCA的中国城镇居民消费结构研究可视化分析
- R语言使用虚拟变量(Dummy Variables) 回归分析工资影响因素|附代码数据
- R语言用贝叶斯线性回归、贝叶斯模型平均 (BMA)来预测工人工资|附代码数据
- R语言绘图|patchwork拼图
- IntelliJ IDEA 撤销和反撤销
- 校园食堂明厨亮灶AI智能分析盒
- IntelliJ IDEA 修改只读模式和可写模式
- 如何在轻量云上创建协同办公云文档
- 生信入门课DAY4--向逸一
- (二)Linux嵌入式开发——软件安装(Ubuntu)
- Linux嵌入式开发——文件系统结构
- Linux嵌入式开发——压缩与解压缩
- C语言之初识指针
- c语言中的常见图形打印
- 初始结构体
- C# 如何部分加载“超大”解决方案中的部分项目