Map的内部结构

常用的Map实现类

常见的Map实现类大概简单地列举几个。

• java.util.HashMap
• java.util.LinkedHashMap
• java.util.concurrent.ConcurrentHashMap
• java.util.concurrent.ConcurrentSkipListMap
• java.util.IdentityHashMap
• java.util.TreeMap
• java.util.Hashtable
• org.springframework.util.ConcurrentReferenceHashMap
• org.springframework.core.annotation.AnnotationAttributes extends LinkedHashMap
• org.springframework.ui.ModelMap extends LinkedHashMap
• com.mysql.jdbc.util.LRUCache extends LinkedHashMap

各种Map的数据结构，特点

• HashMap基于单向链表数组存储数据，默认容积16，但是在数组上并没有按照数组下标顺序存储，而是按Key的哈希值计算在数组中的位置。

/**
 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
 * (16) and the default load factor (0.75).
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

/**
 * Associates the specified value with the specified key in this map.
 * If the map previously contained a mapping for the key, the old
 * value is replaced.
 *
 * @param key key with which the specified value is to be associated
 * @param value value to be associated with the specified key
 * @return the previous value associated with <tt>key</tt>, or
 *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 *         (A <tt>null</tt> return can also indicate that the map
 *         previously associated <tt>null</tt> with <tt>key</tt>.)
 */
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

/**
 * Computes key.hashCode() and spreads (XORs) higher bits of hash
 * to lower.  Because the table uses power-of-two masking, sets of
 * hashes that vary only in bits above the current mask will
 * always collide. (Among known examples are sets of Float keys
 * holding consecutive whole numbers in small tables.)  So we
 * apply a transform that spreads the impact of higher bits
 * downward. There is a tradeoff between speed, utility, and
 * quality of bit-spreading. Because many common sets of hashes
 * are already reasonably distributed (so don't benefit from
 * spreading), and because we use trees to handle large sets of
 * collisions in bins, we just XOR some shifted bits in the
 * cheapest possible way to reduce systematic lossage, as well as
 * to incorporate impact of the highest bits that would otherwise
 * never be used in index calculations because of table bounds.
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

• LinkedHashMap基于双向链表存储数据。

/**
 * The head (eldest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> head;

/**
 * The tail (youngest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> tail;

• IdentityHashMap并不是常用的类，但也还是说一下，它基于Object数组存储，默认容积32，实例化时容积会在默认容积*2(64)，因为Key进行哈希后指定坐标位置存储，然后紧接着下个下标元素会存储对应的value；扩容算法为乘以2；另一个特点，它key在取哈希的时候是用的Object的原始算法，因此，只要KEY是不同的对象，内存地址不相同就可以存入两个相同内容的KEY,也就是Key可以重复。

/**
 * Constructs a new, empty identity hash map with a default expected
 * maximum size (21).
 */
public IdentityHashMap() {
    init(DEFAULT_CAPACITY);
}

/**
 * Initializes object to be an empty map with the specified initial
 * capacity, which is assumed to be a power of two between
 * MINIMUM_CAPACITY and MAXIMUM_CAPACITY inclusive.
 */
private void init(int initCapacity) {
    // assert (initCapacity & -initCapacity) == initCapacity; // power of 2
    // assert initCapacity >= MINIMUM_CAPACITY;
    // assert initCapacity <= MAXIMUM_CAPACITY;

    table = new Object[2 * initCapacity];
}
    
/**
 * Associates the specified value with the specified key in this identity
 * hash map.  If the map previously contained a mapping for the key, the
 * old value is replaced.
 *
 * @param key the key with which the specified value is to be associated
 * @param value the value to be associated with the specified key
 * @return the previous value associated with <tt>key</tt>, or
 *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 *         (A <tt>null</tt> return can also indicate that the map
 *         previously associated <tt>null</tt> with <tt>key</tt>.)
 * @see     Object#equals(Object)
 * @see     #get(Object)
 * @see     #containsKey(Object)
 */
public V put(K key, V value) {
    final Object k = maskNull(key);

    retryAfterResize: for (;;) {
        final Object[] tab = table;
        final int len = tab.length;
        int i = hash(k, len);

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

        final int s = size + 1;
        // Use optimized form of 3 * s.
        // Next capacity is len, 2 * current capacity.
        if (s + (s << 1) > len && resize(len))
            continue retryAfterResize;

        modCount++;
        tab[i] = k;
        tab[i + 1] = value;
        size = s;
        return null;
    }
}

/**
 * Returns index for Object x.
 */
private static int hash(Object x, int length) {
    int h = System.identityHashCode(x);
    // Multiply by -127, and left-shift to use least bit as part of hash
    return ((h << 1) - (h << 8)) & (length - 1);
}

• TreeMap基于红黑二叉树结构。左孩子节点存放比根节点小的，右孩子节点存放比根节点大的数据，因此，数据存储是有顺序的; 非线程安全，因此，若要在多线程同时处理时需要在外部做好同步操作处理。

/**
 * Associates the specified value with the specified key in this map.
 * If the map previously contained a mapping for the key, the old
 * value is replaced.
 *
 * @param key key with which the specified value is to be associated
 * @param value value to be associated with the specified key
 *
 * @return the previous value associated with {@code key}, or
 *         {@code null} if there was no mapping for {@code key}.
 *         (A {@code null} return can also indicate that the map
 *         previously associated {@code null} with {@code key}.)
 * @throws ClassCastException if the specified key cannot be compared
 *         with the keys currently in the map
 * @throws NullPointerException if the specified key is null
 *         and this map uses natural ordering, or its comparator
 *         does not permit null keys
 */
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();
        @SuppressWarnings("unchecked")
            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;
}

*

有趣的设计

• 接口中又定义了接口， Map.Entry定义了所有数据节点的结构和方法。

最后

由于是尝试分析，非常地浅显，欢迎各路大神对文中错误提出指正，对不足之处不吝赐教。