HashMap存储结构浅析

什么是hashcode
    分析HashMap之前先介绍下什么Hashcode(散列码)。它是一个int，每个对象都会有一个hashcode，它在内存的存放位置是放在对象的头部（对象头部存放的信息有hashcode，指向Class的引用，和一些有关垃圾回收信息）。具体如何生成hashcode，这个相当复杂，由于我们的主题是“浅析”，所以不深入探讨。有个问题需要讲的是，如果在你的类中覆盖了Object的equals(Object)方法，那么你必须覆盖hashCode方法，不然，当你使用HashMap，HashSet，HashTable时会出现问题。具体原因下文会详细描述。
String类的hashcode
    String类重写了Object类中的equals和hashCode方法，原因很简单，Object中的equals方法是指比较两个对象是不是指向同一个引用对象，而String类指需要比较内容相不相等就可以了。所以String覆盖了equals方法，同时覆盖了hashCode方法。这里需要提一下Object规范里规定：如果两个对象根据equals(Object)方式是相等的，那么这两个对象的hashCode一定要相等。
String中的hashcode算法很简单如下：

for (int i = 0; i < len; i++) {
                h = 31*h + val[off++];
            }

Val是一个char[]，存放的是字符串的各个字符；Len是字符串长度；off从0开始；h从0开始。比如一个字符串“abc”(a的ascii码是97)，它的hashcode算法是：
h = 31 * 0 + 97 ==> h = 97;
h = 31 * 97 + 98 ==> h = 3105;
h = 31 * 3105 + 99 ==> h = 96354;
所以“abc”的hashCode就是96354
存储方式
    列表的存储方式是基于数组，如下图：


    链表的存储方式是基于指针，如下图：（单向链表）


    HashMap的存储方式是上面两种的结合，如下图：


HashMap的存取
    HashMap的功能是通过“键(key)”能够快速的找到“值”。下面我们分析下HashMap存数据的基本流程：
    1、 当调用put(key,value)时，首先获取key的hashcode，int hash = key.hashCode();
    2、 再把hash通过一下运算得到一个int h.
hash ^= (hash >>> 20) ^ (hash >>> 12);
int h = hash ^ (hash >>> 7) ^ (hash >>> 4);
为什么要经过这样的运算呢？这就是HashMap的高明之处。先看个例子，一个十进制数32768(二进制1000 0000 0000 0000)，经过上述公式运算之后的结果是35080(二进制1000 1001 0000 1000)。看出来了吗？或许这样还看不出什么，再举个数字61440(二进制1111 0000 0000 0000)，运算结果是65263(二进制1111 1110 1110 1111)，现在应该很明显了，它的目的是让“1”变的均匀一点，散列的本意就是要尽量均匀分布。那这样有什么意义呢？看第3步。
    3、 得到h之后，把h与HashMap的承载量（HashMap的默认承载量length是16，可以自动变长。在构造HashMap的时候也可以指定一个长度。这个承载量就是上图所描述的数组的长度。）进行逻辑与运算，即 h & (length-1)，这样得到的结果就是一个比length小的正数，我们把这个值叫做index。其实这个index就是索引将要插入的值在数组中的位置。第2步那个算法的意义就是希望能够得出均匀的index，这是HashTable的改进，HashTable中的算法只是把key的hashcode与length相除取余，即hash % length，这样有可能会造成index分布不均匀。还有一点需要说明，HashMap的键可以为null，它的值是放在数组的第一个位置。
    4、 我们用table[index]表示已经找到的元素需要存储的位置。先判断该位置上有没有元素（这个元素是HashMap内部定义的一个类Entity，基本结构它包含三个类，key，value和指向下一个Entity的next）,没有的话就创建一个Entity<K,V>对象，在table[index]位置上插入，这样插入结束；如果有的话，通过链表的遍历方式去逐个遍历，看看有没有已经存在的key，有的话用新的value替换老的value；如果没有，则在table[index]插入该Entity，把原来在table[index]位置上的Entity赋值给新的Entity的next，这样插入结束。
