Java集合框架 - Map

作者: overflowedstack | 来源:发表于2021-05-22 15:36 被阅读0次

Java Map 框架

一. HashTable

1. 定义

哈希表的实现类，底层是将数据放在一个数组里。
当发生哈希碰撞时，形同哈希值的key会被放在一个链表里，数组里记录链表的头。

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {
......
    /**
     * The hash table data.
     */
    private transient Entry<?,?>[] table;
......
}

2. 初始化容量initial capacity 和负载因子load factor

Hashtable中有两个参数影响它的性能，初始化容量，以及负载因子。
HashTable的默认初始化容量为11，也就是说当HashTable被创建时，哈希散列桶的大小为11.
默认负载因子为0.75. 负载因子是衡量哈希散列桶有多满的指标。

 /* An instance of <code>Hashtable</code> has two parameters that affect its
 * performance: <i>initial capacity</i> and <i>load factor</i>.  The
 * <i>capacity</i> is the number of <i>buckets</i> in the hash table, and the
 * <i>initial capacity</i> is simply the capacity at the time the hash table
 * is created. Note that the hash table is <i>open</i>: in the case of a "hash
 * collision", a single bucket stores multiple entries, which must be searched
 * sequentially.  The <i>load factor</i> is a measure of how full the hash
 * table is allowed to get before its capacity is automatically increased.
 * The initial capacity and load factor parameters are merely hints to
 * the implementation.  The exact details as to when and whether the rehash
 * method is invoked are implementation-dependent.<p>
*/

    /**
     * Constructs a new, empty hashtable with a default initial capacity (11)
     * and load factor (0.75).
     */
    public Hashtable() {
        this(11, 0.75f);
    }

3. Hashtable是如何扩容的

先观察下，不断往hashtable里添加元素，hashtable的size和capacity的变化。

Hashtable size: 0 Hashtable capacity: 11
Hashtable size: 1 Hashtable capacity: 11
Hashtable size: 2 Hashtable capacity: 11
Hashtable size: 3 Hashtable capacity: 11
Hashtable size: 4 Hashtable capacity: 11
Hashtable size: 5 Hashtable capacity: 11
Hashtable size: 6 Hashtable capacity: 11
Hashtable size: 7 Hashtable capacity: 11
Hashtable size: 8 Hashtable capacity: 11

Hashtable size: 9 Hashtable capacity: 23
Hashtable size: 10 Hashtable capacity: 23
Hashtable size: 11 Hashtable capacity: 23
Hashtable size: 12 Hashtable capacity: 23
Hashtable size: 13 Hashtable capacity: 23
Hashtable size: 14 Hashtable capacity: 23
Hashtable size: 15 Hashtable capacity: 23
Hashtable size: 16 Hashtable capacity: 23
Hashtable size: 17 Hashtable capacity: 23

Hashtable size: 18 Hashtable capacity: 47
Hashtable size: 19 Hashtable capacity: 47
Hashtable size: 20 Hashtable capacity: 47

hashtable有一个变量叫做threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);

hash table 初始化capacity为11.
往里放第9个元素之前，threadhold为11*0.75 = 8.25。若放入第9个元素，那么hashtable中的元素count为9，大于threshold，触发扩容。新容量变成23.

放第18个元素之前，threadhold为23*0.75 = 17.25. 若放入第18个元素，那么hashtable中元素count为9，大于threshold，触发扩容。新容量变成47.

那么新容量是怎么计算的呢？
在rehash方法中，int newCapacity = (oldCapacity << 1) + 1;
初始化capacity为11，二进制1011.
扩容为二进制10111，即23.
再扩容为二进制101111，即47.
为什么新容量按照2n+1来计算呢？
因为计算数组下标的时候，是模除数组长度即capacity来算的。数组长度为素数或者奇数，计算出来的下标更均匀，不容易产生哈希碰撞。

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

4. Hashtable是线程安全的

Hashtable的方法用synchronized修饰，所以Hashtable是线程安全的。例如下面这些方法。
不过，也正是因为它是synchronized，导致Hashtable的效率很低。

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

