三顾java.util.HashMap

如果大家看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的对象持久化我还没怎么用过，如果大家用过或有经验之谈，还望交流。

评论

8 楼 s929498110 2011-04-11  

LZ

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

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

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

你感觉我说的对不？

7 楼 s929498110 2011-04-11  

我最近也在看Collection的源码

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

6 楼 贾懂凯 2011-04-11  

heqingcool 写道

楼主相当的认真

不过还是有几点没搞明白（已经在文章里了列出了），发这个帖是希望大家讨论下下

5 楼 heqingcool 2011-04-11  

楼主相当的认真

4 楼 hh.凝望 2011-04-10  

不错，学习了

3 楼 lingyibin 2011-04-10  

哈哈，不错不错，顶一个！

2 楼 freewxy 2011-04-10  

楼主够认真，死磕很犀利啊

1 楼 沈冠军 2011-04-10  

写得很好，有空好好研究一下，现在要搞别的事情