HashMap和ConcurrentHashMap(jdk1.7/jdk1.8)

  • 2018-10-17
  • 105
  • 0
  • 1

一. 概述

        Map是非常经典的Key-Value 存储结构。

ConcurrentHashMap 是为了解决HashMap的并发问题,jdk1.7和jdk1.8又有哪些区别。

二.HashMap

        众所周知 HashMap 底层是基于【数组 + 链表组成的,不过在 jdk1.7 和 1.8 中具体实现稍有不同。

2.1 Base jdk1.7

2.1.1 jdk1.7 中的数据结构

结构图如下:

比较核心的几个成员变量:

 /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 16;

    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */
    transient Entry<K,V>[] table;

    /**
     * The number of key-value mappings contained in this map.
     */
    transient int size;

    /**
     * The next size value at which to resize (capacity * load factor).
     * @serial
     */
    int threshold;

    /**
     * The load factor for the hash table.
     *
     * @serial
     */
    final float loadFactor;

    /**
     * The number of times this HashMap has been structurally modified
     * Structural modifications are those that change the number of mappings in
     * the HashMap or otherwise modify its internal structure (e.g.,
     * rehash).  This field is used to make iterators on Collection-views of
     * the HashMap fail-fast.  (See ConcurrentModificationException).
     */
    transient int modCount;

分析:

  • 默认值 DEFAULT_INITIAL_CAPACITY 初始化桶大小,数组大小默认为16;
  • 默认值 MAXIMUM_CAPACITY 桶最大值,1 << 30表示往左位移30,就是2^30;
  • 默认值 DEFAULT_LOAD_FACTOR 默认的负载因子(0.75)float类型,支持修改但一般别去修改,要相信jdk的性能,设置这么大肯定有原因;
  • Entry<K,V>[] table, 真正存放数据的数组,链表结构(单向);
  • size, 是Map 存放数量的大小;
  • threshold ,阈值,扩容时候判断参考的变量(capacity * load_factor),比如默认就是16*0.75f=12;
  • loadFactor, 负载因子,可在初始化时显式指定;
  • modCount, HashMap结构修改的次数。

HashMap默认初始化:

public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        // Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;

        this.loadFactor = loadFactor;
        threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];
        useAltHashing = sun.misc.VM.isBooted() &&
                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        init();
    }

关键代码分析:

  • initialCapacity 不能超过默认最大值;
  • capacity 赋值为1, 如果指定初始化的 capacity < initialCapacity,则进行往左1位位移(capacity <<= 1),直到跳出while循环。往左位移1位的目的,是保证n^2这样进行扩容;
  • threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
  • 桶初始化 table = new Entry[capacity];

看一下数据存储结构:

transient Entry<K,V>[] table =  = new Entry[capacity];

结构定义:

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

        public final K getKey() {
            return key;
        }

        public final V getValue() {
            return value;
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

分析:Entry 是 HashMap 中的一个内部类,并且实现了Map.Entry<K,V>内部接口,几个属性也容易理解,分别是:

  • key 和 value;
  • 单向链表Entry<K,V> next;
  • hash 存放的是当前 key 的 hashcode。

分析完了基本结构,接下来看看其中重要的几个Method函数:

2.1.2 put方法

public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

2.1.3 get方法

public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }



2.2 Base jdk1.8

三.ConcurrentHashMap

3.1 Base jdk1.7

3.2 Base jdk1.8

四.思考题

为啥要用链表,有没有其他实现方式

存储密度

五.参考资料

HashMap? ConcurrentHashMap? 相信看完这篇没人能难住你!

评论

还没有任何评论,你来说两句吧