再回头看看前面提到的为什么覆盖了equals方法之后一定要覆盖hashCode方法，很简单，比如，String a = new String(“abc”);String b = new String(“abc”);如果不覆盖hashCode的话，那么a和b的hashCode就会不同，把这两个类当做key存到HashMap中的话就会出现问题，就会和key的唯一性相矛盾。

    HashMap取的过程也类似。太累了，不写了。赶紧结束。
    文中可能会有错误的地方请指出，谢谢！

评论

25 楼 无根V稻草 2011-03-30  

支持，要是能再详细点就好了

24 楼 flyingpig4 2011-03-30  

pengmj 写道

什么是hashcode
    分析HashMap之前先介绍下什么Hashcode(散列码)。它是一个int，每个对象都会有一个hashcode，它在内存的存放位置是放在对象的头部（对象头部存放的信息有hashcode，指向Class的引用，和一些有关垃圾回收信息）。具体如何生成hashcode，这个相当复杂，由于我们的主题是“浅析”，所以不深入探讨。有个问题需要讲的是，如果在你的类中覆盖了Object的equals(Object)方法，那么你必须覆盖hashCode方法，不然，当你使用HashMap，HashSet，HashTable时会出现问题。具体原因下文会详细描述。
String类的hashcode
    String类重写了Object类中的equals和hashCode方法，原因很简单，Object中的equals方法是指比较两个对象是不是指向同一个引用对象，而String类指需要比较内容相不相等就可以了。所以String覆盖了equals方法，同时覆盖了hashCode方法。这里需要提一下Object规范里规定：如果两个对象根据equals(Object)方式是相等的，那么这两个对象的hashCode一定要相等。
String中的hashcode算法很简单如下：

for (int i = 0; i < len; i++) {
                h = 31*h + val[off++];
            }

Val是一个char[]，存放的是字符串的各个字符；Len是字符串长度；off从0开始；h从0开始。比如一个字符串“abc”(a的ascii码是97)，它的hashcode算法是：
h = 31 * 0 + 97 ==> h = 97;
h = 31 * 97 + 98 ==> h = 3105;
h = 31 * 3105 + 99 ==> h = 96354;
所以“abc”的hashCode就是96354
存储方式
    列表的存储方式是基于数组，如下图：


    链表的存储方式是基于指针，如下图：（单向链表）


    HashMap的存储方式是上面两种的结合，如下图：


HashMap的存取
    HashMap的功能是通过“键(key)”能够快速的找到“值”。下面我们分析下HashMap存数据的基本流程：
    1、 当调用put(key,value)时，首先获取key的hashcode，int hash = key.hashCode();
    2、 再把hash通过一下运算得到一个int h.
hash ^= (hash >>> 20) ^ (hash >>> 12);
int h = hash ^ (hash >>> 7) ^ (hash >>> 4);
为什么要经过这样的运算呢？这就是HashMap的高明之处。先看个例子，一个十进制数32768(二进制1000 0000 0000 0000)，经过上述公式运算之后的结果是35080(二进制1000 1001 0000 1000)。看出来了吗？或许这样还看不出什么，再举个数字61440(二进制1111 0000 0000 0000)，运算结果是65263(二进制1111 1110 1110 1111)，现在应该很明显了，它的目的是让“1”变的均匀一点，散列的本意就是要尽量均匀分布。那这样有什么意义呢？看第3步。
    3、 得到h之后，把h与HashMap的承载量（HashMap的默认承载量length是16，可以自动变长。在构造HashMap的时候也可以指定一个长度。这个承载量就是上图所描述的数组的长度。）进行逻辑与运算，即 h & (length-1)，这样得到的结果就是一个比length小的正数，我们把这个值叫做index。其实这个index就是索引将要插入的值在数组中的位置。第2步那个算法的意义就是希望能够得出均匀的index，这是HashTable的改进，HashTable中的算法只是把key的hashcode与length相除取余，即hash % length，这样有可能会造成index分布不均匀。还有一点需要说明，HashMap的键可以为null，它的值是放在数组的第一个位置。
    4、 我们用table[index]表示已经找到的元素需要存储的位置。先判断该位置上有没有元素（这个元素是HashMap内部定义的一个类Entity，基本结构它包含三个类，key，value和指向下一个Entity的next）,没有的话就创建一个Entity<K,V>对象，在table[index]位置上插入，这样插入结束；如果有的话，通过链表的遍历方式去逐个遍历，看看有没有已经存在的key，有的话用新的value替换老的value；如果没有，则在table[index]插入该Entity，把原来在table[index]位置上的Entity赋值给新的Entity的next，这样插入结束。
