HashMap

1、HashMap的特性

• HashMap存储键值对实现快速存取，允许null，key不能重复，若key重复则覆盖（调用put方法添加成功返回null，覆盖返回oldValue)
• 非同步，线程不安全
• 底层是hash表，不保证有序

2、Map的size和length的区别

size：当前map中存储的key-value对个数

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

/**
 * Returns the number of key-value mappings in this map.
 *
 * @return the number of key-value mappings in this map
 */
public int size() {
    return size;
}

/**
 * Returns <tt>true</tt> if this map contains no key-value mappings.
 *
 * @return <tt>true</tt> if this map contains no key-value mappings
 */
public boolean isEmpty() {
    return size == 0;
}

length：map中用来散列key的Node数组的长度（Node是HashMap的静态内部类），默认大小是16，总为2的幂次方，也是capacity

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 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 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;

final int capacity() {
    return (table != null) ? table.length :
    (threshold > 0) ? threshold :
    DEFAULT_INITIAL_CAPACITY;
}

3、数组的长度为什么总是2的n次方？

目的：散列高效（取模运算转为&操作），减少碰撞，达到存取高效

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);

散列高效：put方法中使用(length-1) & hash替换hash % length取模，当length为2ⁿ时成立

减少碰撞：二进制表示时，2ⁿ实际是1后面跟n个0，2ⁿ-1，为n个1

长度为9时，3 & (9-1) = 11 & 1000 = 0, 2 & (9-1) = 10 & 1000 = 0，都在0上，发生碰撞

长度为8时，3 & (8-1) = 11 & 111 = 11 = 3，2 & (8-1) = 10 & 111 = 10 = 2，不发生碰撞

即按位与时，每一位都能&1。若不考虑效率可直接取模，也不要求长度为2的幂次方。

4、数组的最大长度为什么是2³⁰？

补码表示的整数，范围为：-2^n-1 ≤ X ≤ (2^n-1 - 1)，int的最大值为2³¹-1，所以length的最大长度为2³⁰

当达到2³⁰ * 0.75的阈值时，数组不扩容，只是将阈值调整为Integer.MAX_VALUE，之后再put，碰撞频繁

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) { // length为2的30次方
                threshold = Integer.MAX_VALUE;  // 阈值增加到最大（size也是int类型）
                return oldTab; // 不做扩容，之后碰撞频繁
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // 使用带参构造器，threshold的值为最接近构造器设置的cap的2的幂次方
            newCap = oldThr; 
        else {               // 使用无参构造器，则threshold此时为0，对其赋值
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) { // 带参构造器的阈值为newCap，要重新赋值
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
    ...
}

若构造器传入的初始容量大于最大容量，则数组长度依然取为最大容量，即2³⁰

 public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY; // 取最大容量 2的30次方
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity); // 此时阈值为2的幂次方,put时进入resize，更新阈值
}

/**
 * Returns a power of two size for the given target capacity.
 根据给定容量cap，找到大于等于该值的最近的2的幂次值
 思想：转为二进制来看，将n的最高位后面全部变为1，然后+1,就得到2的幂次，如何让n的最高位后面全变成1，方法采用和最高位做或运算，再把已经变为1的高位右移，将次高位变为1，依次类推，将后面位全变成1
 */
