1. java.util.HashMap

• jdk1.7 数组 + 链表
• jdk1.8 数组 + 链表/红黑树

类图 类继承AbstraMap类，实现接口：Map，Clonable，Serializable

#### public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

    主要参数

默认初始化容量：16 ，要求必须是2的次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
最大容量：2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
默认负载因子（load factor）：0.75f
static final float DEFAULT_LOAD_FACTOR = 0.75f;
默认链表转红黑树阈值：8，在一个node节点下值个数大于8时，转成红黑树
static final int TREEIFY_THRESHOLD = 8;
默认红黑树转链表阈值：6，在一个node节点下红黑树节点的个数小于6，转回成链表
static final int UNTREEIFY_THRESHOLD = 6;
最小链表树化容量：64
static final int MIN_TREEIFY_CAPACITY = 64;

主要方法     如果单个节点的链表节点数量大于设定的链表转树阈值，会转为红黑树     多线程，线程不安全 使用put方法没有加锁，会导致多线程情况下数据修改不安全   HashMap put/get/resize过程，读源码 put(key, value)：

// 1.对key的hashCode()做hash运算，计算index;
// 2.如果没碰撞直接放到bucket⾥；
// 3.如果碰撞了，以链表的形式存在buckets后；
// 4.如果碰撞导致链表过⻓(⼤于等于TREEIFY_THRESHOLD)，就把链表转换成红⿊树(JDK1.8中的改动)；
// 5.如果节点已经存在就替换old value(保证key的唯⼀性)
// 6.如果bucket满了(超过load factor*current capacity)，就要resize

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)
// HashMap的懒加载策略，当执行put操作时检测Table数组初始化。
           n = (tab = resize()).length;
       if ((p = tab[i = (n - 1) & hash]) == null)
//通过``Hash``函数获取到对应的Table，如果当前Table为空，则直接初始化一个新的Node并放入该Table中。       
           tab[i] = newNode(hash, key, value, null);
       else {
           Node<K,V> e; K k;
           //进行值的判断： 判断对于是不是对于相同的key值传进来不同的value，若是如此，将原来的value进行返回
           if (p.hash == hash &&
               ((k = p.key) == key || (key != null && key.equals(k))))
               e = p;
           else if (p instanceof TreeNode)
          // 如果当前Node类型为TreeNode，调用 PutTreeVal 方法。
               e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
           else {
//如果不是TreeNode，则就是链表，遍历并与输入key做命中碰撞。 
               for (int binCount = 0; ; ++binCount) {
                   if ((e = p.next) == null) {

//如果当前Table中不存在当前key，则添加。
                       p.next = newNode(hash, key, value, null);
                       if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

//超过了``TREEIFY_THRESHOLD``则转化为红黑树。
                           treeifyBin(tab, hash);
                       break;
                   }
                   if (e.hash == hash &&
                       ((k = e.key) == key || (key != null && key.equals(k))))            
//做命中碰撞，使用hash、内存和equals同时判断（不同的元素hash可能会一致）。
                       break;
                   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;
   }

get(key):

// 1.对key的hashCode()做hash运算，计算index;
// 2.如果在bucket⾥的第⼀个节点⾥直接命中，则直接返回；
// 3.如果有冲突，则通过key.equals(k)去查找对应的Entry;
// 4. 若为树，则在树中通过key.equals(k)查找，O(logn)；
// 5. 若为链表，则在链表中通过key.equals(k)查找，O(n)。

final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        // 判断 表是否为空，表重读是否大于零，并且根据此 key 对应的表内是否存在 Node节点。    
        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))))
                // 检查第一个Node 节点，若是命中则不需要进行do... whirle 循环。
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                //树形结构，采用 对应的检索方法，进行检索。
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                //链表方法 做while循环，直到命中结束或者遍历结束。
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

问题 1）为什么使用链表+数组 计算key的hash值取得下标，不同的key的下标一样，出现了hash冲突，所以每个数组元素存储链表，当出现hash冲突时，将元素放在同一个下标的数组元素的链表中，进行链式存储。 2）⽤LinkedList代替数组结构可以吗？ 可以，但是效率没有数组高，数组直接通过下标就可以获取到元素，查询效率是O(1)，而链表查找时间复杂度是O(n)(需要遍历)。 那为什么不采用ArrayList？查找效率也是O(1)。 因为ArrayList有自己的扩容机制，1.5倍扩容。而HashMap中的数组扩容刚好是2的次幂，在做取模运算的时候效率高。 3）说一下hashMap put/get的过程？ put：

