HashMap - 知识点
1. HashMap底层数据结构
- hash数据+单链表，在jdlk1.8以后使用的是数组+链表+红黑树
2. HashMap工作原理
- 通过put和get存储和获取对象，当给put方法传递键值对的时候，相对键做一个hashCode()运算，得到它在bucket数组中的位置来存储entry对象，当获取对象的时候，通过get获取到backet的位置，在同过键对象的equals() 方法找到正确的键值对，返回对象。
3. 使用HashMap 时，当两个对象的hashCode相同怎么办
- HashCode相同不一定是相等的，可以通过equals方法进行比较，，HashCode相同则在数组中的下标是相同的，因为采用了链表或红黑树所以会存储在对应的数据结构中。
4. HashMap的哈希函数怎么设计的
- hash函数是先通过拿到key的hashCode，它是一个32位的Int类型，然后让hashCode的高16位和低16位进行异或操作。
- 可以降低hash碰撞发生的概率；
- 因为操作是高频的，所以算法一定要高效，所以采用了位运算；
5. HashMap遍历方法有几种
- Iterator迭代器；
- foreach；
- 通过key的set集合遍历
6. 为什么采用HashCode的高16位和低16位异或能降低碰撞
- 因为key.hashCode() 函数调用的是key类型自带的哈希函数，返回一个int值。int的范围 是-2147483648~ 2147483647 ， 前后大概有四十亿的映射空间，只要哈希函数映射的比较松散就不容易发生碰撞，但是四十亿的数组太大了，内存放不下。正常HashMap创建默认大小是16，用之前需要对数组的长度取模。
7. 解决hash冲突的方法
8. 为什么采用异或运算
- 保证了对象的hashCode只要有一位发生改变，整个hash函数返回的值就会发生变化，减少了冲突的发生。
9. HashMap的table的容量是如何确定的
- table数组的大小是由capacity这个参数决定的默认是16，可以由构造方法传入；
- loadFactor 是装载因子，主要的目的是用来确认table是否需要动态扩展，默认是0.75，比如默认大小是16 如果装入的元素超过12个则进行扩容；
- 扩容时，调用
resize() 方法，将table的长度变为原来的一倍； - 如果数据很大的情况下，扩展时将会带来性能的损失，在性能要求很高的地方，这种损失是致命的；
10. 解释loadFactor
- 装载因子，通过此项来判断当前的map的拥挤程度，当装入元素 / table 长度 > 此数的时候，可以认为冲突发生的可能性大大增加，就需要通过扩容来进行调整。
11. 说说put方法的过程
- 接收需要存储的键值对
- 根据传入的key计算hash的值
- 根据hash的值计算数组的下标
- 判断是否发生冲突
- 发生冲突：判断当前的节点是红黑树 or 链表
- 红黑树：在红黑树中插入数据；
- 链表：在链表尾插入数据；
- 未发生冲突：将对应的数据放入到数组对应的位置；
- 结束
12. 当链表的长度 >= 8的时候为什么要将链表转化为红黑树
- 因为红黑树的平均查找长度为log(n) 在长度为8 的时候查找长度为3，如果继续使用链表，则平均查找长度为8。所以长度超过7的时候会进行转化；
13. new HashMap(18) 此时容量是多少
- 容量是32；
- 在HashMap中有一个静态方法tableSizeFor，这个方法的返回值是大于等于给定构造容量的最小2的幂次方；
14 resize 扩容的过程
15. hashMap 中get的实现
- 对key的hashCode进行hash计算，与运算计算下标获取在数组bucket中的位置，如果在桶的首位则直接返回，如否则在链表或者红黑树中进行查找，如果有hash冲突，利用equals方法遍历链表进行查找
16. 拉链法导致的链表过深为何不用二叉查找树而用红黑树
- 用红黑树为为了解决二叉查找树的缺陷，二叉查找树在特殊情况下会变成一条线性结构，这就和原来的链表相同的了，而使用红黑树则会在插入的过程中调整二叉树，保持平衡，而保持平衡就需要付出更多的消耗，所以在特定得条件下才会使用红黑树。
17. 红黑树
- 红黑树是一种自平衡的二叉树，是一种高效的查找树。
- 红黑树通过如下的性质实现自平衡
- 节点是红色或者黑色
- 根是黑色的
- 所有的叶子都是黑色，叶子是NUL节点
- 每个红色的节点必须由两个黑色的子节点，或者说从根到叶子不允许出现连续两个红色的节点。
- 每个叶子节点到根都包含相同数量的黑色节点（黑高相同）
18. 1.7到1.8对hashMap有哪些改变
- 引入了红黑树，容量大于64，且链表长度大于7的时候会转化
- 发生hash碰撞时，1.7采用头插入，1.8采用尾插入
- 在1.8中使用Node替换了Entry
19. HashMap 中的key可以是任何类型么
- 可以使用自定义的类型作为Key
- 需要重写
equals() 和 hashCode() 方法 - 类的所有实例都需要遵循与equals 和hashCode相关的规则；
- 如果一个类没有使用equals则不应该在hashCode中使用它；
- 为了更好的性能要确保hashCode和equals在未来不会发生变换
20. HashMap的长度为什么是2的幂次方
- 为了让HashMap存数据和取数据的时候效率更高，即让数据尽可能的分散。取余操作中如果除数是2的幂次，则等价于其除数-1的与操作，并且采用二进制位操作 & 相当于提高了取余的操作效率。
21. HashMap和LinkedHashMap、TreeMap的区别
- LinkedHashMap 是继承HashMap，基于HashMap和双向链表实现的。
- HashMap无序，LinkedHashMap有序，可以分为插入顺序和访问顺序两种。如果是访问顺序，那put和get操作已存在的Node时，都会把Node移动到双向链表的表尾（其实就是先删除，再插入）
- LinkedHashMap存数据的时候和HashMap是一样的，只是保证了顺序；
- LinkedHashMap是线程不安全的；
- TreeMap是有序的，他是按照插入的key进行排序的。
22. 什么是 fail-fast
- fail-fast是Java集合中的一种错误机制，当多个线程对同一个集合的内容进行操作时，就可能发生fail-fast事件
- 例如当线程A通过迭代器遍历集合的过程中，集合被其他线程修改了，A就会抛出ConcurrentModificationException异常。解决方法是使用concurrent包下的类取代util包下的类。
23. HashMap和HashTable的区别
- HashMap是线程不安全的，HashTable是线程安全的；
- HashMap的效率在正常情况下是高于HashTable的；
- HashMap最多允许一条记录的键值为NULL，允许多条记录的值为NULL，而HashTable不允许；
- HashMap的默认大小是16，HashTable的默认大小是11，前者扩容扩大两倍，后者扩大两倍+1；
24. HashMap是线程安全的么
- 在多线程环境下，1.7中可能产生死循环，数据丢失，数据覆盖的问题，在1.8中会有数据覆盖的问题，如在1.8中，A线程判断index位置为空后挂起，B线程同样判断index位置为空，写入数据，此时A恢复继续执行，就会发生A将B的数据覆盖的问题，同时还有++size会造成多线程同时扩容的问题。
25. 如何避免HashMap的线程不安全
- 单线程环境下：
- 保证只通过HashMap本和或者只通过迭代器去修改数据，不能在迭代器使用结束之前使用HashMap本身的方法修改数据；
- 多线程环境：
- 可以使用Collections.synchronizedMap 构造一个同步的Map
- 使用ConcurrentHashMap
26. HashMap和ConcurrentHashMap区别
- 都是键值对的存储形式；
- HashMap线程不安全，ConcurrentHashMap线程安全；
- HashMap底层数据结构采用数组+链表+红黑树
- ConcurrentHashMap 在1.8之前是使用分段锁来实现Segment+HashEntry，Segment默认大小是16，2的n次方。在1.8以后 采用Node + CAS + Synchronized来保证并发安全的
27. 为什么ConcurrentHashMap比HashTable效率高
- HashTable：使用的是一把锁，直接会锁住整个数据结构，容易阻塞；
- ConcurrentHashMap： 在1.8以后 使用CAS + Synchronized + Node + 红黑树。锁粒度是Node（首节点）
28. ConcurrentHashMap中的锁机制
- 在1.8中取消了Segment直接使用table数组存储键值对；当HashEntry对象组成的链表超过TREEIFY_THRESHOLD时，链表会转换为红黑树，提升性能。
29. ConcurrentHashMap为何使用内置锁synchronized来代替重入锁ReentrantLock
- 降低了锁的粒度
- JVM对Synchronized进行了相关的优化；
- 在大量数据操作下，对于JVM内存压力，基于API的ReentrantLock的开销更大；
30. 对ConcurrentHashMap 简单介绍
- 重要常量
- sizeCtl：当为负数时标识在初始化， -N标识N-1个线程正在扩容。为0时标识table没有初始化，其他正数表示初始化或者下一次进行扩容的大小。
- 数据结构：
- Node：基本的存储单元，继承HashMap中的Entry
- TreeNode：继承Node，但是数据结构换成了二叉树，是红黑树的存储结构，用于红黑树的存储；
- TreeBin：是封装TreeNode的容器，提供转换红黑树的条件和锁控制；
- 存储对象时（put方法）
- 如果没有初始化，调用initTable（）方法进行初始化；
- 如果没有Hash冲突就直接CAS无锁插入；
- 如果需要扩容就先进行扩容；
- 如果存在Hash冲突，就加锁来保证线程安全：
- 链表：直接遍历到尾端插入
- 红黑树：按照对应的结构插入
- 如果满足转换红黑树的条件，先转换，然后重新插入；
- 如果插入成功，调用 addCount() 方法统计 size 判断是否需要扩容；
- 扩容方法 transfer() ：
- 默认容量是16，扩容变为两倍。
- helpTransfer()：调用多个工作线程一起帮助进行扩容。
- 取对象（get）
- 计算hash值，定位到table的位置，如果首位符合条件直接返回；
- 如果需要扩容，会调用标记正在扩容的节点ForwardingNode.find() 方法，查找该节点，匹配就返回；
- 以上都不符合，就往下遍历节点，匹配则返回，不匹配返回NULL；
31. ConcurrentHashMap的并发度
- 程序运行时能够同时更新ConcurrentHashMap且不产生锁竞争的最大线程数，默认是16，并且可以在构造函数中进行设置。当用户设置并发度时ConcurrentHashMap会使用大于等于该值的最小2的幂次方作为实际的并发度
- 因为ConcurrentHashMap 的锁是在Node的头节点上的，所以默认情况下最大的并发度就是16，而每次扩容后都是2的幂次方，所以对应的并发度就是ConcurrentHashMap的大小
|