static final int tableSizeFor(int cap) {
    int n = cap - 1; // 防止cap已经为2的幂次，若不减1，则会变为cap * 2
    n |= n >>> 1; // 最高的2位变为1
    n |= n >>> 2; // 最高的4位变为1
    n |= n >>> 4; // 最高的8位变为1
    n |= n >>> 8; // 高16位
    n |= n >>> 16; // 全部
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

5、为什么默认容量为16，load factor为0.75

• 容量必须是2的整数次幂：1，2，4，8，16，32...，8及以下，容易发生碰撞，32相对其他集合过大（ArrayList为10）
• load factor过小，频繁扩容，空间利用率低，过大，碰撞频繁，put的时间增加，空间利用率高，但查找成本提高（put\get）
• load factor=0.75，2的幂次方乘以0.75是个整数；其次，该值在工程实践中是一个相对友好的值
• 实时负载：size / length

6、为什么树的阈值是8，非树阈值是6？

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

JDK8引入红黑树结构，若桶中链表元素大于等于8时，链表转换为树结构，若桶中链表元素个数小于等于6时，树结构还原成链表，因为红黑树的平均查找长度为log(n)，长度为8时，平均查找长度为3，而链表平均查找长度为4，所以有转换为树的必要。链表长度若小于等于6，平均查找长度为3，与树相同，但是转换为树结构和生成树的时间并不会太短。

选择6和8，中间值7可以防止链表和树频繁转换，若只有8，则当一个hashmap不停的在8附近插入、删除元素，链表元素个数在8左右徘徊，就会频繁的发生树转链表，链表转树，效率会很低。

7、最小树形化阈值 MIN_TREEIFY_CAPACITY

/**
 * The smallest table capacity for which bins may be treeified.
 * (Otherwise the table is resized if too many nodes in a bin.)
 * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
 * between resizing and treeification thresholds.
 当数组长度 ≥ 该值时，才允许树形化链表，否则，当桶内链表元素太多时，直接扩容
 为避免进行扩容、树形化选择冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
 */
static final int MIN_TREEIFY_CAPACITY = 64;

put时，做了转树阈值判断

// ...
if ((e = p.next) == null) {
    p.next = newNode(hash, key, value, null);
    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
        treeifyBin(tab, hash);
    break;
}
// ...

树化方法内：根据最小树形化阈值判断是树化还是扩容

/**
 * Replaces all linked nodes in bin at index for given hash unless
 * table is too small, in which case resizes instead.
 */
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) // 数组长度小于最小树形化阈值，做扩容
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) { //树化
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

8、put方法源码分析

/**
 * 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>.)
 若key有关联的值，则返回旧值，若没有，则返回null（若key关联的value=null,则返回也为null）
 */
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

8.1 计算key的hash

若key=null，则为0，否则为key的hashcode值的高16位保留，低16位与高16位进行异或，得到的hash值中低16位中也有高位信息。高位信息被变相保留，参杂的元素多了，生成的hash值的随机性会增大。这种方法可以有效保护hash值的高位，有些数据计算出的hash值主要差距在高位，而hashmap的hash寻址是忽略容量以上高位的（取模），可以避免hash碰撞。

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

8.2 put过程

/**
 * Implements Map.put and related methods.
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
     */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // put第一个元素时，table=null，先进行扩容
    // 容量为默认16或构造器定义的cap（大于等于该值的最近的2的幂次方）
    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;
        // 判断key是否相同(和链表的第一个元素判断)
        // key的hash相同（一定相同，同一个桶）且key地址相同或key的queals方法返回true
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; // 记录旧值
        else if (p instanceof TreeNode) // 树结构
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else { // 链表，且第一个元素的key不同
            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;
                }
                // 判断e是否与新插入的key相同，相同则退出，更新旧值
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // 相同key存在，则更新value，返回旧值
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount; // hashmap结构修改的次数
    if (++size > threshold) // 插入后，再扩容
        resize();
    afterNodeInsertion(evict);
    return null;
}

① 执行hash(key)得到hash值，判断table是否为空，为空表明这是第一个元素插入，则先resize，初始默认16

② 若不需要初始化，则判断要插入节点的位置是否为空，也就是没有产生hash地址冲突，是则直接放入table

③ 否则产生了冲突，那么有两种情况：key相同，key不同

④ 如果p是TreeNode的实例，说明p下面是红黑树，需要在树中找到一个合适的位置插入

⑤ p下面的节点数未超过8，则以单向链表的形式存在，逐个往下判断：若下一个位为空，插入，且判断当前插入后容量超过8则转成红黑树，break；若下一个位有相等的hash值，则覆盖，break，返回oldvalue

⑥ 判断新插入这个值是否导致size已经超过了阈值，是则扩容后插入新值。

java7：新值插入到链表的最前面，先（判断）扩容后插入新值

java8：新值插入到链表的最后面，先插值再（判断）扩容

8.3 resize

• 时机：①第一次put；② 插入后达到阈值
• 策略：若构造器处传入了cap，则为threshold的值（2的幂次），若使用无参构造器，则默认16；扩容时为2倍
• rehash：因为是2倍扩容，则原hash值增加一个高位，若高位为0，则rehash的桶不变，若高位为1，则rehash的桶为 原index+原容量

