【Java】Map总结和源码注释

前言

Map为一个Java中一个重要的数据结构，主要表示<key, value>的映射关系对。本文包括了相关Map数据结构的总结和源码的阅读注释。

HashMap

初始化，可以选择第二个初始化函数来设置装载能力threshold和装载系数loadFactor：

HashMap()
HashMap(int initialCapacity, float loadFactor)

HashMap中定义的一些常量：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

缺省的初始大小
static final int MAXIMUM_CAPACITY = 1 << 30;

最大限定大小，当超过这个值时，会resize()到Integer.MAX_VALUE
static final float DEFAULT_LOAD_FACTOR = 0.75f;

threshold = capacity*laodFactor

HashMap的大小始终为2的倍数，若插入时超过threshold时，会调用resize()来自动将大小扩大一倍。

值在Node<K,V>[] table中的定位方式为(n-1)&hash(key)

基本方法：

V put(K key, V value)：若key不存在，则插入；若key存在，则更新value值，返回旧的value
V putIfAbsent(K key, V value)
V get(Object key)：get不存在的key时会返回null，需要注意NullPointerException
int size()

遍历方式

forEach(lambda)通过lambda表达式进行遍历

entrySet().iterator()

Iterator iter = map.entrySet().iterator();

while(iter.hasNext()){

	Map.Entry e = (Map.Entry)iter.next();

    key = e.getKey();

    value = e.getValue();

}

keySet().iterator()

Iterator iter = map.keySet().iterator();

while(iter.hasNext()){

    key = iter.next();

    value = map.get(key);

}

values().iterator()

`resize()`

final Node<K,V>[] resize() {

    Node<K,V>[] oldTab = table;

    int oldCap = (oldTab == null) ? 0 : oldTab.length;

    int oldThr = threshold;

    int newCap, newThr = 0;

    if (oldCap > 0) {

        if (oldCap >= MAXIMUM_CAPACITY) { // 旧的大小已经达到设置的最大值时不再增加，改变阈值

            threshold = Integer.MAX_VALUE;

            return oldTab;

        }

        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && // 新大小=旧大小*2

                 oldCap >= DEFAULT_INITIAL_CAPACITY)

            newThr = oldThr << 1; // 阈值也一起*2

    }

    else if (oldThr > 0) // initial capacity was placed in threshold

        newCap = oldThr;

    else {               // oldCap为0时处于初始化阶段，进行初始化

        newCap = DEFAULT_INITIAL_CAPACITY;

        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

    }

    if (newThr == 0) {

        float ft = (float)newCap * loadFactor;

        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?

                  (int)ft : Integer.MAX_VALUE);

    }

    threshold = newThr;

    @SuppressWarnings({"rawtypes","unchecked"})

    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

    table = newTab;

    if (oldTab != null) { // 将旧map移到新map中

        for (int j = 0; j < oldCap; ++j) {

            Node<K,V> e;

            if ((e = oldTab[j]) != null) {

                oldTab[j] = null; // 置为null值方便GC

                if (e.next == null) // 桶中没有链，直接赋值

                    newTab[e.hash & (newCap - 1)] = e;

                else if (e instanceof TreeNode) // 如果桶中为红黑树

                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

                else { // preserve order

                    Node<K,V> loHead = null, loTail = null;

                    Node<K,V> hiHead = null, hiTail = null;

                    Node<K,V> next;

                    do {

                        next = e.next;

                        if ((e.hash & oldCap) == 0) { // 若为真，则在原来位置不变

                            if (loTail == null)

                                loHead = e;

                            else

                                loTail.next = e;

                            loTail = e;

                        }

                        else {	// 为假时说明扩容后原链表中的节点位置发生了改变

                            if (hiTail == null)

                                hiHead = e;

                            else

                                hiTail.next = e;

                            hiTail = e;

                        }

                    } while ((e = next) != null);

                    if (loTail != null) {

                        loTail.next = null;

                        newTab[j] = loHead; // 原链表所在

                    }

                    if (hiTail != null) {

                        hiTail.next = null;

                        newTab[j + oldCap] = hiHead; // 扩容部分节点位置加上了oldCap

                    }

                }

            }

        }

    }

    return newTab;

}