public synchronized V get(Object key) {}

public synchronized V remove(Object key) {}

public synchronized int size() {}

5. put方法

Hashtable不允许key或者value为null。若为null，put的时候抛出NPE.

    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)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }

        addEntry(hash, key, value, index);
        return null;
    }

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

        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++;
    }

二. HashMap

1. 定义

底层实现是数组。
处理哈希冲突时，用到了链表存放冲突元素。如果链表长度大于8，会用红黑树类存放冲突元素，来提高查找效率。

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
......
    /**
     * The table, initialized on first use, and resized as
     * necessary. When allocated, length is always a power of two.
     * (We also tolerate length zero in some operations to allow
     * bootstrapping mechanics that are currently not needed.)
     */
    transient Node<K,V>[] table;
......
}

    /**
     * The bin count threshold for using a tree rather than list for a
     * bin.  Bins are converted to trees when adding an element to a
     * bin with at least this many nodes. The value must be greater
     * than 2 and should be at least 8 to mesh with assumptions in
     * tree removal about conversion back to plain bins upon
     * shrinkage.
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * The bin count threshold for untreeifying a (split) bin during a
     * resize operation. Should be less than TREEIFY_THRESHOLD, and at
     * most 6 to mesh with shrinkage detection under removal.
     */
    static final int UNTREEIFY_THRESHOLD = 6;

2. 初始化容量initial capacity 为16，负载因子load factor为0.75

    /**
     * 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
    }

3. HashMap扩容

每次扩容时，新容量是旧容量的两倍。

HashMap size: 0 HashMap capacity: 0
HashMap size: 1 HashMap capacity: 16
HashMap size: 2 HashMap capacity: 16
HashMap size: 3 HashMap capacity: 16
HashMap size: 4 HashMap capacity: 16
HashMap size: 5 HashMap capacity: 16
HashMap size: 6 HashMap capacity: 16
HashMap size: 7 HashMap capacity: 16
HashMap size: 8 HashMap capacity: 16
HashMap size: 9 HashMap capacity: 16
HashMap size: 10 HashMap capacity: 16
HashMap size: 11 HashMap capacity: 16
HashMap size: 12 HashMap capacity: 16
HashMap size: 13 HashMap capacity: 32
HashMap size: 14 HashMap capacity: 32
HashMap size: 15 HashMap capacity: 32
HashMap size: 16 HashMap capacity: 32
HashMap size: 17 HashMap capacity: 32
HashMap size: 18 HashMap capacity: 32
HashMap size: 19 HashMap capacity: 32
HashMap size: 20 HashMap capacity: 32

4. HashMap是线程不安全的。

5. HashMap的key或者value可以为null。

如果key为null，哈希值为0.

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

三. ConcurrentHashMap

1. 定义

底层由数组，链表，红黑树实现。
与hashmap相比，concurrenthashmap实现了线程安全。java8中用synchronized, volatile，cas等来做到线程安全的。对树的节点加锁，锁的粒度更小，效率更高。

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
    implements ConcurrentMap<K,V>, Serializable {
...
    /**
     * The array of bins. Lazily initialized upon first insertion.
     * Size is always a power of two. Accessed directly by iterators.
     */
    transient volatile Node<K,V>[] table;

    /**
     * The next table to use; non-null only while resizing.
     */
    private transient volatile Node<K,V>[] nextTable;
...
}

2. ConcurrentHashMap初始化大小及扩容

    /**
     * The load factor for this table. Overrides of this value in
     * constructors affect only the initial table capacity.  The
     * actual floating point value isn't normally used -- it is
     * simpler to use expressions such as {@code n - (n >>> 2)} for
     * the associated resizing threshold.
     */
    private static final float LOAD_FACTOR = 0.75f;

    /**
     * Creates a new, empty map with the default initial table size (16).
     */
    public ConcurrentHashMap() {
    }