/**
     * Initializes or doubles table size.  If null, allocates in
     * accord with initial capacity target held in field threshold.
     * Otherwise, because we are using power-of-two expansion, the
     * elements from each bin must either stay at same index, or move
     * with a power of two offset in the new table.
     *
     * @return the table
     */
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;
        }
        // 2倍扩容，阈值也乘2
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // 初始化：设置了初始容量
        newCap = oldThr;
    else {               // 初始化：未设置初始容量，使用默认的16
        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) { // 扩容：移数据
        for (int j = 0; j < oldCap; ++j) { // 处理每个桶
            Node<K,V> e;
            // 桶不为空
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null; // 原桶置空
                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 { // 链表，rehash
                    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) { // hash高位是0，桶序号不变
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {  // hash高位为1，桶序号为 原序号 + 原容量
                            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;
                    }
                }
            }
        }
    }
    return newTab;
}

8.4 put并发下问题

• table=null时，多线程插入第一个元素，同时resize，后为table赋值的线程覆盖了前一个table值，导致前面线程插入的数据丢失【现象：不发生扩容，丢失数据，没有key冲突或碰撞，偶现】

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

table = newTab; // resize 扩容时也有问题

• 两个线程插入的node数组下标一样，且该位置没有元素，则后执行的线程覆盖前面插入的元素【碰撞】

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

• 两个线程插入的链表是同一个，在尾部插入时，后面插入的可能覆盖前面插入的元素

if ((e = p.next) == null) {
    p.next = newNode(hash, key, value, null);
    //...
}

• 更新size大小时，同时写入，则size值错误

if (++size > threshold)
   resize();

9、get方法源码

当获取对象时，先计算key的hash值，找到对应的index，再通过键对象的equals()方法找到正确的键值对，然后返回值对象

/**
     * Returns the value to which the specified key is mapped,
     * or {@code null} if this map contains no mapping for the key.
     *
     * <p>More formally, if this map contains a mapping from a key
     * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
     * key.equals(k))}, then this method returns {@code v}; otherwise
     * it returns {@code null}.  (There can be at most one such mapping.)
     *
     * <p>A return value of {@code null} does not <i>necessarily</i>
     * indicate that the map contains no mapping for the key; it's also
     * possible that the map explicitly maps the key to {@code null}.
     * The {@link #containsKey containsKey} operation may be used to
     * distinguish these two cases.
     *
     * @see #put(Object, Object)
     */
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

