在阅读JAVA中HashMap的源码时,以前数据结构学的都又回到脑海中,JAVA中的HashMap是"链表散列"的结构。有些收获点在此记录。
1. 基本结构Entry为 key-value,HashMap中的Entry<K,V>结构大致如下:
static class Entry<K,V> implements Map.Entry<K,V>{
final K key;
V value;
Entry<K,V> next;
final int hash;
.......
}
HashMap这里的Entry<K,V>相当于《数据结构》中节点node,Entry包含key(常量),value,hash(哈希值)和指向下一个Entry结构的引用。这么一来,一个Entry就相当于一个链表了。
2. HashMap本身的成员变量如下:
//The table, resized as necessary. Length MUST Always be a power of two.
transient Entry[] table;
(核心结构,table是一个Entry类型的数组,每一个元素都是Entry节点的链表。)
//The default initial capacity - MUST be a power of two.
static final int DEFAULT_INITIAL_CAPACITY = 16;
默认哈希表的初始容量,必须为2的多少次幂。为什么?正确答案:这是为了让元素在数组中分布均匀,而且为元素在数组中位置的计算速度优化做了铺垫。
考虑哈希表要添加一个元素,现在假设前提是某个Entry的hash值已经计算出来,那么我们都知道哈希表下一步就是根据这个hash值
把Entry放在table数组的某个位置。我们首先想到的就是把hash值对数组长度取模运算,这样一来,元素的分布相对来说是比较均匀的。但是,“模”运算的消耗还是比较大。我们看一下Java的牛人是怎么写的。Java源码中indexFor(int h, int length) 方法用来计算某Entry对象应该保存在 table 数组的哪个索引处,其代码如下:
static int indexFor(int h, int length) {
return h & (length-1);
}
这个h为Entry的哈希值,length为table数组的长度。
这个方法简单而又非常巧妙,它通过 h & (table.length -1) 来得到该对象的保存位,而HashMap底层数组的长度总是 2 的 n 次方,这里就是HashMap在速度上优化的一个点。在 HashMap 构造器中有如下代码:
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
这段代码保证初始化时HashMap的容量总是2的n次方,即底层数组的长度总是为2的n次方。
当length总是 2 的n次方时,h& (length-1)运算等价于对length取模,也就是h%length,但是&比%具有更高的效率。
这看上去很简单,其实比较有玄机的,我们举个例子来说明:
假设数组长度分别为15和16,优化后的hash码分别为8和9,那么&运算后的结果如下:
h & (table.length-1) hash table.length-1
8 & (15-1): 0100 & 1110 = 0100
9 & (15-1): 0101 & 1110 = 0100
--------------------------------------------------------------------------------------
8 & (16-1): 0100 & 1111 = 0100
9 & (16-1): 0101 & 1111 = 0101
从上面的例子中可以看出:当它们和15-1(1110)“与”的时候,产生了相同的结果,也就是说它们会定位到数组中的同一个位置上去,这就产生了碰撞,8和9会被放到数组中的同一个位置上形成链表,那么查询的时候就需要遍历这个链 表,得到8或者9,这样就降低了查询的效率。同时,我们也可以发现,当数组长度为15的时候,hash值会与15-1(1110)进行“与”,那么 最后一位永远是0,而0001,0011,0101,1001,1011,0111,1101这几个位置永远都不能存放元素了,空间浪费相当大,更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率,减慢了查询的效率!而当数组长度为16时,即为2的n次方时,2n-1得到的二进制数的每个位上的值都为1,这使得在低位上&时,得到的和原hash的低位相同,加之hash(int h)方法对key的hashCode的进一步优化,加入了高位计算,就使得只有相同的hash值的两个值才会被放到数组中的同一个位置上形成链表。
所以说,当数组长度为2的n次幂的时候,不同的key算得得index相同的几率较小,那么数据在数组上分布就比较均匀,也就是说碰撞的几率小,相对的,查询的时候就不用遍历某个位置上的链表,这样查询效率也就较高了。现在明白为什么MUST be a power of two 了吧。Java在这里充分考虑了速度的优化。
static final int MAXIMUM_CAPACITY = 1 << 30;
//The load factor used when none specified in constructor.
static final float DEFAULT_LOAD_FACTOR = 0.75f;
这个0.75是HashMap的负载因子,即数据结构做题的时候算的那个 “散列表的实际元素数目(n)/ 散列表的容量(m)”。
负载因子衡量的是一个散列表的空间的使用程度,负载因子越大表示散列表的装填程度越高,反之愈小。对于使用链表法的散列表来说,查找一个元素的平均时间是O(1+a),因此如果负载因子越大,对空间的利用更充分,然而后果是查找效率的降低;如果负载因子太小,那么散列表的数据将过于稀疏,对空间造成严重浪费。
//The number of key-value mappings contained in this map.
transient int size;
size 用于记录Entry的总数
//The next size value at which to resize (capacity * load factor).
int threshold;
threshold为Entry数目的上限,为容量和负载因子的乘积。当size超过了threshold时,将table进行扩容。
/**
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
transient volatile int modCount;
modCount记录对HashMap结构性修改的次数,modCount声明为volatile,保证线程之间修改的可见性。我们知道 java.util.HashMap不是线程安全的,因此如果在使用迭代器的过程中有其他线程修改了map,那么将抛出 ConcurrentModificationException,这就是所谓fail-fast策略。
未完待续。。。
参考 http://beyond99.blog.51cto.com/1469451/429789
分享到:
相关推荐
哈希计算器哈希计算器哈希计算器哈希计算器
对一批关键字集合采用开放定址哈希表的存储结构来建立相应的哈希表和完成查找过程。 (1) 熟练掌握哈希表的构造方法 (2) 理解哈希表与其他结构表的实质性差别。
输入:待哈希数据序列 功能要求:输出哈希方法和解决冲突的方法(文字输出),输出哈希表
////采用除留余数法定义哈希表,哈希表长度为10,哈希函数为H(key)=key%13。产生冲突时采用线性探测法实现下面要求的功能。 ////(1)初始化哈希表,置空哈希表 ////(2)在哈希表中查找元素 ////(3)在哈希表中...
哈希表的建立和查找哈希表的建立和查找哈希表的建立和查找哈希表的建立和查找
哈希查找: 1、 哈希表类的哈希函数采用除留余数法哈希函数; 2、 解决哈希冲突的函数采用开放定址法中的线性探察法。 3、 建立一个由10个数据元素组成的集合; 4、 测试哈希表长度m=13和m=11两种情况下的哈希表,并...
数据结构哈希表的实现,很值得初学者的学习与应用,看完代买能够掌握基本哈希表的应用
哈希表(散列表)和哈希查找方法,解决冲突方法教程
哈希
哈希树遍历 HashMap遍历和使用 HashMap遍历和使用
dwHashType = 0时计算的哈希值用于确定字符串在哈希表中的位置; dwHashType = 1,dwHashType = 2时计算的哈希值用于验证字符串 返回值:字符串的哈希值 */ unsigned long HashString(char *lpszString, ...
毕业论文:哈希函数的构造方法,仅供参考。毕业论文 哈希函数
数据结构中的哈希表,用c++写的,通过老师验证
参考网上博客的感知哈希算法的理论知识,实现基本的感知哈希算法,内有几张图片用来测试,程序可参考。
delphi哈希加密示例
模糊哈希的主要原理是,使用一个弱哈希计算文件局部内容,在特定条件下对文件进行分片,然后使用一个强哈希对文件每片计算哈希值,取这些值的一部分并连接起来,与分片条件一起构成一个模糊哈希结果。使用一个字符串...
//哈希查找法 #include #include #include<iomanip.h> #define datawidth 5 //设置数据显示宽度 #define arraymaxnum 21 //约定数组大小,0号单元默认不用,故用户数据可以接受20个 #define defaultnum 10 //约定...
/为班级30个人的姓名设计一个哈希表,假设姓名用汉语拼音表示。要求用除留余数法 构造哈希函数,用线性探测再散列法处理冲突,平均查找长度的上限为2。 编写数据结构和算法来实现。要求:将哈希函数和处理冲突方法...
哈希表课程设计数据结构实验报告——哈希表设计 针对某个集体中的人名设计一个哈希表,使得平均查找长度不超过R,完成相应的建立和查表程序. 1.2 人名为汉语拼音形式,最长不超过18个字符(如:庄双双 ...
两个完全免费而且体积小巧的哈希值计算程序, 支持字符串和文件的哈希值计算, 可以计算的哈希值类型包括:MD5、SHA1、CRC32, 把你需要计算哈希值的文件拖放到程序窗口中即可。 大小: 45380 字节 MD5: 229B43E34BC5...