冲突解决

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

               boolean evict) {

    Node<K,V>[] tab; Node<K,V> p; int n, i;

    if ((tab = table) == null || (n = tab.length) == 0)

        n = (tab = resize()).length; // 数组为空的情况

    if ((p = tab[i = (n - 1) & hash]) == null)

        tab[i] = newNode(hash, key, value, null); // 没有冲突直接放入

    else {

        Node<K,V> e; K k;

        if (p.hash == hash &&

            ((k = p.key) == key || (key != null && key.equals(k))))

            e = p;	// 有冲突但是key相同，则覆盖原来的值

        else if (p instanceof TreeNode)

            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 如果已经拉成红黑树则插入树中

        else {

            for (int binCount = 0; ; ++binCount) {

                if ((e = p.next) == null) {

                    p.next = newNode(hash, key, value, null); // 找到链表尾插入链表中

                    if (binCount >= TREEIFY_THRESHOLD - 1) // 如果桶的链长度超过阈值则拉成红黑树

                        treeifyBin(tab, hash);

                    break;

                }

                if (e.hash == hash &&

                    ((k = e.key) == key || (key != null && key.equals(k))))

                    break; // 在链中找到相同的key则覆盖其值

                p = e;

            }

        }

        if (e != null) { // existing mapping for key

            V oldValue = e.value;

            if (!onlyIfAbsent || oldValue == null)

                e.value = value;

            afterNodeAccess(e);

            return oldValue;

        }

    }

    ++modCount;

    if (++size > threshold)

        resize();

    afterNodeInsertion(evict);

    return null;

}

Hashtable

初始化函数：

public Hashtable() {

    this(11, 0.75f);

}

默认下initialCapacity = 11，loadFactor = 0.75。

插入操作put(K,V)

public synchronized V put(K key, V value) {

    // Make sure the value is not null

    if (value == null) {

        throw new NullPointerException();

    }

    // Makes sure the key is not already in the hashtable.

    Entry<?,?> tab[] = table;

    int hash = key.hashCode();

    int index = (hash & 0x7FFFFFFF) % tab.length;

    @SuppressWarnings("unchecked")

    Entry<K,V> entry = (Entry<K,V>)tab[index];

    for(; entry != null ; entry = entry.next) {

        if ((entry.hash == hash) && entry.key.equals(key)) { // 找到相同的key则覆盖原值

            V old = entry.value;

            entry.value = value;

            return old;

        }

    }

    addEntry(hash, key, value, index);

    return null;

}

Hashtable的hash寻址方法为(hash & 0x7FFFFFFF) % tab.length，当插入的key之前有值时返回旧值，否则返回null。

addEntry(hash, key, value, index)，当table的大小不够时，执行rehash()扩大table

private void addEntry(int hash, K key, V value, int index) {

    Entry<?,?> tab[] = table;

    if (count >= threshold) {

        // Rehash the table if the threshold is exceeded

        rehash();

        tab = table;

        hash = key.hashCode();

        index = (hash & 0x7FFFFFFF) % tab.length;

    }

    // Creates the new entry.

    @SuppressWarnings("unchecked")

    Entry<K,V> e = (Entry<K,V>) tab[index];

    tab[index] = new Entry<>(hash, key, value, e);

    count++;

    modCount++;

}

rehash():