/**
     * Implements Map.get and related methods.
     *
     * @param hash hash for key
     * @param key the key
     * @return the node, or null if none
     */
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) { // 找到对应桶
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k)))) // equals判断key
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode) // 树
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do { // 链表
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

10、hash碰撞

情况

• 两节点key相同（hash一定相同）
• 两节点key不同，hash函数的局限性导致hash值相同
• 两节点key不同，hash值不同，但hash值对数组长度取模后相同

解决办法

• 链地址法（hashmap采用），插入时间最有O(1)，最差O(n)

• 开放定址法：index(i) = (H(key) + di) mod m

  • 线性探测再散列： di = i
  • 二次探测再散列：di = 1², -1², 2², -2², ...
  • 随机探测再散列：di = 伪随机数列

• 建立公共溢出区，查找时先从基本表中查找，找不到再在溢出区查找

减少碰撞

• hashcode算法保证不相同的对象返回不同的hashcode，碰撞几率小，也不会频繁调用equals方法，提高hashmap性能
• 使用不可变的、声明为final的对象，采用合适的equals和hashcode方法，减少碰撞发生，不可变性使得能够缓存不同key的hashcode，提高整个获取对象的速度，使用string、Integer这类包装类作为key是很好的选择，因为string和Integer是final的，且重写了equals和hashcode。不可变性是必要的，因为要计算hashcode，要防止key值改变，若key值放入和获取时返回不同的hashcode，就不能从hashmap中找到想要的对象

hash攻击

通过请求大量key不同，但是hashCode相同的数据，让HashMap不断发生碰撞，硬生生的变成了SingleLinkedList。这样put/get性能就从O(1)变成了O(N)，CPU负载呈直线上升，形成了放大版DDOS的效果，这种方式就叫做hash攻击。在Java8中通过使用红黑树，提升了处理性能，可以一定程度的防御Hash攻击。

11、HashMap的数据结构

数组+链表+红黑树

数组：hash表，使定位index为O(1)

链表：解决hash冲突

红黑树：提高搜索性能（二分查找）O(logn)

11.1 为什么不用二叉查找树

二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢。

而红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，

引入红黑树就是为了查找数据快，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少，所以当长度大于8的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。

11.2 为什么不用平衡二叉树AVL

• 红黑树不追求"完全平衡"，即不像AVL那样要求节点的 |balFact| <= 1，它只要求部分达到平衡，但是提出了为节点增加颜色，红黑是用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决，而AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多。

• 就插入节点导致树失衡的情况，AVL和RB-Tree都是最多两次树旋转来实现复衡rebalance，旋转的量级是O(1)
  删除节点导致失衡，AVL需要维护从被删除节点到根节点root这条路径上所有节点的平衡，旋转的量级为O(logN)，而RB-Tree最多只需要旋转3次实现复衡，只需O(1)，所以说RB-Tree删除节点的rebalance的效率更高，开销更小！

• AVL的结构相较于RB-Tree更为平衡，插入和删除引起失衡，如2所述，RB-Tree复衡效率更高；当然，由于AVL高度平衡，因此AVL的Search效率更高啦。

• 针对插入和删除节点导致失衡后的rebalance操作，红黑树能够提供一个比较"便宜"的解决方案，降低开销，是对search，insert ，以及delete效率的折衷，总体来说，RB-Tree的统计性能高于AVL.

• 故引入RB-Tree是功能、性能、空间开销的折中结果。

  • AVL更平衡，结构上更加直观，时间效能针对读取而言更高；维护稍慢，空间开销较大。
  • 红黑树，读取略逊于AVL，维护强于AVL，空间开销与AVL类似，内容极多时略优于AVL，维护优于AVL。
    基本上主要的几种平衡树看来，红黑树有着良好的稳定性和完整的功能，性能表现也很不错，综合实力强

红黑树的查询性能略微逊色于AVL树，因为其比AVL树会稍微不平衡最多一层，也就是说红黑树的查询性能只比相同内容的AVL树最多多一次比较，但是，红黑树在插入和删除上优于AVL树，AVL树每次插入删除会进行大量的平衡度计算，而红黑树为了维持红黑性质所做的红黑变换和旋转的开销，相较于AVL树为了维持平衡的开销要小得多

总结：实际应用中，若搜索的次数远远大于插入和删除，那么选择AVL，如果搜索，插入删除次数几乎差不多，应该选择RB。

12、如何线程安全的使用HashMap

• HashMap map = Collections.synchronizeMap(new HashMap());

  synchronizedMap()方法返回一个SynchronizedMap类的对象，而在SynchronizedMap类中使用了synchronized来保证对Map的操作是线程安全的，故效率其实也不高。

  具体而言，该方法返回一个同步的Map，该Map封装了底层的HashMap的所有方法，使得底层的HashMap即使是在多线程的环境中也是安全的。

  通过这种方式实现线程安全，所有访问的线程都必须竞争同一把锁，不管是get还是put。好处是比较可靠，但代价就是性能会差一点

  package java.util;
  public class Collections {
      
  	public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
          return new SynchronizedMap<>(m);
      }
  
      /**
       * @serial include
       */
      private static class SynchronizedMap<K,V>
          implements Map<K,V>, Serializable {
          private static final long serialVersionUID = 1978198479659022715L;
  
          private final Map<K,V> m;     // Backing Map
          final Object      mutex;        // Object on which to synchronize
  
          SynchronizedMap(Map<K,V> m) {
              this.m = Objects.requireNonNull(m);
              mutex = this;
          }
  
          SynchronizedMap(Map<K,V> m, Object mutex) {
              this.m = m;
              this.mutex = mutex;
          }
  
          public int size() {
              synchronized (mutex) {return m.size();}
          }
          public boolean isEmpty() {
              synchronized (mutex) {return m.isEmpty();}
          }
          public boolean containsKey(Object key) {
              synchronized (mutex) {return m.containsKey(key);}
          }
          public boolean containsValue(Object value) {
              synchronized (mutex) {return m.containsValue(value);}
          }
          public V get(Object key) {
              synchronized (mutex) {return m.get(key);}
          }
          //...
      }
      //...
  }
  

• ConcurrentHashMap

  JDK8前，通过分段锁技术提高了并发的性能，首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。另外concurrenthashmap的get操作没有锁，是通过volatile关键字保证数据的内存可见性。所以性能提高很多。

  JDK8对ConcurrentHashmap也有了巨大的的升级，同样底层引入了红黑树，并且摒弃segment方式，采用新的CAS算法思路去实现线程安全，再次把ConcurrentHashmap的性能提升了一个台阶。但同样的，代码实现更加复杂了许多。

13、ConcurrentHashMap

