java容器

java容器之集合体系结构知识总结，包括单列集合、双列集合、对比等内容，内容比较多，需要的可以看下。

集合体系结构

• 单列集合(Collection)
  • List
    • ArrayList(1.5倍扩容)
      • 数据结构：底层维护了一个Object数组
      • 扩容机制：如果创建ArrayList不指定大小，初始容量为0，第一次添加元素扩容到10，之后的扩容为原来的1.5倍;如果指定大小，初始容量为指定的值，之后扩容为原来的1.5倍
      • 线程安全性：线程不安全
      • 特点：增删元素效率低，查找元素效率高
    • Vector(线程安全，2倍扩容)
      • 数据结构：底层也维护了一个Object数组
      • 扩容机制：如果创建Vector不指定大小，则初始容量为10，之后扩容为原来的2倍；如果创建Vector指定大小，初始容量为指定的值，之后扩容为原来的2倍
      • 线程安全性：线程安全(Vector类的所有操作方法都被synchronized修饰)
    • LinkedList
      • 数据结构：双向链表
      • 线程安全性：线程不安全
      • 特点：增删元素效率高、查找元素效率低
  • Set
    • HashSet(无序，2倍扩容)
      • 数据结构：底层维护了一个HashMap
      • 扩容机制：第一次添加元素时，数组扩容到16，加载因子为0.75，也就是当所有链表上节点个数之和大于12时，将数组扩容2倍
      • 添加元素：首先计算元素的hash值，然后转为索引值，如果索引位置没有元素，直接插入，如果有元素，则遍历索引位置的链表，用equals比较插入元素与链表元素是否相同，如果相同，则放弃插入，如果与链表所有元素都不同，则将该元素插入链表尾部。
      • 转为红黑树：在jdk1.8之后，如果一条链表元素个数大于等于8，且数组长度大于等于64，则将该链表转化为红黑树；如果链表长度大于等于8，但是数组长度没有超过64，则不会进行树化，而是将数组扩容为原来的2倍。
      • LinkedHashSet(有序)
        • 数据结构：底层是LinkedHashMap，LinkedHashMap底层数据结构是数组+双向链表，每个节点都有前驱和后继属性，能够保证遍历顺序和插入顺序一致。
    • TreeSet(自定义排序)
      • 数据结构：底层是红黑树，适用于需要对元素进行排序的场景
• 双列集合(Map)
  • HashMap
    • 数据结构：底层是数组+链表+红黑树，key不能重复，可以有一个null值，value可以重复，可以有多个null值，不能保证插入元素的顺序，没有实现线程同步，因此是线程不安全的
    • 扩容机制：第一次添加元素时，将数组扩容为16，默认加载因子是0.75，当元素个数超过12时，将数组扩容为原来的2倍
    • 添加元素：当添加一个键值对时，首先根据key计算hash值，然后转换成索引位置，如果索引位置没有元素则直接添加，如果有元素，则用equals方法来判断要插入的key与当前位置的key是否相等，如果相等，则替换value，并返回旧的value，如果不相等，则继续遍历当前节点的后继节点，直到最后一个节点都不相同，则将该键值对插入到链表的末尾。
    • 转为红黑树：在jdk1.8以后，如果链表长度大于等于8，且数组容量超过了64，则将该链表转化为红黑树，当元素个数降为6时，又会将红黑树退化为链表。
    • LinkedHashMap
      • 数据结构：底层是一个双向链表，每个节点都有前驱后继属性，保证了插入顺序与遍历顺序一致。
    • CurrentHashMap
      • jdk1.7版本
        • 数据结构：底层维护了一个Segment数组，Segment类继承了可重入锁ReentrantLock，Segment类内部又维护了一个Entry数组
        • 线程安全机制：读数据不加锁，因为HashEntry中的value变量由volatile修饰，能够保证可见性。在进行写入数据时，只对当前的Segment对象加锁，而其他的Segment对象不加锁，这样就实现了高并发
        • 定位元素：需要进行两次hash操作，第一次定位到具体的Segment对象，第二次定位到元素所在的链表头部。
      • jdk1.8版本
        • 数据结构：摒弃了Segment概念，而是选择了与HashMap相同的Node数组+链表+红黑树结构。
        • 线程安全机制：采用CAS+synchronized来实现更加细粒度的锁。如果插入元素时没有发生hash冲突，直接通过CAS的方式进行赋值，如果出现了冲突，只需要对索引位置的链表头结点进行加锁来保证线程的安全。
  • TreeMap(红黑树)
  • HashTable(2倍+1扩容)
    • 数据结构：底层是一个entry数组，初始容量为11，之后扩容为原来的2倍加1，key和value都不能为空，所有方法都实现了同步机制，因此是线程安全的
    • Properties
• 对比
  • HashMap与HashTable的区别？
    • 数据结构：前者使用数组+链表+红黑树，后者使用数组+链表
    • 扩容机制：前者初始容量为16，扩容时将容量扩容为原来的2倍，后者初始容量为11，扩容时将容量扩容为原来的2倍加一。
    • 允许为空：HashMap允许有一个key为空，允许有多个value为空，HashTable不允许key和value为空
    • 线程安全：前者线程不安全，后者线程安全
  • ConcurrentHashMap在jdk1.7和1.8之间的区别？
    • 数据结构：jdk1.7使用了Segment数组，每一个Segment类内部又维护一个HashEntry数组，jdk1.8使用Node数组+链表+红黑树
    • 线程安全机制：前者采用分段锁机制，其中的Segment继承可重入锁，后者采用CAS+synchronized关键字来实现线程安全。
    • 锁粒度：前者是对一个segment对象加锁，后者是对一个Node节点加锁。
    • hash定位：前者需要两次hash定位，后者只需要一次定位。
    • 查询复杂度：前者是O(N)，后者是O(logN)。
  • HashMap1.7和1.8的区别？
    • 数据结构：前者使用数据+链表，后者使用数据+链表+红黑树
    • 节点实现类：前者是Entry类，后者是Node类
    • 数据插入方式：前者采用头插法，后者采用尾插法
    • hash值计算方式：前者使用9次扰动，即4次位运算和5次异或运算，后者使用2次扰动，1次位运算和一次异或运算
  • ArrayList与LinkedList的区别？
    • 数据结构：ArrayList使用动态数组存储数据，LinkedList使用双向链表存储数据
    • 查询元素：ArrayList可以通过地址进行随机访问元素，查询速度快，LinkedList需要移动指针进行访问元素，查询速度慢
    • 扩容方面：当ArrayList长度达到一定值，需要进行扩容
  • ArrayList与Vector的区别？
    • 扩容方面：ArrayList每次扩容1.5倍，Vector每次扩容2倍
    • 线程安全：ArrayList线程不安全，Vector线程安全
  • Iterator和ListIterator的区别？
    • 前者只能遍历List及其子类，或者可以遍历整个集合
    • ListIterator拥有比Iterator更多的方法
      • ListIterator有hasPrevious()以及previous()方法，因此可以进行前向遍历
      • ListIterator有add()和set()方法，可以进行增加和修改元素
      • ListIterator有nextIndex()和previousIndex()，可以定位当前索引位置
• 待研究
  • 为什么HashMap的length必须是2的n次方？