1.对比 Hashtable、HashMap、TreeMap 有什么不同？
Hashtable 是早期 Java 类库提供的一个哈希表实现，本身是同步的，不支持 null 键和值，由于同步导致的性能开销，所以已经很少被推荐使用。
HashMap 是应用更加广泛的哈希表实现，行为上大致上与 HashTable 一致，主要区别在于 HashMap 不是同步的，支持 null 键和值等。通常情况下，HashMap 进行 put 或者 get 操作，可以达到常数时间的性能，所以它是绝大部分利用键值对存取场景的首选，比如，实现一个用户 ID 和用户信息对应的运行时存储结构。
TreeMap 则是基于红黑树的一种提供顺序访问的 Map，和 HashMap 不同，它的 get、put、remove 之类操作都是 O（log(n)）的时间复杂度，具体顺序可以由指定的 Comparator 来决定，或者根据键的自然顺序来判断。
2.介绍下对象的 hashCode()和equals()，使用场景
hashcode
顶级类Object里面的方法，所有的类都是继承Object,返回是⼀个int类型的数，根据⼀定的hash规则(存储地址，字段，长度等)，映射成⼀个数组，即散列值。
equals
顶级类Object里面的方法，所有的类都是继承Object,返回是⼀个boolean类型，根据自定义的匹配规则，用于匹配两个对象是否⼀样，一般逻辑如下：
1.判断地址是否⼀样
2.非空判断和Class类型判断
3.强转
4.对象里面的字段一一匹配
hashCode 和 equals 的一些基本约定，比如：
1.equals 相等，hashCode 一定要相等。
2.重写了 hashCode 也要重写 equals。
3.hashCode 需要保持一致性，状态改变返回的哈希值仍然要一致。
4.equals 的对称、反射、传递等特性。
3.HashMap和TreeMap应该怎么选择，使用场景
hashMap: 散列桶(数组+链表)，可以实现快速的存储和检索，但是确实包含无序的元素，适用于在map中插入删除和定位元素。
treeMap:使用存储结构是⼀个平衡⼆叉树->红⿊树，可以⾃定义排序规则，要实现Comparator接口，
能便捷的实现内部元素的各种排序，但是⼀般性能比HashMap差，适用于按照自然排序或者自定义排
序规则。
4.Set和Map的关系
Set的核心就是不保存重复的元素，存储⼀组唯⼀的对象。
set的每⼀种实现都是对应Map里面的一种封装。
HashSet对应的就是HashMap，treeSet对应的就是treeMap。
例如：HashSet无参构造方法，其实就是初始化了一个HashMap：
public HashSet() {
map = new HashMap<>();
}
5.LinkedHashMap 和 TreeMap
虽然 LinkedHashMap 和 TreeMap 都可以保证某种顺序，但二者还是非常不同的。
LinkedHashMap 通常提供的是遍历顺序符合插入顺序，它的实现是通过为条目（键值对）维护一个双向链表。注意，通过特定构造函数，我们可以创建反映访问顺序的实例，所谓的 put、get、compute 等，都算作“访问”。
对于 TreeMap，它的整体顺序是由键的顺序关系决定的，通过 Comparator 或 Comparable（自然顺序）来决定。
6.如果需要线程安全，且效率高的Map，应该怎么做？
多线程环境下可以用concurrent包下的ConcurrentHashMap, 或者使用Collections.synchronizedMap(),
ConcurrentHashMap虽然是线程安全，但是他的效率比Hashtable要高很多。
ConcurrentHashMap<String, String> concurrentHashMap = new ConcurrentHashMap<>();
Map<Object, Object> map = Collections.synchronizedMap(new HashMap<>());
7.介绍下你了解的HashMap
HashMap 内部的结构，它可以看作是数组（Node[] table）和链表结合组成的复合结构，数组被分为一个个桶（bucket），通过哈希值决定了键值对在这个数组的寻址；哈希值相同的键值对，则以链表形式存储，你可以参考下面的示意图。这里需要注意的是，如果链表大小超过阈值（TREEIFY_THRESHOLD, 8），图中的链表就会被改造为树形结构。
从非拷贝构造函数的实现来看，这个表格（数组）似乎并没有在最初就初始化好，仅仅设置了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数组为空
if ((tab = table) == null || (n = tab.length) == 0)
//调用resize()方法，初始化table，并设置n=DEFAULT_INITIAL_CAPACITY，n=16
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;
//如果要放入键的hash等于首节点hash，且，key相等，则覆盖掉原来的value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果该Node是一个红黑树
else if (p instanceof TreeNode)
//执行红黑树插入逻辑
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//如果该Node是一个链表
else {
//遍历当前链表
for (int binCount = 0; ; ++binCount) {
//如果当前节点是尾节点
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;
}
//如果要放入元素的键，与当前键相等，跳出循环。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//将e指向P，相当于循环里面的第二个语句
p = e;
}
}
//如果key已经存在了，覆盖旧的value。
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//空实现
afterNodeAccess(e);
//返回旧的value
return oldValue;
}
}
//判断是否有并发插入的变量。
++modCount;
//如果当前数组长度+1>阈值（数组长度*加载因子）
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不为空，且头节点不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//如果头节点的hash等于hash，且头节点的key等于key
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
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;
}
8.ConcurrentHashMap 如何实现高效地线程安全？
早期 ConcurrentHashMap，其实现是基于：
分离锁，也就是将内部进行分段（Segment），里面则是 HashEntry 的数组，和 HashMap 类似，哈希相同的条目也是以链表形式存放。
HashEntry 内部使用 volatile 的 value 字段来保证可见性，也利用了不可变对象的机制以改进利用 Unsafe 提供的底层能力，比如 volatile access，去直接完成部分操作，以最优化性能，毕竟 Unsafe 中的很多操作都是 JVM intrinsic 优化过的。
可以参考下面这个早期 ConcurrentHashMap 内部结构的示意图，其核心是利用分段设计，在进行并发操作的时候，只需要锁定相应段，这样就有效避免了类似 Hashtable 整体同步的问题，大大提高了性能。
在 Java 8 和之后的版本中，ConcurrentHashMap 发生了哪些变化呢？
总体结构上，它的内部存储变得 HashMap 结构非常相似，同样是大的桶（bucket）数组，然后内部也是一个个所谓的链表结构（bin），同步的粒度要更细致一些。
其内部仍然有 Segment 定义，但仅仅是为了保证序列化时的兼容性而已，不再有任何结构上的用处。因为不再使用 Segment，初始化操作大大简化，修改为 lazy-load 形式，这样可以有效避免初始开销，解决了老版本很多人抱怨的这一点。
数据存储利用 volatile 来保证可见性。
使用 CAS 等操作，在特定场景进行无锁并发操作。
使用 Unsafe、LongAdder 之类底层手段，进行极端情况的优化。
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，对应的数组元素为空
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);
//存在哈希冲突，利用synchronized (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);
return null;
}
JDK8之前，ConcurrentHashMap使⽤锁分段技术，将数据分成⼀段段存储，每个数据段配置⼀把
锁，即segment类，这个类继承ReentrantLock来保证线程安全
JKD8的版本取消Segment这个分段锁数据结构，底层也是使用Node数组+链表+红黑树，从而实现对
每⼀段数据进行加锁，也减少了并发冲突的概率，CAS(读)+Synchronized(写)