JDK1.8的实现已经摒弃了Segment的概念，而是直接用Node数组+链表+红黑树的数据结构来实现，并发控制使用Synchronized和CAS来操作，整个看起来就像是优化过且线程安全的HashMap，虽然在JDK1.8中还能看到Segment的数据结构，但是已经简化了属性，只是为了兼容旧版本。

13.1 Node

value和next增加了volatile关键字，且不允许修改value值

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

    Node(int hash, K key, V val, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.val = val;
        this.next = next;
    }
    // 不允许修改value
    public final V setValue(V value) {
        throw new UnsupportedOperationException();
    }
    // ...
}

volatile：可见性

• volatile关键字为实例域的同步访问提供了一种免锁机制。如果一个域为volatile，那么编译器和虚拟机就知道该域是可能被另一个线程并发更新的。volatile变量不能提供原子性

• 如果一个字段被声明成volatile，java线程内存模型确保所有线程看到这个变量的值是一致的。因为它不会引起线程上下文的切换和调度

保证：

• 其他线程对变量的修改，可以及时反应在当前线程中；

• 确保当前线程对volatile变量的修改，能及时写回到共享内存中，并被其他线程所见（保证了不同线程对这个变量进行操作时的可见性，即一个线程修改了某个变量的值，这新值对其他线程来说是立即可见的）；

• 使用volatile声明的变量，编译器会保证其有序性（禁止进行指令重排序）。

• volatile不保证对变量操作的原子性。保证原子性操作采用synchronized、lock、AtomicInteger

13.2 CAS

CAS（Compare-And-Swap）算法保证数据的原子性

CAS算法是硬件对于并发操作共享数据的支持，包含了三个操作数：内存值 V、预估值 A、更新值 B，当且仅当V==A时，V=B，否则，将不会任何操作。CAS不放弃CPU，继续读取更新操作，效率更高

13.3 put方法源码

/**
 * Maps the specified key to the specified value in this table.
 * Neither the key nor the value can be null. 
 * 
 * <p>The value can be retrieved by calling the {@code get} method
 * with a key that is equal to the original key.
 *
 * @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}
 * @throws NullPointerException if the specified key or value is null
 */
public V put(K key, V value) {
    return putVal(key, value, false);
}

/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
    // key和value均不能为null
    if (key == null || value == null) throw new NullPointerException();
    // 计算hash值：(h ^ (h >>> 16)) & HASH_BITS  异或后与Integer.MAX_VALUE做与操作
    int hash = spread(key.hashCode()); 
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable(); // 根据容量大小初始化table（CAS）
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // 下标位置无元素，使用CAS插入
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        else if ((fh = f.hash) == MOVED) // 正在扩容，当前线程加入扩容
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            synchronized (f) { // 下标所在桶锁了
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) { // 链表
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            // 末尾插入
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) { // 树
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                              value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i); // 转树
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount); // 更新count值
    return null;
}

• key和value均不能为null
• 计算hash值，(h ^ (h >>> 16)) & HASH_BITS
• 若table为空，则初始化，使用CAS修改sizeCtl的值为-1，默认容量为16，初始化后，更新sizeCtl为阈值
• 若table插入的下标处无元素，使用CAS插入元素
• 若插入时，正在扩容，则加入扩容
• 将下表所在节点锁住，遍历链表或树，若存在key相同节点，则覆盖，记录旧值，否则，插入新节点
• 若达到转树阈值，则转树（有最小树化限制）
• CAS更新baseCount值，若需要则扩容

初始化table

/**
 * Table initialization and resizing control.  When negative, the
 * table is being initialized or resized: -1 for initialization,
 * else -(1 + the number of active resizing threads).  Otherwise,
 * when table is null, holds the initial table size to use upon
 * creation, or 0 for default. After initialization, holds the
 * next element count value upon which to resize the table.

 作为table初始化和扩容的控制，值为负时表示table正在初始化或扩容
 -1：初始化
 -N: N-1个线程正在进行扩容
 当table=null时，该值表示初始化大小，默认为0（带参构造器，选择大于等于入参的2的幂次方）
 table初始化后，表示需要扩容的阈值：table长度*0.75【类似于hashmap的阈值】
 */
private transient volatile int sizeCtl;  

/**
 * Initializes table, using the size recorded in sizeCtl.
 */