再回头看看前面提到的为什么覆盖了equals方法之后一定要覆盖hashCode方法，很简单，比如，String a = new String(“abc”);String b = new String(“abc”);如果不覆盖hashCode的话，那么a和b的hashCode就会不同，把这两个类当做key存到HashMap中的话就会出现问题，就会和key的唯一性相矛盾。

    HashMap取的过程也类似。太累了，不写了。赶紧结束。
    文中可能会有错误的地方请指出，谢谢！

23 楼 pengmj 2010-12-13  

hangdian_123 写道

不好意思，还没怎么发过言。我一直有个疑惑，想请问一下楼主。
String 类的hashcode的生成函数中
for (int i = 0; i < len; i++) { 
                h = 31*h + val[off++]; 
            } 
为什么要用31×h，这个数字是怎么算出来的或者说用31有什么好处？？忘请赐教

说实话我也不太清楚，下面的地址可以参考一下。
http://stackoverflow.com/questions/299304/why-does-javas-hashcode-in-string-use-31-as-a-multiplier

22 楼 xiaoxin5230 2010-12-13  

这里有篇对hashmap的深度解析。。。。大家可以看看http://www.oracle.com/technology/global/cn/pub/articles/maps1.html

21 楼 hangdian_123 2010-12-13  

不好意思，还没怎么发过言。我一直有个疑惑，想请问一下楼主。
String 类的hashcode的生成函数中
for (int i = 0; i < len; i++) { 
                h = 31*h + val[off++]; 
            } 
为什么要用31×h，这个数字是怎么算出来的或者说用31有什么好处？？忘请赐教

20 楼 hangdian_123 2010-12-13  

pengmj 写道

什么是hashcode
   
String中的hashcode算法很简单如下：

for (int i = 0; i < len; i++) {
                h = 31*h + val[off++];
            }

Val是一个char[]，存放的是字符串的各个字符；Len是字符串长度；off从0开始；h从0开始。比如一个字符串“abc”(a的ascii码是97)，它的hashcode算法是：
h = 31 * 0 + 97 ==> h = 97;
h = 31 * 97 + 98 ==> h = 3105;
h = 31 * 3105 + 99 ==> h = 96354;
所以“abc”的hashCode就是96354
存储方式

19 楼 laogao3232 2010-12-12  

以前看过，后来忘记了。
不过今天看这些讨论，又有新的收获，那就是hashmap的初始数组长度为什么是16.
受教了，另外增长为什么是倍数增长，原来都是有原因的啊。

18 楼 分离的北极熊 2010-12-12  

xieboxin 写道

pengmj 写道

什么是hashcode
    ....

这里需要提一下Object规范里规定：如果两个对象根据equals(Object)方式是相等的，那么这两个对象的hashCode一定要相等。

我查了一下API,Object里面的equals函数的说明以下：

指示其他某个对象是否与此对象“相等”。
equals 方法在非空对象引用上实现相等关系：

自反性：对于任何非空引用值 x，x.equals(x) 都应返回 true。
对称性：对于任何非空引用值 x 和 y，当且仅当 y.equals(x) 返回 true 时，x.equals(y) 才应返回 true。
传递性：对于任何非空引用值 x、y 和 z，如果 x.equals(y) 返回 true，并且 y.equals(z) 返回 true，那么 x.equals(z) 应返回 true。
一致性：对于任何非空引用值 x 和 y，多次调用 x.equals(y) 始终返回 true 或始终返回 false，前提是对象上 equals 比较中所用的信息没有被修改。
对于任何非空引用值 x，x.equals(null) 都应返回 false。
Object 类的 equals 方法实现对象上差别可能性最大的相等关系；即，对于任何非空引用值 x 和 y，当且仅当 x 和 y 引用同一个对象时，此方法才返回 true（x == y 具有值 true）。