protected void rehash() {

    int oldCapacity = table.length;

    Entry<?,?>[] oldMap = table;

    // overflow-conscious code

    int newCapacity = (oldCapacity << 1) + 1; // 新大小=原大小*2+1

    if (newCapacity - MAX_ARRAY_SIZE > 0) {

        if (oldCapacity == MAX_ARRAY_SIZE)

            // Keep running with MAX_ARRAY_SIZE buckets

            return;

        newCapacity = MAX_ARRAY_SIZE;

    }

    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

    modCount++;

    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1); // 更新阈值

    table = newMap;

    for (int i = oldCapacity ; i-- > 0 ;) { // 将旧map中的值一道新map

        for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {

            Entry<K,V> e = old;

            old = old.next;

            int index = (e.hash & 0x7FFFFFFF) % newCapacity;

            e.next = (Entry<K,V>)newMap[index];

            newMap[index] = e;

        }

    }

}

与HashMap的区别

HashMap 继承自AbstractMap类，Hashtable继承自Dictionary类
Hashtable中的方法均用sychronized关键字修饰，为线程安全
扩容方法不同，HashMap直接double，使得大小始终是2的倍数，Hashtable在double后加1
在table中的查找方式不同：HashMap为hash&(n-1)，Hashtable为(hash & 0x7FFFFFFF) % tab.length

TreeMap

TreeMap的本质是红黑树，红黑树是一种特殊的二叉查找树，所以TreeMap中的节点都是有序的。

TreeMap中节点Entry的定义为

static final class Entry<K,V> implements Map.Entry<K,V> {

    K key;

    V value;

    Entry<K,V> left;

    Entry<K,V> right;

    Entry<K,V> parent;

    boolean color = BLACK;

}

初始化函数：

public TreeMap() {

    comparator = null;

}

public TreeMap(Comparator<? super K> comparator) {

    this.comparator = comparator;

}

TreeMap支持自定义的比较器，若是使用空初始化函数，则默认为key的自然顺序

 /**

     * The comparator used to maintain order in this tree map, or

     * null if it uses the natural ordering of its keys.

     *

     * @serial

     */

private final Comparator<? super K> comparator;

插入操作put(K,V)

public V put(K key, V value) {

    Entry<K,V> t = root;

    if (t == null) { // root为空则直接new

        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) { // 自定义comparator时

        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);	// 如果key相等则直接覆盖value

        } while (t != null);

    }

    else {	// 使用key的comparable接口

        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); //找到相同的key则直接覆盖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;

}

插入后红黑树的自平衡过程:

private void fixAfterInsertion(Entry<K,V> x) {

    x.color = RED; // 设插入节点的颜色为红

    while (x != null && x != root && x.parent.color == RED) { // 当x.parent为黑时树已经平衡

        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { // x.parent是祖父节点的左子节点

            Entry<K,V> y = rightOf(parentOf(parentOf(x))); // x的uncle节点

            if (colorOf(y) == RED) { // uncle为红的时候recolor

                setColor(parentOf(x), BLACK);

                setColor(y, BLACK);

                setColor(parentOf(parentOf(x)), RED);

                x = parentOf(parentOf(x)); // 向上变色直到满足平衡条件

            } else { // uncle为黑的时候则需要rotate

                if (x == rightOf(parentOf(x))) { // 左右的情况，向左旋转

                    x = parentOf(x);

                    rotateLeft(x);

                }

                setColor(parentOf(x), BLACK);

                setColor(parentOf(parentOf(x)), RED);

                rotateRight(parentOf(parentOf(x)));

            }

        } else {

            Entry<K,V> y = leftOf(parentOf(parentOf(x)));

            if (colorOf(y) == RED) {

                setColor(parentOf(x), BLACK);

                setColor(y, BLACK);

                setColor(parentOf(parentOf(x)), RED);

                x = parentOf(parentOf(x));

            } else {

                if (x == leftOf(parentOf(x))) { // 右左的情况，向右旋转

                    x = parentOf(x);

                    rotateRight(x);

                }

                setColor(parentOf(x), BLACK);

                setColor(parentOf(parentOf(x)), RED);

                rotateLeft(parentOf(parentOf(x)));

            }

        }

    }

    root.color = BLACK;

}

如有不对请多指正

巴特西