集合框架

HashMap相关

常用的map主要有以下几种： HashMap 访问速度一般情况下较快，遍历顺序不定线程不安全 hashtable 线程安全，但效率较低 LinkedHashMap 保存了记录的插入顺序，再用Iterator 遍历时，先得到的记录肯定是先插入的。 TreeMap 带顺序的MAP,默认是升序

插入元素流程 1.7采用头插法，在发生hash冲突的情况下，将新进的元素放在头部，1.8的Hashmap的插入流程如下。
数据结构
1.7 及以下使用数组加链表的方式，但在hash冲突较为严重时，链表长度较长，对查找极不友好，所以 1.8采用动态方式，如果数组较长（>=64）或某个index的链表超过一定长度（8个），则转化为红黑树（treefiy）。对于移除，当同一个索引位置的节点在移除后达到 6 个，并且该索引位置的节点为红黑树节点，会触发红黑树节点转链表节点（untreeify）
为什么用红黑树而不用二叉树
二叉树在插入时如果所有元素都小于根节点，则二叉树是不平衡，查找时间大大增加
线程安全的concurrenthashmap
ConcurrentHashmap 的数据结构大致与hashmap 相似，也是数组加链表的模式，但对数据进行了分段，在插入数据时需要计算插入到哪个段里。
ConcurrentHashMap如何实现线程安全 ConcurrentHashMap 采用了分段锁技术，其中 Segment 继承于 ReentrantLock。不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理，理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment 数组数量)的线程并发。每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。