对于 Java 汇合的局部温习知识点整顿

ArrayList

1. ArrayList 实质上继承了 AbstractList，而 AbstractList 则是继承了 Collection 汇合类，并且 Arraylist 是实现了 List 的接口
2. ArrayList 初始的容量，DEFAULT_CAPACITY = 10，即初始容量为 10，但初始化对象的时候能够传入你自定义的容量最大容量为 Interger.MaxValue-8
3. ArrayList 的默认元素存储，是一个 Object[] 数组
4. ArrayList 源码外面存在一个 ensureCapacity 的办法，用来确认数组的容量是否须要扩容，扩容的时候采纳的是 Arrays.Copyof 的办法，复制元素到一个新的数组
5. 对于 ArrayList 的扩容机制，达到了定义容量（不传入容量的话，即为默认容量）的时候，会动静扩容 1.5 倍，也是采纳上述的复制办法
6. ArrayList 其实是存在手动缩容的办法的，在源码中有叫做 trimToSize() 的办法，个别是手动调用的
7. ArrayList 中删除元素的 Remove 办法其实也是采纳 arraycopy() 的办法来进行元素的挪动，实质跟数组差不多
8. ArrayList 是线程不平安的，外面没有实现线程平安的保障，多线程在拜访的时候，实现的主动扩容也是造成线程不平安的一部分起因。相同，常见的 Vector 基本上是靠 synchronized 来实现线程平安的

HashMap

• HashMap 实现了 Map 接口，初始容量为 16，最大容量为 1 << 30，默认加载因子为 0.75，如果本人传入初始值 K，则容量为大于 K 的 2 次方整数，例如：传入 10 的话，则容量为 16

• HashMap 的插入原理

• 在 JDK1.8 之前，HashMap 应用数组 + 链表实现，即应用链表解决抵触，同一 hash 值的节点都存储在一个链表里。然而当位于一个桶中的元素较多，即 hash 值相等的元素较多时，通过 key 值顺次查找的效率较低。而 JDK1.8 中，HashMap 采纳数组 + 链表 + 红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间，红黑树转链表的阈值是 6

  • hash 函数是通过拿到 key 的 hashcode，而后让 hashcode 的高 16 位和低 16 位进行异或操作，这样设计的起因是尽可能地减小 hash 碰撞，其二是位运算比拟高效

• hashmap 如果采纳头插法的话，在多线程的状况下会产生环，并且 hashmap 在多线程下也是不平安的，在 JDK8 之前的话，是先判断扩容再插入的，而 JDK8 之后则是先插入再判断是否须要扩容，扩容为扩容到原数组大小的 2 倍

  • 扩容的时候 1.7 须要对原数组中的元素进行从新 hash 定位在新数组的地位，1.8 采纳更简略的判断逻辑，地位不变或索引 + 旧容量大小
  • 链表转红黑树，并不是达到 8 个 Node 节点的阈值就进行转换，而是要判断一下整个数据结构中的 Node 数量是否大于 64，大于才会转，小于就会用扩容数组的形式代替红黑树的转换

扩大

Java 中有 HashTable、Collections.synchronizedMap、以及 ConcurrentHashMap 能够实现线程平安的 Map。

1. HashTable 是间接在操作方法上加 synchronized 关键字，锁住整个数组，粒度比拟大；
2. Collections.synchronizedMap 是应用 Collections 汇合工具的外部类，通过传入 Map 封装出一个 SynchronizedMap 对象，外部定义了一个对象锁，办法内通过对象锁实现；
3. ConcurrentHashMap 应用分段锁，升高了锁粒度，让并发度大大提高。