三顾java.util.HashMap -

贾懂凯

浏览: 121211 次
性别:
来自: 杭州

最近访客更多访客>>

huhuxin10

扛大炮的小鱼

cainiao1923

Gaberil

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

三顾java.util.HashMap

博客分类：

java collection frame

Java ITeye 算法 J#JDK

如果大家看java.util.HashMap的源码的话，无非需要注意以下几点：
1、k-v如何put/get/remove
2、扩容机制
3、实际使用时，如何配置自己的table初始容量和装载因子的大小
4、如果是并发环境需要注意同步
5、key的hashcode与equals方法重写
下面，我将就这几点来谈谈我的想法：

1、k-v如何put/get/remove
首先请看懂这篇文章：http://www.iteye.com/topic/754887
上面这篇文章对put/get以及讲解的还是比较详细的，我自认为很难有新的东西讲出来，所以不赘述了。
不过，我想补充几点:

a 关于HashMap源码中的index方法：

/**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

其实如果我们去实现的时候也可以用%来做，不过有一中说法说%效率没有位运算高，我做了一个测试：

int q=0;
    	
    	Long BeginTime=System.currentTimeMillis();//记录BeginTime  
    	for(int i=0;i<100000000;i++){
    		q=i & 10;
    		q=i & 10;
    		q=i & 10;
    		q=i & 10;
    		q=i & 10;
    		q=i & 10;
    		q=i & 10;
    		q=i & 10;
    		q=i & 10;
    		q=i & 10;
    		q=i & 10;
    		q=i & 10;
    		q=i & 10;
    		q=i & 10;
    		q=i & 10;
    		q=i & 10;
    		
    	}
    	Long EndTime=System.currentTimeMillis();//记录EndTime  
		System.out.println("insert time-->"+(EndTime - BeginTime));
    	
    	Long aBeginTime=System.currentTimeMillis();//记录BeginTime  
    	for(int i=0;i<100000000;i++){
    		q=i % 10;
    		q=i % 10;
    		q=i % 10;
    		q=i % 10;
    		q=i % 10;
    		q=i % 10;
    		q=i % 10;
    		q=i % 10;
    		q=i % 10;
    		q=i % 10;
    		q=i % 10;
    		q=i % 10;
    		q=i % 10;
    		q=i % 10;
    		q=i % 10;
    		q=i % 10;
    	}
    	Long aEndTime=System.currentTimeMillis();//记录EndTime  
		System.out.println("insert time-->"+(aEndTime - aBeginTime))；

得到一组对比数据：
8-6
11-9
8-6
13-6
11-6
11-6
11-10
10-11
……
调换两个循环的顺序，测试结果：
13-7
11-13
11-11
10-12
9-8
9-8
10-10
……
我迷糊了，从上面的测试看不出什么端倪，也许从汇编的高度这个问题可以解决。我的汇编不过关，望熟悉汇编的指点一下！

b 这个算法我不是很理解

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);
    }

这个方法到底何用，注解了说使得哈希码的重码率降低了，我还是不明白如何能使其降低呢？难道这个方法里的算法有什么精妙之处？大家发发言

2、扩容机制
排除对一般情况下对性能影响不大的key为null和相同key值相同的情况，判断是否扩容的时机在在每put一个新元素的时候都会调用addEntry函数，这个函数中总是会判断是否需要扩容，源代码是这样的：

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);
    }

这里，我假设你已经看过我上面附的链接的内容并且看得八九不离十了，所以，我不再详细解释上面源码中每一个符号的意思了。我们都知道table设计为2的幂的原因是为了index函数求需要插入的新k-v对的table数组中的索引位置能用上&（当然，设计为2的倍数是否还有别的深意我还看出来）。
附上resize何transfer的源码，方便大家看：

void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }

    /**
     * Transfers all entries from current table to newTable.
     */
    void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry<K,V> e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    Entry<K,V> next = e.next;
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }

可能在transfer方法装哦你的新老数组元素传递的时候比较难以理解，我也很难理解：put方法里新插入的元素如果出现hash collisions（哈希冲突）总是放在对应index链表的最前面的，而这里Rehashes的时候却又要在transfer方法里把链表的先后顺序给又调换过来。为什么transfer不直接写成：

void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry<K,V> e = src[j];
            if (e != null) {
                src[j] = null;
		int i = indexFor(e.hash, newCapacity);
                newTable[i] = e;//我直接把链表挂上去
	    }
        }
    }