注意：当此方法被重写时，通常有必要重写 hashCode 方法，以维护 hashCode 方法的常规协定，该协定声明相等对象必须具有相等的哈希码。
--------end-------


当equals==true时，个人认为hashcode可以不相同，但是在set中，是否判断为同一个对象不仅仅是通过equals方法，还要hashcode相同时，才判断为同一个对象。

把EFFECTIVE JAVA 的东西都搬出来了，回复也是如此COPY

17 楼 pengmj 2010-12-12  

liuzhiqiangruc 写道

Entry里面的key是什么？

Entry里面的key就是HashMap.put(k,v)中的“k”

16 楼 liuzhiqiangruc 2010-12-12  

Entry里面的key是什么？

15 楼 pengmj 2010-12-11  

worldterminator 写道

能讲讲怎么扩展hash表么， length增加了，根据 %length 计算 索引不到啊

你的意思是不是“如果HashTable中的数组的length自动扩展了，它里面已经存在的Entity如何索引是吗？”
HashTable里面有一个方法叫rehash(),它就是在length扩展的时候调用的，它的目的就是为里面已有的元素重新计算索引。
HashMap也类似，不过方法名叫resize()。
下面是HashTable中的rehash()

protected void rehash() {
	int oldCapacity = table.length;
	Entry[] oldMap = table;

	int newCapacity = oldCapacity * 2 + 1;
	Entry[] newMap = new Entry[newCapacity];

	modCount++;
	threshold = (int)(newCapacity * loadFactor);
	table = newMap;

	for (int i = oldCapacity ; i-- > 0 ;) {
	    for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
		Entry<K,V> e = old;
		old = old.next;

		int index = (e.hash & 0x7FFFFFFF) % newCapacity;
		e.next = newMap[index];
		newMap[index] = e;
	    }
	}
    }

threshold 是一个门槛，这个值是容量和加载因子的乘积，只要HashTable的size大于或等于threshold，那么这个容器就要进行扩展了。

14 楼 pengmj 2010-12-11  

RonQi 写道

楼主好文呢，这一个“浅析”让很多非计算机专业的同学补充了数据结构方面的知识，功德无量，
一个笔误

引用

基本结构它包含三个类，key，value和指向下一个Entity的next

楼主是说包含三个属性吧

还有些困惑一个小问题

引用

比如一个字符串“abc”(a的ascii码是97)，它的hashcode算法是：
h = 31 * 0 + 97 ==> h = 97;
h = 31 * 97 + 98 ==> h = 3105;
h = 31 * 3105 + 99 ==> h = 96354;
所以“abc”的hashCode就是96354

如果照这个方法算下去，对于稍长的字符串hashCode岂不是越来越大？很快int就放不下来了吧？

哈哈，你的问题很好。
不管它如何增大，它只取32位，所以说会出现负数。
hashcode的范围就是一个int的范围-2^32到2^31

13 楼 volking 2010-12-11  

数据结构一书有学过

12 楼 yangyi 2010-12-11  

这是不可能的，你看一下HashMap的代码实现，里面的MAX_CAPACITY是Integer Max Value的一半，也就是低位的部分不可能出现在符号位上

11 楼 xieboxin 2010-12-11  

pengmj 写道

什么是hashcode
    ....

这里需要提一下Object规范里规定：如果两个对象根据equals(Object)方式是相等的，那么这两个对象的hashCode一定要相等。

我查了一下API,Object里面的equals函数的说明以下：

指示其他某个对象是否与此对象“相等”。
equals 方法在非空对象引用上实现相等关系：

