Map
Map接口并不是继承自Collection接口，这个要注意了
-
常见的Map实现类:
- HashMap
- ConcurrentHashMap
- LinkedHashMap
- TreeMap
-
util包的关系图，Map和Dictionary
util包中Map依赖关系图 关于Hash算法和Hash冲突的解决方法，详细可参考全网把Map中的hash()分析的最透彻的文章，别无二家。-HollisChuang's Blog
HashMap
- 环形链表的问题：具体见疫苗：Java HashMap的死循环 | | 酷 壳 - CoolShell
- 环形链表的形成是发生在并发rehash的过程中的
- 并不是说rehash就直接导致死循环了，rehash只是导致的了环形链表的形成
- 底层数据结构
- 数组
- 链表
- 红黑树
- 扩容
- 时机：map中的key个数达到容量c * 负载因子loadFactor的时候
- 过程
- 容量扩大一倍
- rehash一次
- 冲突解决
- 默认的策略是在相应的index位置形成链表
- 当链表的数量达到8个时，出于性能考虑会把链表转成红黑树
- 快速失败是什么意思? 集合遍历的时候检测是否集合中的元素个数有变动，有变动就立即抛出异常ConcurrentModificationException
The number of times this HashMap has been structurally modified Structural modifications are those that change the number of mappings in the HashMap or otherwise modify its internal structure (e.g.,
rehash). This field is used to make iterators on Collection-views of
the HashMap fail-fast. (See ConcurrentModificationException).
- [x]loadFactor是用来干什么的？决定是否扩容
ConcurrentHashMap
- 底层数据结构
- 数组
- 链表
- 红黑树
- 扩容过程
- JDK7锁住所有段，然后扩容，保证一致性
- JDK8多线程扩容，标记要迁移的点（要迁移的点node的hash值会被标记成为MOVED，即-3），当一个线程要获取fh被标记为MOVED的节点时，要先帮忙扩容，然后再获取值
- size是怎么计算的？
- 默认是使用baseCount，如果因为并发导致这个属性更新失败，会使用counterCells来计数。
- 计数的时候，会使用先计算两次，如果没变化，就认为总数是正确
- 如果一直在变化，就多尝试两次。如果还是失败，就锁全表进行计算。
- JDK7和JDK8上的分段锁机制的差别
- DK7使用ReentrantLock来实现分段锁
- JDK8使用CAS+synchronized，为什么使用synchronized+CAS, 而不是segment+ReentrantLock呢？ConcurrentHashMap 1.8为什么要使用CAS+Synchronized取代Segment+ReentrantLock - 羊飞 - 博客园
- [x]synchronized默认情况是偏向锁，或者是自旋锁，效率高，ReentrantLock则是tryLock之后就挂起，这样导致有线程上下文切换的成本， JDK7版本这里会tryLock很多次
- [x]锁的粒度细化到了node级别，粒度更小，并发能力更大
常见面试题
Map
- rehash的时候，链表上的点还会在同一个链表上么？@可能不在同一个位置上了， 这是因为桶位置的计算方式是hash&(cap-1), hash值是不变的， cap变化的情况，可能导致计算的index不一样， 譬如cap为16，hash分别为5, 21, 37, rehash之后，桶的index分别为5, 21,
HashMap
- 扩容过程 @见上面的笔记
- size为什么是2的整数倍?
- 计算index的时候可以减小冲突
- 计算index的公式 hash & (size - 1)
- 冲突解决的过程 @见上面的笔记
ConcurrentHashMap
- 为什么JDK8中要用CAS+synchronized替代segment+ReentrantLock的实现来防止并发？@见上面的笔记