3、实际使用时，如何配置自己的table初始容量和装载因子的大小
显然，按HashMap源码里的那种重构方法，如果reHash过多，显然会影响性能。所以为了防止过多的reHash，我们需要自己配置HashMap的装载因子loadFactor和初始的table容量capacity的大小（可以在构造函数里配或者调用方法配）。
很容易理解，如果我们已经知道我们使用的HashMap一般情况的存储在1W对以上，你给它一个默认的16的初始的table容量，默认reHash每次容量翻倍，这得重构多少次呀！（如果装载因子为1，还得要约5～6次）。但是如果我们的对HashMap的容量需求不是很大，你给它一个默认1W的容量，显然又浪费宝贵的空间了。至于这两个参数的选择可以自己去把握，甚至可以设定动态绑定：分析历史数据，找出规律，或者预测未来的走向找出规律。对HashMap这两个参数实现一个动态的调整。比如早上8点～9点A业务比较忙，它对应的HashMap可以提前多给些空间，而10点以后B业务使用的HashMap比较忙，A相对清闲，可以缩减A的空间给B。

4、如果是并发环境需要注意同步
显然，HashMap设计时就把它定义为不同布，或者是定义为同步工作交给程序员处理，也避免了同步带来的消耗，所以性能上还不错咯。
不过这就有些难为我们写代码的了，得自己控制呀。你得包装HashMap，不过我是不太敢用。可以尝试下java.util.concurrent包下面已经给我们做好同步的类，例如ConcurrentMap。这些类我下次大家再一起讨论吧

5、key的hashcode与equals方法重写
（这部分参考http://www.iteye.com/topic/539465中的一段然后扩展了下下）
首先，我们需要知道的是为什么需要改写key的这两方法：
正常的逻辑，这个问题可以转化为key的这两个方法在HashMap中哪里用到了（如果没用到改写干啥）。
我们ctrl+F：
put方法中第三行： int hash = hash(key.hashCode());也用到equals
putForCreate方法中第一行：int hash = (key == null) ? 0 : hash(key.hashCode());
get用到hashcode和equals
removeEntryForKey
removeMapping……
好多，不列举了。

我指针对put方法中用到的地方分析一下：

 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;
    }

int hash = hash(key.hashCode());这一行调用了key的hashCode方法。这个方法在Object里定义，jdk中某些类有重写这个方法。其实这个方法就是哈希算法啦。这个方法的设计原则设计上就是哈希算法的设计原则了：低重码率，高性能。

在改写equals方法的时候，需要满足以下三点：
(1) 自反性：就是说a.equals(a)必须为true。
(2) 对称性：就是说a.equals(b)=true的话，b.equals(a)也必须为true。
(3) 传递性：就是说a.equals(b)=true，并且b.equals(c)=true的话，a.equals(c)也必须为true。

于是，我们可以看出所谓的key相同，包括得满足e.hash == hash && ((k = e.key) == key || key.equals(k))为true。如果你hash值相等，而我们重写的equls方法判定不为true还是算key不同的。所以，小心设计你key的这两个方法吧。

补充：
1、补充一个链接，http://java-mzd.iteye.com/blog/827523。这篇blog列举的关于index方法和解决hash collisions的方法（虽然没有细讲，只是提到）。不过，我们能了解到原来解决hash collisions 可以不仅仅事jdk里提供的挂链一种，还有很多种，还是有帮助的。这篇文章有一个简单的HashMap的实现，精神可佳，不过个人觉得没有意义不大，而且实现代码比较……
2、关于HashMap的对象持久化我还没怎么用过，如果大家用过或有经验之谈，还望交流。

分享到：

引用类，WeakHashMap，以及让value自动回 ... | about eC(a OO programming lanauage based ...

2011-04-10 11:00
浏览 4304
评论(28)
论坛回复 / 浏览 (26 / 8732)
分类:编程语言
查看更多

28 楼贾懂凯 2011-11-27

schweigen 写道

贾懂凯写道

b 这个算法我不是很理解

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);
    }

这个方法到底何用，注解了说使得哈希码的重码率降低了，我还是不明白如何能使其降低呢？难道这个方法里的算法有什么精妙之处？大家发发言

这个是和indexFor 联合起来用的，因为HashMap 的table size 都是2 的倍数，而且index = h & (length - 1)，所以获得的index 的位置一般都取决于hash 的低位bits。你可以根据这个hash 算法移位看下，在低四位（也就是hashMap size 16）的情况下，这个int 里面的32bits总共有多少bits 参与了hash 运算，这就是最大可能保证了不冲突的情况