private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
        if ((sc = sizeCtl) < 0) // 有线程初始化中
            Thread.yield(); // lost initialization race; just spin
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { // 将sizeCtl改为-1
            try {
                if ((tab = table) == null || tab.length == 0) {
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    sc = n - (n >>> 2); // n * 0.75
                }
            } finally {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

compareAndSwapInt方法

public final native boolean compareAndSwapInt(java.lang.Object o, long l, int i, int i1);

o：将要修改的值的对象

l：对象在内存中偏移量为l的值，就是要修改的数据的值在内存中的偏移量，解和 o+l 找到要修改的值

i：期望内存中的值，这个值和 o + l 值比较，相同修改，返回true，否则返回false

i1：上一步相同，则将该值赋给 o + l 值，返回true

addCount

/**
 * Base counter value, used mainly when there is no contention,
 * but also as a fallback during table initialization
 * races. Updated via CAS.
 */
private transient volatile long baseCount;   

/**
 * Table of counter cells. When non-null, size is a power of 2.
 */
private transient volatile CounterCell[] counterCells;

// Unsafe
private static final long BASECOUNT;

/**
 * Adds to count, and if table is too small and not already
 * resizing, initiates transfer. If already resizing, helps
 * perform transfer if work is available.  Rechecks occupancy
 * after a transfer to see if another resize is already needed
 * because resizings are lagging additions.
 *
 * @param x the count to add
 * @param check if <0, don't check resize, if <= 1 only check if uncontended
 */
private final void addCount(long x, int check) {
    CounterCell[] as; long b, s;
    // counterCells不为空，或CAS更新baseCount失败
    if ((as = counterCells) != null ||
        !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
        CounterCell a; long v; int m;
        boolean uncontended = true;
        // counterCells为空（尚未并发）
        // 随机取余一个数组位置为空 或修改这个槽位变量失败（有并发）
        if (as == null || (m = as.length - 1) < 0 ||
            (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
            !(uncontended =
              U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
            fullAddCount(x, uncontended); // 更新baseCount失败的元素个数保存到CounterCells中
            return;
        }
        if (check <= 1)
            return;
        s = sumCount(); // 总节点数量
    }
    if (check >= 0) {
        Node<K,V>[] tab, nt; int n, sc;
        while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
               (n = tab.length) < MAXIMUM_CAPACITY) { // 扩容
            int rs = resizeStamp(n); // 根据length得到一个标识
            if (sc < 0) { // 正在扩容
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                    sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                    transferIndex <= 0)
                    break;
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                    transfer(tab, nt);
            }
            // 不在扩容，使用CAS将sizeCtl更新：标识符左移16位+2，高位为标识符，低16位为2(负数)
            else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                         (rs << RESIZE_STAMP_SHIFT) + 2))
                transfer(tab, null); // 扩容
            s = sumCount();
        }
    }
}

size、节点总数sumCount

public int size() {
    long n = sumCount();
    return ((n < 0L) ? 0 :
            (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
            (int)n);
}

final long sumCount() {
    CounterCell[] as = counterCells; CounterCell a;
    long sum = baseCount; // 修改baseCount成功的线程插入的数量
    if (as != null) {
        // 修改baseCount失败的线程插入的数量
        for (int i = 0; i < as.length; ++i) {
            if ((a = as[i]) != null)
                sum += a.value; // 只处理sum返回，不处理失败的集合
        }
    }
    return sum;
}

13.4 ConcurrentHashMap有什么缺陷吗？

ConcurrentHashMap 是设计为非阻塞的。在更新时会局部锁住某部分数据，但不会把整个表都锁住。同步读取操作则是完全非阻塞的。好处是在保证合理的同步前提下，效率很高。

坏处是严格来说读取操作不能保证反映最近的更新。例如线程A调用putAll写入大量数据，期间线程B调用get，则只能get到目前为止已经顺利插入的部分数据。

本栏目推荐文章
• HashMap的七大遍历方式
• set集合&&hashMap总结
• Java中Hashtable、HashMap、TreeMap的比较
• 哈希表(HashMap)与字符串哈希
• Java-研究HashMap的源码
• 【Java集合】双列集合HashMap的概念、特点及使用
• 【JavaSE】集合Collection{List(ArrayList, LinkedList), Set(TreeSet, HashSet, LinkedHashSet)} + Map(HashMap, TreeMap, LinkedHashMap)
• 【JavaSE】数据结构-哈希表（HashSet/HashMap底层哈希表详解，源码分析）
• 你真的了解HashSet 和HashMap的区别、优缺点、使用场景吗？
• HashMap超详细源码解析

HashMaphashmap问题 hashmap方式 hashmap java hashmap时候 hashmap1 hashmap方法put 原理hashmap 源码hashmap 算法hashmap java-hashmap