经典问题：这三者的区别
HashMap的put的逻辑
阀值默认8，最低树化容量：64
HashMap 的长度为什么是2的幂次方
Hash 值的范围值-2147483648到2147483647，一个40亿长度的数组，内存是放不下的，用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是“ (n - 1) & hash”。（n代表数组长度）。这也就解释了 HashMap 的长度为什么是2的幂次方。“取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。
length = 16 16 -1 = 15 15二进制 1111 再相与(&)hash效果很好
如何有效减少碰撞
扰动函数：促使元素位置分布均匀，减少碰撞几率(hash函数保证了同时包含高16位和低16位的特性，使得更加的不确定性)
使用final对象，并采用合适的equals（）和hashcode（），如String Integer ,因为hashcode不会变
追问，为什么若重写equals(Object obj)方法，就必须重写hashcode()方法，确保通过equals(Object obj)方法判断结果为true的两个对象具备相等的hashcode()返回值？
- 如果重写了equals(),两个对象判断相等了。但是没有重写hashCode(),有可能两对象相等却hashCode不同，则HashSet这种存唯一值的可能会存了两个一样的对象。
为什么使用HashCode？
- 通过hashCode比较比equals方法快，当get时先比较hashCode，如果hashCode不同，直接返回false。
hash函数
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
图示：
1.高16bt不变，低16bit和高16bit做了一个异或(得到的hashcode转化为32位的二进制，前16位和后16位低16bit和高16bit做了一个异或)
2.(n-1)&hash=->得到下标
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);
HashMap也可以这样写实现线程安全：
Map safeHashMap = Collections.synchronizedMap(HashMap);
但是和Hashtable一样，都是串行的，效率低下。
concurrentHashMap key和Value不可以为null
CAS乐观锁，synchronized悲观锁
concurrentHashMap 比java 8之前的 segment（分段加锁），锁更细
首先使用无锁操作CAS插入头节点，失败则循环重试
若头节点已存在，则尝试获取头节点的同步锁，再进行操作
size方法和mappingCount（）方法的异同，两者计算是否准确
JDK1.7 和 JDK1.8 对 size 的计算是不一样的。 1.7 中是先不加锁计算三次，如果三次结果不一样在加锁。
JDK1.8 size 是通过对 baseCount 和 counterCell 进行 CAS 计算，最终通过 baseCount 和 遍历 CounterCell 数组得出 size。
JDK 8 推荐使用mappingCount 方法，因为这个方法的返回值是 long 类型，不会因为 size 方法是 int 类型限制最大值。
size（）最大值是 Integer 类型的最大值，但是 Map 的 size 可能超过 MAX_VALUE， 所以还有一个方法 mappingCount()，JDK 的建议使用 mappingCount() 而不是size()
原文链接：https://blog.csdn.net/qq_27037443/article/details/94441885
多线程下环境如何进行扩容
TreeMap 是有序的散列表，它是通过红黑树实现的。它一般用于单线程中存储有序的映射。（了解一下）
手撕一个Hashmap（无红黑树）
首先，接口类
public interface BtyMap<K,V> {
public V put(K k,V v);
public V get(K k);
interface Entry<K,V>{
public K getKey();
public V getValue();
}
}
具体实现类：
public class ButyHashMap<K,V> implements BtyMap<K, V>{
private Entry<K, V>[] arr = null;
int size;
public ButyHashMap() {
arr = new Entry[16];
}
public int size() {
return this.size;
}
class Entry<K,V> implements BtyMap.Entry<K, V>{
private K key;
private V value;
private Entry<K, V> next;
public Entry(){
}
public Entry(K key, V value,Entry<K, V> next) {
this.key = key;
this.value = value;
this.next=next;
}
@Override
public K getKey(){return key;}
@Override
public V getValue(){return value;}
}
@Override
public V put(K key, V value) {
V oldValue= null;
int index = key.hashCode() % arr.length;
if (arr[index] == null) {
arr[index] = new Entry<K,V>(key, value,null);
size++;
} else {
Entry<K, V> entry=arr[index];
Entry<K, V> e = entry;
while(e != null){
if(key == e.getKey()||key.equals(e.getValue())){
oldValue = e.value;
e.value = value;
return oldValue;
}
e = e.next;
}
arr[index] = new Entry(key, value, entry);
size++;
}
return oldValue;
}
@Override
public V get(K key){
int index=key.hashCode() % arr.length;
if(arr[index]==null)
return null;
else{
Entry<K, V> entry = arr[index];
while(entry!=null){
if(key == entry.getKey()||key.equals(entry.getKey())){
return entry.value;
}
entry=entry.next;
}
}
return null;
}
}
红黑树规则
红黑树本质上还是二叉查找树，额外的引入了5个约束条件：
1.节点只能是红色或黑色
2.根节点必须是黑色
3.所有NIL节点都是黑色的
4.一条路径上不能出现相邻的两个红色节点
5.在任何递归子树内，根节点到叶子节点的所有路径上包含相同数目的黑色节点
红黑树的插入与旋转
那些年，面试被虐过的红黑树