自反性：对于任何非空引用值 x，x.equals(x) 都应返回 true。
对称性：对于任何非空引用值 x 和 y，当且仅当 y.equals(x) 返回 true 时，x.equals(y) 才应返回 true。
传递性：对于任何非空引用值 x、y 和 z，如果 x.equals(y) 返回 true，并且 y.equals(z) 返回 true，那么 x.equals(z) 应返回 true。
一致性：对于任何非空引用值 x 和 y，多次调用 x.equals(y) 始终返回 true 或始终返回 false，前提是对象上 equals 比较中所用的信息没有被修改。
对于任何非空引用值 x，x.equals(null) 都应返回 false。
Object 类的 equals 方法实现对象上差别可能性最大的相等关系；即，对于任何非空引用值 x 和 y，当且仅当 x 和 y 引用同一个对象时，此方法才返回 true（x == y 具有值 true）。

注意：当此方法被重写时，通常有必要重写 hashCode 方法，以维护 hashCode 方法的常规协定，该协定声明相等对象必须具有相等的哈希码。
--------end-------


当equals==true时，个人认为hashcode可以不相同，但是在set中，是否判断为同一个对象不仅仅是通过equals方法，还要hashcode相同时，才判断为同一个对象。

10 楼 kjigh 2010-12-11  

yangyi 写道

...
length是基于power of 2的，所以length - 1的binary形式一定是一堆1，然后做与运算的结果就是取优化后哈希值的低位

原来如此，受教了
还有一点疑问，与运算会将计算出的哈希值转换成正的吧？上面有提到过溢出的问题，这样可能会导致二进制符号位为1，得出的值是负数，而进行与运算后会重新把哈希值的符号位变成0。是这样理解的么？

9 楼 yangyi 2010-12-11  

...
length是基于power of 2的，所以length - 1的binary形式一定是一堆1，然后做与运算的结果就是取优化后哈希值的低位

8 楼 smzd 2010-12-11  

RonQi 写道

楼主好文呢，这一个“浅析”让很多非计算机专业的同学补充了数据结构方面的知识，功德无量，
一个笔误

引用

基本结构它包含三个类，key，value和指向下一个Entity的next

楼主是说包含三个属性吧

还有些困惑一个小问题

引用

比如一个字符串“abc”(a的ascii码是97)，它的hashcode算法是：
h = 31 * 0 + 97 ==> h = 97;
h = 31 * 97 + 98 ==> h = 3105;
h = 31 * 3105 + 99 ==> h = 96354;
所以“abc”的hashCode就是96354

如果照这个方法算下去，对于稍长的字符串hashCode岂不是越来越大？很快int就放不下来了吧？

    public int hashCode() {
	int h = hash;
	if (h == 0) {
	    int off = offset;
	    char val[] = value;
	    int len = count;

            for (int i = 0; i < len; i++) {
                h = 31*h + val[off++];
            }
            hash = h;
        }
        return h;
    }

这是JDK源码，其实现就是这样的。至于放不下了并不会导致错误，溢出之后会丢掉一些信息，并且可能负负为正，这都有可能，但是不影响最终是一个int。并且可以看出，一个字符串的hash只会在用到的时候进行计算，且只计算一次，因为String是final的，是不可修改的

7 楼 worldterminator 2010-12-10  

能讲讲怎么扩展hash表么， length增加了，根据 %length 计算 索引不到啊

6 楼 RonQi 2010-12-10  

楼主好文呢，这一个“浅析”让很多非计算机专业的同学补充了数据结构方面的知识，功德无量，
一个笔误

引用

基本结构它包含三个类，key，value和指向下一个Entity的next

楼主是说包含三个属性吧

还有些困惑一个小问题

引用

比如一个字符串“abc”(a的ascii码是97)，它的hashcode算法是：
h = 31 * 0 + 97 ==> h = 97;
h = 31 * 97 + 98 ==> h = 3105;
h = 31 * 3105 + 99 ==> h = 96354;
所以“abc”的hashCode就是96354

如果照这个方法算下去，对于稍长的字符串hashCode岂不是越来越大？很快int就放不下来了吧？