定做化高效使用Map的一些经验技巧

2012-12-27

定制化高效使用Map的一些经验技巧Map是一种非常用的数据结构，在一些底层框架或者效率十分关键的地方也是十

定制化高效使用Map的一些经验技巧
Map是一种非常用的数据结构，在一些底层框架或者效率十分关键的地方也是十分常用的。我写这篇文章的意图就是把我关于高效使用map的一些经验技巧写下来，当然其中我的一些观点可能不对，如果有朋友发现有错误的地方，欢迎指正。

在Java中Map是什么呢？先说HashMap，java.util.HashMap这个类，就是一个链表数组，最简单的理解就是把key的hashCode % len得到所在链表的位置，然后在链表上挨个查找。

这个代码摘抄自JDK 6的java.util.HashMap，为了方便说明问题，有所删减。其中一些关键点，我都已经注释说明

public class HashMap<K,V> {// Entry是一个很标准的链表结构static class Entry<K,V> {final K key;V value;Entry<K,V> next;final int hash;}transient Entry[] table; // table就是一个链表数组transient int size;   public HashMap(int initialCapacity) {        // 注意，这里是性能的一个很关键地方，如果自行编写HashMap时，table.length不是2的n次方，性能会很容易很糟糕。        int capacity = 1;        while (capacity < initialCapacity)            capacity <<= 1;        table = new Entry[capacity];    }// get方法所做的事情包括hash、indexFor、链表遍历、链表中每个Entry.key的相等比较public V get(Object key) {    int hash = hash(key.hashCode()); // int index = indexFor(hash, table.length);     for (Entry<K,V> e = table[index]; e != null; e = e.next) { // 链表遍历        Object k;        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {            return e.value;}    }    return null;}    public V put(K key, V value) {        int hash = hash(key.hashCode());        int index = indexFor(hash, table.length);        for (Entry<K,V> e = table[index]; 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;                return oldValue;            }        }        addEntry(hash, key, value, index);        return null;    }    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); // 多个线程并发访问时，resize会调用transfer方法，而transfer方法会在某种情况下产生死循环。}    }static int hash(int h) {    h ^= (h >>> 20) ^ (h >>> 12);    return h ^ (h >>> 7) ^ (h >>> 4);}static int indexFor(int h, int length) {    return h & (length-1); // 这个比取模运算%速度快。}}

通过上面的代码和注释，我们基本能够了解HashMap是干啥的，他是一个很简单很常用的数据结构，本身HashMap的性能很好，但是某些场景下，我们还是对HashMap做定制化的处理，使得其更高效。

例如Key是int的场景，专门编写IntHashMap能够获得更高效的性能，中间能够减少Integer对象的产生，减轻GC负担，同时，hash函数和遍历时的equals也能省下不少动作。一个性能比较数据如下：

测试的代码：

final int COUNT = 1000 * 10;final int loopCount = 10000;HashMap<Object, Object> map = new HashMap<Object, Object>(); // IntHashMap测试时相对应是IntHashMapfor (int i = 0; i < loopCount; ++i) {for (int j = 0; j < COUNT; ++j) {if (map.get(j) == null) {map.put(j, value);}}}

结果：