• 对key进行hashcode值进行位运算，获取数组下标值；
• 是否有hash碰撞，有的话追加到链表节点，没有则新建一个Node存储在数组该下标处；
• 如果hash碰撞导致链表长度超过设定的链表转树阈值，则将链表转为红黑树；
• 如果节点已经存在的话就替换掉旧值；
• 如果容量超过当前的负载，即load_factor * current_capacity，就要扩容resize()。

get:

• 对key进行hashcode值进行位运算，获取数组下标值；
• 如果在数组中有节点，就根据key值遍历数组/红黑树获得值，没有返回null
• 如果数组中该处下标美哦与node，直接返回null

4）线程是否安全？ 不安全。 5）为什么先是用链表，超过设定的阈值了才使用红黑树？ 效率，元素小于8个是，链表已经可以保证查询性能了，没有必要使用红黑树，反而麻烦，但元素大于8个时，就可以转化成红黑树提高查询插入效率 6）什么时候退化成链表？ 默认当红黑树节点数减少到6个时，红黑树会退化成链表。 7）key值可以为null吗，value呢 key值可以为null，但是只有一个key值可以为null，value可以为null，并且可以有多个。 8）一般用什么作为key值？ 一般使用Integer，String这种不可变类当做key (1)因为字符串是不可变的，所以在它创建的时候hashcode就被缓存了，不需要重新计算。 这就使得字符串很适合作为Map中的键，字符串的处理速度要快过其它的键对象。 这就是HashMap中的键往往都使⽤字符串。 (2)因为获取对象的时候要⽤到equals()和hashCode()⽅法，那么键对象正确的重写这两个⽅法是⾮常重要的,这些类已 经很规范的覆写了hashCode()以及equals()⽅法。 9）实现一个自定义的class作为Hashmap的key该如何实现？ 重写hashcode和equals方法。   注：

• 对于HashMap而言，扩容是一个特别消耗内存的操作。所以当程序员在使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。
• 负载因子是可以修改的，也可以大于1，但是建议不要轻易修改，除非情况非常特殊。
• HashMap是线程不安全的，不要在并发的环境中同时操作HashMap，建议使用ConcurrentHashMap。

      2. java.util.Hashtable   类图   默认初试化大小 11 ，负载因子0.75f     主要参数   主要方法，同上   多线程，线程安全 put，remove，putAll，clear，clone，toString，equals ，getOrDefault， forEach 等方法有用 synchronized 修饰

public synchronized V put(K key, V value) 

public synchronized V remove(Object key)

public synchronized void putAll(Map<? extends K, ? extends V> t)

public synchronized void clear()

public synchronized Object clone()

public synchronized String toString()

public synchronized boolean equals(Object o)

......

    3. java.util.concurrent.ConcurrentHashMap   类图 线程安全 JDK1.8的ConcurrentHashMap

• 并发控制使⽤synchronized 和 CAS 来操作
• synchronized 只锁定当前链表或红⿊⼆叉树的⾸节点，这样只要 hash 不冲突，就不会产⽣并发，效率⼜提升 N 倍。

  JDK1.7 使用Segment(分段锁)

• Segment(分段锁)：ConcurrentHashMap中的分段锁称为Segment，它即类似于HashMap的结构，即内部拥有一个Entry数组，数组中的每个元素又是一个链表,同时又是一个ReentrantLock（Segment继承了ReentrantLock）。
• 内部结构：ConcurrentHashMap使用分段锁技术，将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问。
• ConcurrentHashMap定位一个元素的过程需要进行两次Hash操作。第一次Hash定位到Segment，第二次Hash定位到元素所在的链表的头部

问题 基本同HashMap，只不过多了加锁操作 4. 比较  

HashMap	HashTable	ConcurrentHashMap
线程不安全	线程安全（synchronized锁住整张hash表，线程独占，效率太低）	线程安全（ synchronized 和 CAS ）
允许key和value为null	不允许key和value为空	不允许key和value为空
底层数组长度为2的次幂	底层数组可以为任意长度
hash计算下标使用位运算	hash计算下标使用取模
jdk1.8 使用数组+链表/红黑树	一直是数组+链表	数组+链表/红黑树
继承AbstractMap类	继承Dictionary类