从数据结构谈HashMap的实现

   最近看了下java的数据结构，同时又大致看了下hashMap的实现源码。下面和大家分享下hashMap的实现方式。
    hashMap用了一个名字为table的数组；还有若干个名字为entry的链表。看hashMap是如何应用这些数据结构的。用插入<key,value>举例：hashMap首先会通过key得到其hashCode，具体的hash函数就不说了（因为没多大意义）；然后把key的hashCode%table.length，就是拿hashCode模table数组大小，得到的余数就是key所在table数组中的下标（实际不是key的下标，是entry类）；但这样做有个问题，可能不同key却有一样的hasdCode，所以求余后其必然会得到相同的下标，那如何存储了？有两个办法，一种是利用开放地址法，就是说后来相同的hashCode去找先来hashCode所在下标的相邻下标。说的有点绕口，举个例子，比如<1,2>已经存在table数组的31的位置上了，再来一个<101,102>，其通过哈希后说：我也应该在31的位置上，但是table说，你后来，你再在31附近找个空位安置下吧。当然，具体怎么找，有规则的。另外一种方式就是链地址法，还是拿以上的例子说，<101,102>来到时，发现31的位置已经被占了，这时table说：<1,2>，你带下<101,102>；其实就是要<1,2>把<101,102>的引用存储了。但是<1,2>说：我怎么存储<101,102>的引用了，我没位置呀。所以table说：我给你们每个壳(entry类)吧，把你们都封装了；于是就有了entry类。

    那hashMap是使用那种方式了。先分析下开放地址和链地址法的优缺点。开放地址法一般需要2倍实际数据大小的空间，因为要留下一定的空闲地址去存储相同hashCode的<key,value>；并且查找相邻空闲地址也是一项比较费时间的任务；链地址法，就不需要2倍的空间（table数组），但是需要存储额外的信息，比如next信息；总体来看，链地址法好点（关键是节省了查找相邻地址的时间），所以，hashMap用的是链地址法。

    还有问题，hashMap为什么用数组存储index（hashCode%table.length）了，而不用链表了？因为数组有固定大小限制，而链表没有，而且map是没有限制大小的？这主要考虑了查找效率的问题。从前面的分析可以看到，因为key的hashCode%table.length直接做为entry的下标，所以其查询key的速度很快，只要O(1)的时间；如果是链表，要一个一个的排查对比，需要O(N)的时间；这之间的效率，相差太远了。所以，hashMap用了数组。

    最后一个问题，那数组的固定大小如何解决了？hashMap在每次插入数据前，会检查table数组的实际容量，如果实际容量>=初始容量，则把table的初始容量扩为原来的2倍，这时，就需要一个一个复制原来的数据项了，这是比较费时的！所以，初始容量很重要。

不错，目前很多开源框架在New Map的时候都预分配了Map容量。

1.hashmap的数据结构就是数组+链接
2.hashmap扩容的条件是实际容量>=初始容量的3/4 扩容两倍

没用过C++,想问一下，其它语言的API包中的HashTable也是用链表法吗？

有没有用二次散列法的？

像memcache又用的是什么方法？

个人认为用链表法是最简单直接和省空间。

能够研究源代码，楼主的精神值得学习。
给楼主提一个建议，发这个帖子之前先看看有没有别人发达更好的。
HashMap详细研究的，我看了至少两个了。。而且非常详细。
楼主的显得有些多余了。

百家之言取其精

我当然看了，他们可能从代码上分析hashMap的实现，我更关注从数据结构上面看hashmap的实现；而且，我更想和大家分享：hashmap为什么选择了数组和链表的数据结构实现，而不只是谈hashmap就是这样实现的。

看了楼主的介绍，随便说下以上标注的几个问题：

 

1. hash函数并非没有多大意义。

    hash(int h)方法根据key的hashCode重新计算一次散列。此算法加入了高位计算，防止低位不变，高位变化时，造成的hash冲突。

static int hash(int h) {  
     h ^= (h >>> 20) ^ (h >>> 12);  
     return h ^ (h >>> 7) ^ (h >>> 4);  
}

 

2. 我看JDK1.6中计算下标的代码是&运算，而非%运算，也可能我和楼主看的版本不同吧。

    在HashMap中，调用 indexFor(int h, int length) 方法来计算该对象应该保存在 table 数组的哪个索引处。indexFor(int h, int length) 方法的代码如下：

static int indexFor(int h, int length) {  
    return h & (length-1);  
} 

    这个方法非常巧妙，它通过 h & (table.length -1) 来得到该对象的保存位，而HashMap底层数组的长度总是 2 的 n 次方，这是HashMap在速度上的优化。

    在HashMap 构造器中有如下代码：

int capacity = 1;  
    while (capacity < initialCapacity)  
        capacity <<= 1;

    当length总是 2 的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。

 

3. HashMap中有加载因子loadFactor这个参数的定义，当HashMap中的元素个数超过数组大小*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。

 

我之前也写过几篇类似的文章，可供参考：深入Java集合学习系列：HashMap的实现原理。

 

[quote=&quot;zhangshixi&quot;]
3. HashMap中有加载因子loadFactor这个参数的定义，当HashMap中的元素个数超过数组大小*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。

我之前也写过几篇类似的文章，可供参考：深入Java集合学习系列：HashMap的实现原理。



请问你，如何预设hashmap的个数？？

在已知存入数据数目的情况下
将hashmap的值设置为
已知的数据*4/3+1这样
，比如你的已知数目是12,12*4/3+1为17不会超过17的3/4。


修改一下 刚才看了源码，他会用int转型的 所以你要保证的是你的结果可以整除4的。
但是你自己也是可以修改这个扩容因子的。