1.對比 Hashtable、HashMap、TreeMap 有什么不同？
Hashtable 是早期 Java 類庫提供的一個哈希表實現(xiàn)，本身是同步的，不支持 null 鍵和值，由于同步導致的性能開銷，所以已經(jīng)很少被推薦使用。
HashMap 是應用更加廣泛的哈希表實現(xiàn)，行為上大致上與 HashTable 一致，主要區(qū)別在于 HashMap 不是同步的，支持 null 鍵和值等。通常情況下，HashMap 進行 put 或者 get 操作，可以達到常數(shù)時間的性能，所以它是絕大部分利用鍵值對存取場景的首選，比如，實現(xiàn)一個用戶 ID 和用戶信息對應的運行時存儲結(jié)構(gòu)。
TreeMap 則是基于紅黑樹的一種提供順序訪問的 Map，和 HashMap 不同，它的 get、put、remove 之類操作都是 O（log(n)）的時間復雜度，具體順序可以由指定的 Comparator 來決定，或者根據(jù)鍵的自然順序來判斷。
2.介紹下對象的 hashCode()和equals()，使用場景
hashcode
頂級類Object里面的方法，所有的類都是繼承Object,返回是?個int類型的數(shù)，根據(jù)?定的hash規(guī)則(存儲地址，字段，長度等)，映射成?個數(shù)組，即散列值。
equals
頂級類Object里面的方法，所有的類都是繼承Object,返回是?個boolean類型，根據(jù)自定義的匹配規(guī)則，用于匹配兩個對象是否?樣，一般邏輯如下：
1.判斷地址是否?樣
2.非空判斷和Class類型判斷
3.強轉(zhuǎn)
4.對象里面的字段一一匹配
hashCode 和 equals 的一些基本約定，比如：
1.equals 相等，hashCode 一定要相等。
2.重寫了 hashCode 也要重寫 equals。
3.hashCode 需要保持一致性，狀態(tài)改變返回的哈希值仍然要一致。
4.equals 的對稱、反射、傳遞等特性。
3.HashMap和TreeMap應該怎么選擇，使用場景
hashMap: 散列桶(數(shù)組+鏈表)，可以實現(xiàn)快速的存儲和檢索，但是確實包含無序的元素，適用于在map中插入刪除和定位元素。
treeMap:使用存儲結(jié)構(gòu)是?個平衡?叉樹->紅?樹，可以?定義排序規(guī)則，要實現(xiàn)Comparator接口，
能便捷的實現(xiàn)內(nèi)部元素的各種排序，但是?般性能比HashMap差，適用于按照自然排序或者自定義排
序規(guī)則。
4.Set和Map的關(guān)系
Set的核心就是不保存重復的元素，存儲?組唯?的對象。
set的每?種實現(xiàn)都是對應Map里面的一種封裝。
HashSet對應的就是HashMap，treeSet對應的就是treeMap。
例如：HashSet無參構(gòu)造方法，其實就是初始化了一個HashMap：
public HashSet() {
map = new HashMap<>();
}
5.LinkedHashMap 和 TreeMap
雖然 LinkedHashMap 和 TreeMap 都可以保證某種順序，但二者還是非常不同的。
LinkedHashMap 通常提供的是遍歷順序符合插入順序，它的實現(xiàn)是通過為條目（鍵值對）維護一個雙向鏈表。注意，通過特定構(gòu)造函數(shù)，我們可以創(chuàng)建反映訪問順序的實例，所謂的 put、get、compute 等，都算作“訪問”。
對于 TreeMap，它的整體順序是由鍵的順序關(guān)系決定的，通過 Comparator 或 Comparable（自然順序）來決定。
6.如果需要線程安全，且效率高的Map，應該怎么做？
多線程環(huán)境下可以用concurrent包下的ConcurrentHashMap, 或者使用Collections.synchronizedMap(),
ConcurrentHashMap雖然是線程安全，但是他的效率比Hashtable要高很多。
ConcurrentHashMap<String, String> concurrentHashMap = new ConcurrentHashMap<>();
Map<Object, Object> map = Collections.synchronizedMap(new HashMap<>());
7.介紹下你了解的HashMap
HashMap 內(nèi)部的結(jié)構(gòu)，它可以看作是數(shù)組（Node[] table）和鏈表結(jié)合組成的復合結(jié)構(gòu)，數(shù)組被分為一個個桶（bucket），通過哈希值決定了鍵值對在這個數(shù)組的尋址；哈希值相同的鍵值對，則以鏈表形式存儲，你可以參考下面的示意圖。這里需要注意的是，如果鏈表大小超過閾值（TREEIFY_THRESHOLD, 8），圖中的鏈表就會被改造為樹形結(jié)構(gòu)。
從非拷貝構(gòu)造函數(shù)的實現(xiàn)來看，這個表格（數(shù)組）似乎并沒有在最初就初始化好，僅僅設置了loadFactor和initialCapacity。
/**
* The next size value at which to resize (capacity * load factor).
*閾值：下一次擴容時候的值（容量*加載因子）
* @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;
/**
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;
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);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
put()方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* 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;
//如果當前Node數(shù)組為空
if ((tab = table) == null || (n = tab.length) == 0)
//調(diào)用resize()方法，初始化table，并設置n=DEFAULT_INITIAL_CAPACITY，n=16
n = (tab = resize()).length;
//如果要放入鍵值對在哈希表中的位置，沒有節(jié)點。
if ((p = tab[i = (n - 1) & hash]) == null)
//創(chuàng)建新節(jié)點
tab[i] = newNode(hash, key, value, null);
//要放入鍵值對在哈希表中的位置，有節(jié)點。
else {
Node<K,V> e; K k;
//如果要放入鍵的hash等于首節(jié)點hash，且，key相等，則覆蓋掉原來的value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果該Node是一個紅黑樹
else if (p instanceof TreeNode)
//執(zhí)行紅黑樹插入邏輯
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//如果該Node是一個鏈表
else {
//遍歷當前鏈表
for (int binCount = 0; ; ++binCount) {
//如果當前節(jié)點是尾節(jié)點
if ((e = p.next) == null) {
//插入鏈表
p.next = newNode(hash, key, value, null);
//如果當前鏈表索引>=樹化閾值-1，即（8-1）
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//樹化當前鏈表
treeifyBin(tab, hash);
break;
}
//如果要放入元素的鍵，與當前鍵相等，跳出循環(huán)。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//將e指向P，相當于循環(huán)里面的第二個語句
p = e;
}
}
//如果key已經(jīng)存在了，覆蓋舊的value。
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//空實現(xiàn)
afterNodeAccess(e);
//返回舊的value
return oldValue;
}
}
//判斷是否有并發(fā)插入的變量。
++modCount;
//如果當前數(shù)組長度+1>閾值（數(shù)組長度*加載因子）
if (++size > threshold)
//擴容
resize();
afterNodeInsertion(evict);
//返回空值
return null;
}
get方法：
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;
//如果key對應的Node不為空，且頭節(jié)點不為空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//如果頭節(jié)點的hash等于hash，且頭節(jié)點的key等于key
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//如果頭節(jié)點的下一個節(jié)點不為空
if ((e = first.next) != null) {
如果頭節(jié)點是樹
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;
}
8.ConcurrentHashMap 如何實現(xiàn)高效地線程安全？
早期 ConcurrentHashMap，其實現(xiàn)是基于：
分離鎖，也就是將內(nèi)部進行分段（Segment），里面則是 HashEntry 的數(shù)組，和 HashMap 類似，哈希相同的條目也是以鏈表形式存放。
HashEntry 內(nèi)部使用 volatile 的 value 字段來保證可見性，也利用了不可變對象的機制以改進利用 Unsafe 提供的底層能力，比如 volatile access，去直接完成部分操作，以最優(yōu)化性能，畢竟 Unsafe 中的很多操作都是 JVM intrinsic 優(yōu)化過的。
可以參考下面這個早期 ConcurrentHashMap 內(nèi)部結(jié)構(gòu)的示意圖，其核心是利用分段設計，在進行并發(fā)操作的時候，只需要鎖定相應段，這樣就有效避免了類似 Hashtable 整體同步的問題，大大提高了性能。
在 Java 8 和之后的版本中，ConcurrentHashMap 發(fā)生了哪些變化呢？
總體結(jié)構(gòu)上，它的內(nèi)部存儲變得 HashMap 結(jié)構(gòu)非常相似，同樣是大的桶（bucket）數(shù)組，然后內(nèi)部也是一個個所謂的鏈表結(jié)構(gòu)（bin），同步的粒度要更細致一些。
其內(nèi)部仍然有 Segment 定義，但僅僅是為了保證序列化時的兼容性而已，不再有任何結(jié)構(gòu)上的用處。因為不再使用 Segment，初始化操作大大簡化，修改為 lazy-load 形式，這樣可以有效避免初始開銷，解決了老版本很多人抱怨的這一點。
數(shù)據(jù)存儲利用 volatile 來保證可見性。
使用 CAS 等操作，在特定場景進行無鎖并發(fā)操作。
使用 Unsafe、LongAdder 之類底層手段，進行極端情況的優(yōu)化。
put方法
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) {
if (key == null || value == null) throw new NullPointerException();
//對key進行重哈希，減少哈希碰撞概率
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
//如果當前Node[]為空
if (tab == null || (n = tab.length) == 0)
//初始化Node[]
tab = initTable();
//如果key的hash，對應的數(shù)組元素為空
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
}
//如果是這個狀態(tài)則是擴容操作，先進行擴容
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
//存在哈希沖突，利用synchronized (f) 加鎖保證線程安全
else {
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
//如果當前節(jié)點是鏈表，則遍歷插入。
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;
}
}
}
// 如果是紅黑樹則按照紅黑樹規(guī)則插入
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);
return null;
}
JDK8之前，ConcurrentHashMap使?鎖分段技術(shù)，將數(shù)據(jù)分成?段段存儲，每個數(shù)據(jù)段配置?把
鎖，即segment類，這個類繼承ReentrantLock來保證線程安全
JKD8的版本取消Segment這個分段鎖數(shù)據(jù)結(jié)構(gòu)，底層也是使用Node數(shù)組+鏈表+紅黑樹，從而實現(xiàn)對
每?段數(shù)據(jù)進行加鎖，也減少了并發(fā)沖突的概率，CAS(讀)+Synchronized(寫)