最近才看懂兄台这些话！
意思应该是：如果不经过hash()函数的运算，参与运算的位只是length-1中为1的低几位，如10110 11110 length=7的情况，只有低三位参与运算，这样两个值的index值便相同了，如果经过hash()函数就算，再调用indexfor求index，index的结果便不同。这也就是散列函数的设计目标：将key均匀和独立的分配到length长度的数组中，从而避免冲突collision的发生。

27 楼 fjjiaboming 2011-08-09

hash()
你需要去看
The Art Of Computer Programming Vol4 的某个位置

26 楼贾懂凯 2011-04-13

dopic 写道

看下C数据结构里面的Hash

个人觉得算法和数据结构应该无关实现语言。

25 楼贾懂凯 2011-04-13

引用

一时也看不出为什么用这个算法，也许经过测试这个算法误码率相对比较低并且各种情况下表现都比较好吧。

24 楼 schweigen 2011-04-13

贾懂凯写道

b 这个算法我不是很理解

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);
    }

这个方法到底何用，注解了说使得哈希码的重码率降低了，我还是不明白如何能使其降低呢？难道这个方法里的算法有什么精妙之处？大家发发言

23 楼 houzhe11 2011-04-13

要向楼主学习了。

22 楼 dopic 2011-04-13

看下C数据结构里面的Hash

21 楼 s929498110 2011-04-12

贾懂凯写道

s929498110 写道

贾懂凯写道

s929498110 写道

第三点

我感觉装载因子好像不推荐修改吧？如果一次性容量扩充比较大的话
可以自己设定扩充倍数数量级的

但是说实话。装载因子的使用经验几乎为零。。。现在读大二，实战经验也没多少。就不发表意见了。。。

如何自己设定扩充数量级？

下面的是我在HashMap中见到的方法，这个方法应该可以将原来为
2^n 的容量扩充为 2^m 的容量吧？说实话。。。没试过。。。

void resize(int newCapacity) {
		Entry[] oldTable = table;
		int oldCapacity = oldTable.length;
		if (oldCapacity == MAXIMUM_CAPACITY) {
			threshold = Integer.MAX_VALUE;
			return;
		}
		Entry[] newTable = new Entry[newCapacity];
		transfer(newTable);
		table = newTable;
		threshold = (int) (newCapacity * loadFactor);
	}

话说，我们系有一个女生叫贾轶凯，名字挺像的

容量扩充的倍数在方法addEntry里面写死了：
if (size++ >= threshold)
resize(2 * table.length);
为2

被封装起来了？没注意。。。不好意思啊
那样如果想使用估计得自己写一个子类实现了

20 楼 mercyblitz 2011-04-12

贾懂凯写道

s929498110 写道

贾懂凯写道

s929498110 写道

如何自己设定扩充数量级？

下面的是我在HashMap中见到的方法，这个方法应该可以将原来为
2^n 的容量扩充为 2^m 的容量吧？说实话。。。没试过。。。

void resize(int newCapacity) {
		Entry[] oldTable = table;
		int oldCapacity = oldTable.length;
		if (oldCapacity == MAXIMUM_CAPACITY) {
			threshold = Integer.MAX_VALUE;
			return;
		}
		Entry[] newTable = new Entry[newCapacity];
		transfer(newTable);
		table = newTable;
		threshold = (int) (newCapacity * loadFactor);
	}

话说，我们系有一个女生叫贾轶凯，名字挺像的

容量扩充的倍数在方法addEntry里面写死了：
if (size++ >= threshold)
resize(2 * table.length);
为2

没有必要自定义扩容呀，再说，写Java的人，很少关注算法，如果算法强的话，可以自行研究一套算法重新实现。

至于为什么是倍数是2，是为了防止hash 冲突。

19 楼 mercyblitz 2011-04-12

s929498110 写道

有用的，不过很难说清楚。

比如说，一个Map里面有很多元素，如果factor设置太小的话，内部的数组体积会少开辟空间，不过开辟新数组的次说也正增多了。这个还是需要估计大小才能决定。毕竟伐值内部大小，都可以算清楚。

18 楼 mercyblitz 2011-04-12

s929498110 写道

我最近也在看Collection的源码