ConcurrentHashMap size: 0 ConcurrentHashMap capacity: 0
ConcurrentHashMap size: 1 ConcurrentHashMap capacity: 16
ConcurrentHashMap size: 2 ConcurrentHashMap capacity: 16
ConcurrentHashMap size: 3 ConcurrentHashMap capacity: 16
ConcurrentHashMap size: 4 ConcurrentHashMap capacity: 16
ConcurrentHashMap size: 5 ConcurrentHashMap capacity: 16
ConcurrentHashMap size: 6 ConcurrentHashMap capacity: 16
ConcurrentHashMap size: 7 ConcurrentHashMap capacity: 16
ConcurrentHashMap size: 8 ConcurrentHashMap capacity: 16
ConcurrentHashMap size: 9 ConcurrentHashMap capacity: 16
ConcurrentHashMap size: 10 ConcurrentHashMap capacity: 16
ConcurrentHashMap size: 11 ConcurrentHashMap capacity: 16
ConcurrentHashMap size: 12 ConcurrentHashMap capacity: 32
ConcurrentHashMap size: 13 ConcurrentHashMap capacity: 32
ConcurrentHashMap size: 14 ConcurrentHashMap capacity: 32
ConcurrentHashMap size: 15 ConcurrentHashMap capacity: 32
ConcurrentHashMap size: 16 ConcurrentHashMap capacity: 32
ConcurrentHashMap size: 17 ConcurrentHashMap capacity: 32
ConcurrentHashMap size: 18 ConcurrentHashMap capacity: 32
ConcurrentHashMap size: 19 ConcurrentHashMap capacity: 32
ConcurrentHashMap size: 20 ConcurrentHashMap capacity: 32

3. ConcurrentHashMap是线程安全的，并且效率比HashTable更高。

四. TreeMap

1. 定义

这是一个有序的map，基于红黑树实现。它依据key的默认比较器来排序，或者根据自定义的key的比较方法来排序。

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
    private final Comparator<? super K> comparator;

    private transient Entry<K,V> root;

    /**
     * Node in the Tree.  Doubles as a means to pass key-value pairs back to
     * user (see Map.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;

        /**
         * Make a new cell with given key, value, and parent, and with
         * {@code null} child links, and BLACK color.
         */
        Entry(K key, V value, Entry<K,V> parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }
}

2. put方法

由于红黑树是一种特殊的二叉搜索树，那么往treemap里put元素时，会有以下步骤：

拿着要插入的元素key，遍历红黑树
经过层层比较，找到元素的最终位置
放入元素
由于插入元素后，红黑树的定义被打破了，那么需要调整二叉树上的节点，让它再形成一颗红黑树。

Java集合框架 - Map

一. HashTable

1. 定义

2. 初始化容量initial capacity 和负载因子load factor

3. Hashtable是如何扩容的

4. Hashtable是线程安全的

5. put方法

二. HashMap

1. 定义

2. 初始化容量initial capacity 为16，负载因子load factor为0.75

3. HashMap扩容

4. HashMap是线程不安全的。

5. HashMap的key或者value可以为null。

三. ConcurrentHashMap

1. 定义

2. ConcurrentHashMap初始化大小及扩容

3. ConcurrentHashMap是线程安全的，并且效率比HashTable更高。

四. TreeMap

1. 定义

2. put方法

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

Java集合框架 - Map

一. HashTable

1. 定义

2. 初始化容量initial capacity 和 负载因子load factor

3. Hashtable是如何扩容的

4. Hashtable是线程安全的

5. put方法

二. HashMap

1. 定义

2. 初始化容量initial capacity 为16，负载因子load factor为0.75

3. HashMap扩容

4. HashMap是线程不安全的。

5. HashMap的key或者value可以为null。

三. ConcurrentHashMap

1. 定义

2. ConcurrentHashMap初始化大小及扩容

3. ConcurrentHashMap是线程安全的，并且效率比HashTable更高。

四. TreeMap

1. 定义

2. put方法

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

2. 初始化容量initial capacity 和负载因子load factor