TreeMap
TreeMap的底层是红黑树，是自平衡的二叉查找树。
在查找元素时会从左子树或右子树查找，和元素一个一个进行比较，对于大数量的查找的场景TreeMap不适合（HashMap解决了这个问题）。
TreeMap的好处，是一个天然有序集合，适用于对元素进行排序的场景。
HashMap
HashMap原理
HashMap是Map接口的实现类。
HashMap解决大数量查找的问题。
HashMap也叫哈希表，底层：
如何向HashMap中添加一个元素：
- 计算这个元素（key）的哈希值。
- 根据哈希值找到数组中桶的位置。
- 如果桶中没有元素，直接将新元素存入桶中。
- 如果桶中有元素，根据equals方法来判断是否和已有元素相等，如果相等则覆盖，如果不相等就存入链表或红黑树。
哈希值
在Object类中有一个方法得到哈希值。
public native int hashCode();
native: 本地方法，用c语言实现的。
默认哈希值：
- 整数的哈希值是它本身。
- 字符串的哈希值是根据各个字符计算出来的。
- 任意对象的哈希值是它的内存地址。
哈希值的特点：
1、 同一对象多次调用它的hashCode()方法得到哈希值是相同的。
2、默认情况下对象的哈希值是不同的。
自定义类型时可以重写hashCode()方法,根据业务需求自定义哈希值的计算过程。
哈希表的原理
根据源代码分析向哈希表存入元素的过程。
public V put (K key, V value){
return putVal(hash(key), key, value, false, true);
}
// 第一个参数hash（key）计算哈希值
putVal(hash(key), key, value, false, true);
- 如果table为空，调用resize()方法，调整table的长度。
- 得到新表的长度，赋值给变量n。
- 如果桶中没有元素，直接将新元素放入桶中。
- (n-1)&hash计算桶位置。
- 如果要添加的新元素和桶中的元素相等（使用equals方法），直接覆盖。
- 如果节点是TreeNode红黑树，将新元素存入红黑树。否则将新元素存入链表。
哈希表扩容
- 首先根据哈希表的长度计算一个阈值，阈值=hash表的长度*负载因子(0.75)
16 * 0.75 = 12 - 当每次添加完元素，判断集合中的元素个数是否达到阈值，如果达到了，开始扩容。每次扩容原来大小的二倍。
- 扩容不仅是创建新数组，还需要将旧数组中的数据拷贝到新数组中。
哈希冲突
向哈希表添加一个元素，计算桶的位置，当位置上有元素了，叫哈希冲突，也叫哈希碰撞。
哈希冲突影响了存储的效率。
如何避免哈希冲突？
（n - 1）& hash 计算桶的位置
包括两个因素：n表示表的长度; hash表示key的哈希值。
- 避免哈希冲突要保证对象的哈希值不同。
通常要对自定义类型的hashCode()进行重写。
建议使用idea或Eclipse生成：
@Overrride
public int hashCode(){
return Objects.hash(id, nickName, age);
}
- 哈希表的容量使用2的n次幂，默认情况下哈希表的初始容量是16、经过扩容后是32、64···
测试代码
通过测试debug跟踪，HashMap (哈希表的扩容以及链表转成红黑树)。
参考资料：快速搞定Java HashMap底层原理_攀博课堂分享