卡在HashMap这里两天了。对里面的hash code算法不理解，就是LZ你说的那个hash静态方法。感觉HashMap很犀利，即有数组的优势，也有链表的特长

链表的是java.util.LinkedHashMap。

17 楼贾懂凯 2011-04-12

s929498110 写道

贾懂凯写道

s929498110 写道

如何自己设定扩充数量级？

下面的是我在HashMap中见到的方法，这个方法应该可以将原来为
2^n 的容量扩充为 2^m 的容量吧？说实话。。。没试过。。。

void resize(int newCapacity) {
		Entry[] oldTable = table;
		int oldCapacity = oldTable.length;
		if (oldCapacity == MAXIMUM_CAPACITY) {
			threshold = Integer.MAX_VALUE;
			return;
		}
		Entry[] newTable = new Entry[newCapacity];
		transfer(newTable);
		table = newTable;
		threshold = (int) (newCapacity * loadFactor);
	}

话说，我们系有一个女生叫贾轶凯，名字挺像的

容量扩充的倍数在方法addEntry里面写死了：
if (size++ >= threshold)
resize(2 * table.length);
为2

16 楼贾懂凯 2011-04-12

s929498110 写道

第四点

文档上的说明不好用吗？
Map m = Collections.synchronizedMap(new HashMap(...));
这样的一个HashMap线程不安全？表示完全没试过。。。仅存理论啊

得到SynchronizedMap的实例，这个类作为Collection内部类。你是否选用这种方法来处理同步问题，那就看你的选择了。

15 楼 s929498110 2011-04-12

晕。。。网络一卡
放了两遍。。。
零点了，睡觉！明天还得早起去实验室干活呢！

14 楼 s929498110 2011-04-11

贾懂凯写道

s929498110 写道

如何自己设定扩充数量级？

下面的是我在HashMap中见到的方法，这个方法应该可以将原来为
2^n 的容量扩充为 2^m 的容量吧？说实话。。。没试过。。。

void resize(int newCapacity) {
		Entry[] oldTable = table;
		int oldCapacity = oldTable.length;
		if (oldCapacity == MAXIMUM_CAPACITY) {
			threshold = Integer.MAX_VALUE;
			return;
		}
		Entry[] newTable = new Entry[newCapacity];
		transfer(newTable);
		table = newTable;
		threshold = (int) (newCapacity * loadFactor);
	}

话说，我们系有一个女生叫贾轶凯，名字挺像的

13 楼 s929498110 2011-04-11

贾懂凯写道

s929498110 写道

如何自己设定扩充数量级？

下面的是我在HashMap中见到的方法，这个方法应该可以将原来为
2^n 的容量扩充为 2^m 的容量吧？说实话。。。没试过。。。

void resize(int newCapacity) {
		Entry[] oldTable = table;
		int oldCapacity = oldTable.length;
		if (oldCapacity == MAXIMUM_CAPACITY) {
			threshold = Integer.MAX_VALUE;
			return;
		}
		Entry[] newTable = new Entry[newCapacity];
		transfer(newTable);
		table = newTable;
		threshold = (int) (newCapacity * loadFactor);
	}

话说，我们系有一个女生叫贾轶凯，名字挺像的

12 楼贾懂凯 2011-04-11

s929498110 写道

如何自己设定扩充数量级？

11 楼贾懂凯 2011-04-11

s929498110 写道

LZ

HashMap容器重新装载的方法，你修改的不正确

比如第一个key的哈希值是1234
第二个key的哈希值是12345
可能旧的容器的 table.length比较小， indexOf返回的值是一样的
而新的容器的table.length比较大， indexOf的返回值可能不一样！

也就是容器扩充之后，原来挂载点相同的Entry，新的挂载点可能不同

你感觉我说的对不？

赞同！

10 楼 s929498110 2011-04-11

第四点

文档上的说明不好用吗？
Map m = Collections.synchronizedMap(new HashMap(...));
这样的一个HashMap线程不安全？表示完全没试过。。。仅存理论啊

9 楼 s929498110 2011-04-11

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

三顾java.util.HashMap

评论

发表评论

相关推荐

最近访客 更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

三顾java.util.HashMap

评论

发表评论

相关推荐

并发容器——BlockingQueue相关类

简单比较HashMap和Hashtable

引用类，WeakHashMap，以及让value自动回收

集合框架（三）-专用set和map机制分析

再探集合框架(二)——深入源码看数据结构

从提高存取效率的角度深入“集合框架”

最近访客更多访客>>