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 位就是这么计算得来的。