ArrayList

1. 初始化时长度为0
2. 添加一个数字后长度变为10
3. 后面每添加一个数字，校验（动态数组）长度够不够，不够的话长度扩充为原来的1.5倍
4. 如果声明时指定了长度，底层调用的就是新建这个长度的数组，没有扩容
   

   数组与list相互转换

5. list = Arrays.asList(array);这里面array修改时，list受到影响(只涉及引用，未创建新对象)

6. T[] array = list.toArray(new T[size]);list改变时，array不受影响（使用了System.arraycopy(),创建了新的对象）

   与LinkedList

   1. 都是线程不安全的
   2. 为保证线程安全可以：
      • 在方法内使用，局部变量是线程安全的
      • Collections.syncronizedList(new LinkedList<>());来创建list对象

HashMap

数据结构实现

• java8之前是数组+链表，java8之后是数组+链表或数组+红黑树。
• 链表长度大于8且数组长度大于64时会采用红黑树提高性能（同时也能防止ddos），在扩容时树节点小于等于6个又会退化成链表

代码实现

• 懒加载，初始化时未加载数组
• 默认加载因子为0.75
• 第一次添加元素或者长度大于数组长度*加载因子时就会扩容（第一次添加为16）
• 扩容的长度为原来的2倍
• 然后遍历旧数组，把原来的老的元素存到新的数组中（原哈希值与运算老的长度等于零则留在老的位置，否则移到老位置+老数组长度）
• 哈希值运算（扰动算法）：（h = key.hashCode()）^(h>>>16)为的是让其更加均匀
• 取模运算：hash &（n-1），当n为2的n次幂时，这完全等价于hash%n但效率更高

冲突解决

- 散列冲突-拉链法：每个下标称之为桶（bucket）或者槽（slot），每个桶或者槽对应一个链表

concurrentHashMap

1. jdk1.7之前
   • hashcode->segment(数组默认为8，一定为2的幂次方)->对应的（原）hashMap（最小与默认为2），长度为两个相乘（默认为16）
   • 算出的段不同则不需要加锁，相同则使用分段锁提高性能
   • 修改时先使用tryLock（）非阻塞加锁，自旋了64次（多核，单核为1次）之后会改用lock加锁。
   • 调用put方法会查看key是否存在（可在自旋时检查），存在则直接覆盖，不存在则创建
   • 创建时会多次检测是否已经创建，使用了cas方法（不加锁），最终保证只会创建一个对象
2. jdk1.8之后
   • 进入乐观锁，进行初始化操作（如果还没初始化）
   • cas去判空与新建与1.7一样
   • 如果需要扩容，先扩容
   • （产生哈希冲突）加锁，遍历链表，选择覆盖操作还是新建操作，调用的syncronized的锁

Hashtable与concurrentHashMap区别

同步性

• Hashtable： 整个Hashtable 的方法都是同步的，即每个方法都被 synchronized 关键字修饰，保证了线程安全。这意味着在并发访问时，只能有一个线程执行任何Hashtable 方法。
• ConcurrentHashMap： ConcurrentHashMap 使用了更细粒度的锁机制，采用分段锁的方式。不同的段（Segment）上的操作是相互独立的，可以并发执行，提高了并发性能。
  

  Null键值：

• Hashtable： 不允许键或值为null。
• ConcurrentHashMap： 允许null键和null值。
  

  迭代器弱一致性：

• Hashtable： 使用迭代器遍历时是安全的，因为迭代器是同步的，但可能会抛出ConcurrentModificationException 异常。
• ConcurrentHashMap： 支持并发修改，并且迭代器是弱一致的，允许在迭代过程中修改集合，并不一定能够反映出最新的修改。
  

  容量扩充：

• Hashtable： 在容量达到一定阈值时会自动扩充。

• ConcurrentHashMap： 采用了分段锁的设计，每个段都有自己的大小和阈值，因此可以更灵活地进行扩充。

  总体而言，ConcurrentHashMap 是在高并发环境下更推荐使用的 Map 实现，因为它提供了更好的性能和灵活性。但在特定情况下，例如要求完全同步的场景，Hashtable 仍然可以考虑。

ThreaLocal

• 功能： 独立线程与线程之间的数据
• 实现： 一共有三个方法：get（）、set（）、remove（）。看了半天，说人话应该就是新建一个Map（默认16长度），使用哈希取余那套，根据key（线程）去设置到对应的Map中，每次取Map对应的那个value。

bitmap & RoaringBitmap

• bitmap在处理{1，2，3，1000000}时浪费空间，因为他按照最大的那个申请内存。
• RoaringBitmap把前十六位划分为桶，后十六位为arrayContainer或bitmapContainer。。
• arrayContainer初始长度为4位，最大扩容至4096位，超过则转为bitmapContainer。arrayContainer直接存储数字，而非01，因为这种规模的数字直接存内存占用更小，搜索时采用二分搜索。
• bitmapContainer则存储01串，因为一共低位数有十六位，因此大小恒定为8kb，上面的4096位就是这么计算得来的。