java中各种map

int32位 posted @ Apr 23, 2014 05:15:38 PM in java , 3612 阅读
转载请注明: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/若有错误,请多多指正,谢谢!
  • 无匹配
  • 无匹配
Emma 说:
2023年1月27日 02:30

Comment:HashMap is an efficient implementation of a Map in Java, providing excellent performance when dealing with key-value pairs. It uses a table array for engagement rings storing data, with each element being of type Entry, which is an internal class that holds the key and value of the pair. When inserting a value, the HashMap calculates the hash of the key, which is then used to find the corresponding entry in the array. In cases of hash conflicts, the zipper method is used to solve them, where all synonyms are stored in a singly linked list.


登录 *


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