集合

1.集合

collection

• list:特点:

  • arraylist

    • ArraysList:底层基于数组（有序有下标，默认为10），查询和修改快，删除和新增慢
    • 长度是10，超过的时候会进行1.5倍的增长

  • linkedList

    • LinkedList:底层基于双链结构
    • 基于链表，有序，可重复的

  • Vector

    • vector：线程安全的（所有方法都加了锁）

  • 数组和链表在堆内存中：

    • 数组：连续空间固定长度（已知长度时，数组节省空间）
      链表：空间分配不固定（当未知长度时，链表更节省）

  • 有序，可重复

• set:特点:

  • hashset

  • TreeSet

    • 有序，不重复；key不能为空，value可以为null（总结一点：凡是有Tree的集合，都是有序的，凡是有Set的就是不重复的）实现一个compare的接口，

  • 无序不可重复

map

• map

  • 默认值16
    负载因子0.75f（扩容大小,默认的值*负载因子）
    当数据到12位是会自动扩容

当索引位置节点增加到9个时，并且数组长度大于等于64时，链表变为红黑树

当同一个索引位置的节点移除后达到6个时，并且索引位置节点位红黑树节点，红黑树会转成链表节点

在同一个索引位置下加节点也叫拉链法
- 数组扩容：初始容量为16，初始的负载因子为0.75，但数组超过12的时候，会进行扩容，两倍的增长
- 链表：使用hash值来计算储存的位置，如果该位置已经有了不为空，那么会创建出一个链表，链表节点的最大值是8，如果是长度大于64的时候会自动转为红黑树
- 红黑树：使用红黑树查询高于普通列表，因为是使用的二分查找效率要高于顺序查找并且会保持效率。如果当数量小于6的时候会自动转换成链表。

• hashmap

  • 1.结构

    • jdk1.8之前是数组+链表，之后是数组+链表+红黑树

  • 2.特性,特点

    • 以键值对的方式存在key不能重复，value可以重复，属于线程不安全

  • 3.初始值

    • 1.初始长度
    • 2.什么时候扩容
    • 3.什么时候转红黑树
    • 4.什么时候转链表

  • 为什么1.8使用数组+链表+红黑树

    • 一开始数据存数组如果发生hash冲突，这个时候需要把冲突的数据放到后面的链表中（链地址法），如果hash冲突的数据过多，就会让链表过长，查询效率会变低，所以jdk1.8之后当链表长度大于8时就是转化为红黑树。其中换会牵涉到一个数组扩
    • 数组的话是同各国hash冲突，会把冲突的数据放在链表中进行链地址法，如果过多的链表的效率就会变低会转为红黑树

• HashTable

  • 1.特点,特性

    • 不允许key和value为null

  • 2.结构

    • 属于线程安全

  • 3初始值

    • HashTable的初始值是11，扩容 2 * n + 1。HashTable是线程安全的，同步机制决定了它无法追求运行速度上的极致。

• ConcurrentHashMap

  • 1.特性

    • 可以看作是线程安全的hashmap

  • 2.数据结构

    • 在jdk1.8之后就使用node和cas配合使用，相当于在原有的基础上加上红黑树

  • 3.初始值

  • 4.与hashmap对比的优势

  • ConcurrentHashMap实现的原理 ：分段锁机制，在对象中保存一个Segment数组，将整个Hash表划分为多段；每一个Segment元素都类似域一个Hashtable,根据哈希值定位具体的Segment元素，然后对该Segment元素加锁，从而实现多线程开发的安全性

• 哈希冲突解决

  • 1在hash
    2拉链法
    3地址法