Collection

Set

HashSet

1. 内部是通过hashmap来实现的
2. add（E e） 添加的元素是key ,value是一个空对象

3. 只能通过迭代器遍历 遍历map的key

   TreeSet

4. 内部通过TreeMap实现

5. 可以进行排序

   List

   Vector

6. 线程安全

7. 和Arraylist一样，加了同步

ArrayList

1. 底层是数组，默认大小为10
2. 扩容逻辑: 原大小+(原大小*1/2)
3. add(index，e) 将源数据拷贝到index+1位置 element[index] = e

4. 线程不安全

   LinkedList

5. 双向链表

6. 查找逻辑：如果index <size/2 则从前面找 大于这从后面找
7. 线程不安全

8. node 保存当前数据，前一个节点，后一个节点

   CopyArrayList

9. 读写分离。写会复制一份进行操作，然后再替换掉

10. 优点
    1. 读写分离，线程安全

11. 缺点

    1. 写的时候需要拷贝一份，内存消耗大
    2. 读的时候有可能获取不到最新值

       Map

       HashMap

12. 实现原理

    1. 数组+链表，小于8个value时候，put计算hash值存放在hash表中，如果出现hash冲突，则通过链表方式将冲突的值放在末尾
    2. 红黑树，搜索时间为O(logn) 大于8个value的时候
13. resize
    1. 给数组扩容，扩容为旧表的2倍
    2. 当++size>阈值的时候进行扩容
    3. 扩容后遍历整个结构，把所有的元素重新hash 添加到新表中
14. 两个hashcode 相等通过key.equls获取对应的value

15. get 方法，如果存在旧值会返回旧值

    LinkedHashMap

16. 实现原理

    1. 继承于HashMap 在此基础上增加了链表内容，双向链表，Entry 中增加了前一个结点和后一个节点 可用于实现Lru算法
    2. 插入默认在尾部，每次访问会把最新的放到尾部

       ConcurrentHashMap

17. 1.8实现原理

    1. 整体的实现与hashmap类似，加入了CAS+Synchoronized 保证并发安全性
18. put实现
    1. 根据key计算出hashcode
    2. 判断是否需要初始化
    3. 通过key定位出node 如果node== null 则可以写入数据，利用CAS尝试写入，如果失败则自旋保证成功
    4. 如果hashcode ==-1 则需要扩容
    5. 如果以上都不满足，则利用synchroized 锁住node写入数据
    6. 如果size>8 则转为红黑树
19. get 处理流程与HashMap一致