深入浅出Map

Map是java里边是一个接口,常见的实现类有HashMap、LinkedHashMap、TreeMap和ConcurrentHashMap

HashMap底层数据结构是数组+链表/红黑树

LinkedHashMap底层数据结构是数组+链表+双向链表

TreeMap底层数据结构是红黑树

ConcurrentHashMap底层数据结构是数组+链表/红黑树

HashMap

简单总结HashMap：
无序，允许为null，非同步
底层由散列表(哈希表)实现
初始容量和装载因子对HashMap影响挺大的，设置小了不好，设置大了也不好

new一个hashmap时会发生什么?

HashMap有几个构造方法,但最主要的就是指定初始值以及负载因子的大小.如果不指定,默认hashmap的大小为16,负载因子的大小为0.75.

HashMap的大小只能是2次幂,（因为只有大小为2次幂时，才能合理用位运算替代取模）
假如传一个10进去,实际大小是16.
假如传入一个7进去,hashmap最终大小是8,具体实现在tableSizeFor可以看到

把元素放进hashmap的时候，需要算出这个元素所在的位置（hash），在hashmap里用的是位运算来代替取模，能够更加高效地算出该元素所在的位置。

而负载因子的大小决定着哈希表的扩容和哈希冲突。

比如默认hashmap的大小为16,负载因子的大小为0.75.这意味着数组最多只能放16×0.75=12个元素，一旦超过12个元素，则哈希表需要扩容。每次Put元素的时候都会检查hashmap的大小有没有超过这个阈值，如果超过则扩容。

鉴于（HashMap的大小只能是2次幂），所以扩容的时候默认扩容为原来的2倍。

扩容是耗时的,也可以通过调高负载因子来减少扩容.
但是一般不推荐这样做,因为这样意味着哈希冲突的概率会增高,哈希冲突的概率增高同样会耗时(因为查找的速度变慢了)

Put元素

怎么计算hash？

put元素的时候，先算出正常的哈希值，然后与高16位做异或运算，产生最终的哈希值。好处是增加了随机性，减少了碰撞冲突的可能性。

put和get的实现

put

首先对key做hash运算，计算出该key所在的index。
如果没碰撞，直接放到数组中，如果碰撞了，需要判断目前数据结构是链表还是红黑树，根据不同的情况来进行插入。
假如key相同的，则替换到原来的值。最后判断哈希表是否满了（当前哈希表大小×负载因子），如果满了，则扩容。

get

还是对key做hash运算，计算出该key所在的index，然后判断是否有哈希冲突。
假如没有冲突则直接返回。假设有冲突则判断目前数据结构是链表还是红黑树，分别从不同的数据结构中取出。

在hashmap中，怎么判断一个元素是否相同？

首先比较hash值，随后会用==运算符和equals()来判断该元素是否相同。

说白了，就是：

如果只有hash值相同，那说明该元素hash冲突了，如果hash值和equal() || == 都相同，那说明该元素是同一个。

什么情况下会转红黑树？

当数组大小>64且链表的大小>8的时候才会将链表转为红黑树。当红黑树大小为6时，会退化为链表。
这里转红黑树退化为链表的操作主要出于查询和插入时对性能的考量
链表的查询时间复杂度为O(N),插入时间复杂度为O(1),红黑树查询和插入时间复杂度为O(logN)

线程安全？

HashMap是线程不安全的，在多线程环境下，HashMap有可能会有数据丢失和获取不了最新数据的问题，比如线程A put进去了，线程B get不出来。

LinkedHashMap

实际上继承了HashMap，在HashMap的基础上维护了一个双向链表。
有了这个双向链表，插入的顺序是有序的。
LinkedHashMap在遍历的时候，实际上是用的是双向链表来遍历的，所以LinkedHashMap的大小不会影响到遍历的性能

TreeMap

TreeMap的key不能为null（如果为null就不能排序），TreeMap有序是通过Comparator来进行比较的，如果
Comparator为null，那么就使用自然顺序

ConcurrentHashMap

ConcurrentHashMap是JUC包下的线程安全的Map实现类，他能支持高并发的访问和更新。
线程安全的Map实现类还有HashTable，还有可以使用Collections来包装出一个线程安全的Map。
但是HashTable还是Collections来包装出来的，都比较低效，因为都是直接在外层套synchronize。
所以一般有线程安全问题考量的，都使用ConcurrentHashMap。

ConcurrentHashMap通过在部分加锁和利用CAS算法来实现同步，在get的时候没有加锁，Node都用了volatile给修饰。

在扩容时，会给每个线程分配对应的区间，并且为了防止putVal导致数据不一致，会给线程的所负责的区间加锁。