HashMap 中hash table 定位算法:
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
其中indexFor和hash源码如下:
/**
* Applies a supplemental hash function to a given hashCode, which
* defends against poor quality hash functions. This is critical
* because HashMap uses power-of-two length hash tables, that
* otherwise encounter collisions for hashCodes that do not differ
* in lower bits. Note: Null keys always map to hash 0, thus index 0.
*/
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);
}
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
indexFor这个方法论坛中已有人分析过,这里就不再分析。
现在分析一下hash算法:
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
假设key.hashCode()的值为:0x7FFFFFFF,table.length为默认值16。
上面算法执行如下:
得到i=15
其中h^(h>>>7)^(h>>>4) 结果中的位运行标识是把h>>>7 换成 h>>>8来看。
即最后h^(h>>>8)^(h>>>4) 运算后hashCode值每位数值如下:
8=8
7=7^8
6=6^7^8
5=5^8^7^6
4=4^7^6^5^8
3=3^8^6^5^8^4^7
2=2^7^5^4^7^3^8^6
1=1^6^4^3^8^6^2^7^5
结果中的1、2、3三位出现重复位^运算
3=3^8^6^5^8^4^7 -> 3^6^5^4^7
2=2^7^5^4^7^3^8^6 -> 2^5^4^3^8^6
1=1^6^4^3^8^6^2^7^5 -> 1^4^3^8^2^7^5
算法中是采用(h>>>7)而不是(h>>>8)的算法,应该是考虑1、2、3三位出现重复位^运算的情况。使得最低位上原hashCode的8位都参与了^运算,所以在table.length为默认值16的情况下面,hashCode任意位的变化基本都能反应到最终hash table 定位算法中,这种情况下只有原hashCode第3位高1位变化不会反应到结果中,即:0x7FFFF7FF的i=15。
- 大小: 238.6 KB
分享到:
相关推荐
hashmap中hash函数的构造问题,提供了各种构造方法。以及比较函数的构造 挺适合入门学习的
详细分析HashMap的存储原理,key值的hash地址以及扩容
HashMap源码分析
官方
通过 HashMap、HashSet 的源代码分析其 Hash 存储机制1
结合Java的HashMap中的一些优点,改进了C++ 的hash_map。 详细说明见我的博客:http://blog.csdn.net/mdj67887500/article/details/6907702
java1.8 HashMap用的是数组+链表+红黑树实现的,采用尾插法实现的,解决了死循环的问题,今天分析的就是1.8 // 初始容量为16 static final int DEFAULT_INITIAL_CAPACITY = 1 <>> 16); } /** * Implements ...
liballoc 中的 hashmap 默认使用 SipHash,它并没有我们想要的那么快。在编译器中,我们并不真正担心 DOS 尝试,因此我们使用快速非加密哈希。 这与 Firefox 使用的算法相同——它是一种不基于任何广为人知的算法的...
2.Hashtable中的方法是同步的,而HashMap中的方法在缺省情况下是非同步的。即是说,在多线程应用程序中,不用专门的操作就安全地可以使用Hashtable了;而对于HashMap,则需要额外的同步机制。但HashMap的同步问题可...
Java SE程序 HashMap类Java SE...HashMap类Java SE程序 HashMap类Java SE程序 HashMap类Java SE程序 HashMap类Java SE程序 HashMap类Java SE程序 HashMap类Java SE程序 HashMap类Java SE程序 HashMap类Java SE程序 Hash
深入理解hashmap、hash算法、理解加载因子、扩容以及get、put方法
看完这篇 HashMap,和面试官扯皮就没问题了 - HashMap 概述 - HashMap 和 HashTable 的区别 - 相同点 - 不同点 - HashMap 和 HashSet 的区别 ... - HashMap 中的移除方法 - 关于 HashMap 的面
HashMap是一个散列桶(数组和链表),它存储的内容是键值对(key-value)映射HashMap采用了...而Hashtable则不能(原因就是equlas()方法需要对象,因为HashMap是后出的API经过处理才可以)2、HashMap的工作原理是什么?
HashMap 的 put 方法分析六.HashMap扩容机制七.HashMap线程安全性 一.HashMap是什么 HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。 HashMap是一个用于存储Key-Value键值对的集合,每一个...
C语言实现hashMap,包含创建hashMap、插入hashMap、查找hashMap、删除hashMap,已经若干经典的hash函数。文章链接:https://blog.csdn.net/sxf1061700625/article/details/109594495
对HashMap扩容时重新计算旧数组元素在新数组地址的rehash方法中的(e.hash&oldCap)==0算法推导
首先,我们了解一下HashMap的底层结构历史,在JDK1.8之前采用的是数组+链表的数据结构来存储数据,是不是觉得很熟悉,没错这玩意在1.8之前的结构就和HashTable一样都是采用数组+链表,同样也是通过链地址法(这里简称...
本文档主要讲述的是java中HashMap详解;HashMap和HashSet是Java Collection Framework的两个...虽然HashMap和HashSet实现的接口规范不同,但它们底层的Hash存储机制完全一样,甚至HashSet本身就采用HashMap来实现的。
Create Hash map and Hash function
从一个公司的项目中提取的一个基于共享内存的hashMap,vector,list等的相关实现,应用与游戏服务器的数据保存与访问