java中各种map

int32位 posted @ Apr 23, 2014 05:15:38 PM in java , 3105 阅读
转载请注明:http://krystism.is-programmer.com/若有错误,请多多指正,谢谢!

java中有各种类型的map,每种类型的map实现方式不同,但接口都类似。所有的具体map类型必须实现Map接口或者其子类,AbstractMap实现了Map接口,并实现了Map接口的部分功能,因此一般具体Map类型只需继承AbstractMap就可以了。

1. HashMap

HashMap的实现方式是一个table数组,数组元素是一个Entry类型(java8 中是Node类型,Entry变成了一个接口),Entry是一个内部类,类似c++的pair类型,b实际保存key 和value值,当put一个值,即调用put时,先计算key的hash值,通过这个hash值找到对应的table数组索引,如果hash冲突,采用的是拉链法解决冲突,即把所有同义词(hash值相等)存储在一个单链表中,因此Entry可以看作是一个单链表,next指向下一个同义词。一个好的hash应该尽量减少同义词,因为当出现hash冲突时,在同义词中查找是线性查找,效率很低。put方法代码为(java 7):

 public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null) /* null的话直接存放在table[0] */
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length); /*找到table索引 */
        for (Entry<K,V> e = table[i]; e != null; e = e.next) { /* 查找是否已经存在相同的key */
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { /* 如果hash冲突且key一样,则返回旧值,替换成新值 */
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);  //插入新的Entry
        return null; /* 没有替换,则返回null */
    }

从源码中可以看出HashMap允许null作为key值,相当于null的hash为0。当key相同时,则覆盖原来的值,并返回旧的value。判断key是否相同是调用key的equals,因此如果使用自己的类作为key,必须重载equals方法,否则引用相同时才相等。求hash值并不是直接使用key的hashCode方法,而是自己内部实现的hash方法,hash方法会调用key的hashCode方法,这样能够减少hash冲突,且保证hash值能在指定返回内,而hashCode返回的值有可能超出table的索引范围。因此自定义类要作为key还必须覆盖hashCode方法,尽量返回一个素数。

2. IdentityHashMap

上面说了HashMap的key值是否相同是调用equals方法,而IdentityHashMap原理类似,但判断key是否相同运用 == 运算符,即判断是否同一个引用,实现上也有些不同,table不再是Entry,而是一个Object对象数组(不会存在hash冲突)。put时先计算key的hash值,通过hash值找到table数组的索引i,然后table[i]存储key,table[i + 1]存储value,代码为:

  public V put(K key, V value) {
        Object k = maskNull(key);
        Object[] tab = table;
        int len = tab.length;
        int i = hash(k, len);

        Object item;
        while ( (item = tab[i]) != null) {
            if (item == k) {
                V oldValue = (V) tab[i + 1];
                tab[i + 1] = value;
                return oldValue;
            }
            i = nextKeyIndex(i, len);
        }

        modCount++;
        tab[i] = k;
        tab[i + 1] = value;
        if (++size >= threshold)
            resize(len); // len == 2 * current capacity.
        return null;
    }

因此IdentityHashMap用于存储key值重复的map。

3. Hashtable

Hashtable和HashMap类似,不过put方法是同步的,使用synchronized锁住整个方法,支持并发控制,但现在已经废弃了,因为效率太低了,取而代之的是ConcurrentHashMap。

4. ConcurrentHashMap

取代Hashtable,和Hashtable不同,它是使用段加锁的方法实现并发,而不是同步整个方法。和HashMap不同,HashMap所有的Entry保存在一个table数组中,而ConcurrentHashMap是保存在不同的Segment(段)中,通过hash值先定位到Segment(其实也是一个Segment数组),然后只需对这个Segment(继承了ReentrantLock)加锁就可以了,不影响其他Segment。

5.LinkedHashMap

LinkedHashMap是HashMap的子类,因此具有HashMap的所有特点。与HashMap不同的是,HashMap不记录顺序,迭代时不保证任何顺序,而LinkedHashMap Entry使用了一个双链表记录顺序,并且Entry多了before 和after指针,迭代默认根据插入的顺序,可以设置成按最近访问顺序,put效率会比HashMap低,毕竟会有记录顺序的开销,但迭代速度会更快,直接遍历整个双向链表即可。

6. EnumMap

EnumMap使用java Enum类型作为key,相对简单且高效,内部还是使用了table,table的值是Object类型,put时就是根据key的值(原始值,一个整型数)作为索引,直接插入,table的长度就是key的枚举个数,其put代码为:

 public V put(K key, V value) {
        typeCheck(key);

        int index = key.ordinal();
        Object oldValue = vals[index];
        vals[index] = maskNull(value);
        if (oldValue == null)
            size++;
        return unmaskNull(oldValue);
    }

首先是类型检查,判断key是否是初始化的枚举类型(构造方法必须指定枚举类型的类类型),如果value是null则映射成内部的NULL(也是一个Object对象)。由此可见EnumMap是非常高效的,插入删除访问都是O(1),不存在冲突问题。

7. TreeMap

TreeMap和之前的Map类型使用的数据结构不一样,它实现的是SortedMap,即按照key值自然顺序排列的,内部使用的数据结构是红黑树,红黑树是一种类平衡二叉树(和传统严格的平衡树有点差别),put源码为:

 public V put(K key, V value) {
        Entry<K,V> t = root;
        if (t == null) {
            compare(key, key); // type (and possibly null) check

            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();
            Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        Entry<K,V> e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

首先判断根是否空,不为空则遍历红黑树,看是否已经存在key,存在则直接覆盖原来的值并返回旧值,否则插入新数据,并调整红黑树。

8. ConcurrentSkipListMap

ConcurrentSkipListMap也是默认根据key值排序的,并且支持高并发访问(比ConcurrentHashMap并发性能更好,存取速度相对比ConcurrentHashMap低)。不过实现并不是使用红黑树,而是跳表,跳表的性能和查找树性能相当。

题外话:

以上介绍了8中map,如何选择取决于实际应用,如果不关心顺序且是单线程操作,使用HashMap,如果需要key按顺序排列,则使用TreeMap, 如果需要关心插入顺序或者最近访问顺序,使用LinkedHashMap。当涉及并发访问时,不关心key顺序使用ConcurrentHashMap,高并发且关心key顺序,使用ConcurrentSkipListMap,尽量不要使用Hashtable。如果key是枚举类型,则使用EnumMap。另外几乎每个Map类型都有相对应的Set版本,Set一般就是继承自Map,Set的元素值作为Map的key,而Map的value默认为一个Object对象常量,当然其实Map的value是什么都无所谓。

转载请注明:http://krystism.is-programmer.com/若有错误,请多多指正,谢谢!
  • 无匹配
  • 无匹配

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter