fail-fast机制
容器内存储一个变量为modCount来记录容器结构发生变化的次数，结构发生变化是指添加或删除一个元素所有操作、或改变容器内部数组大小，仅仅是设置值并不算结构发生变化
在进行序列化或迭代器迭代操作时，会比较modCount与expectedModecount是否相等，如果不等则抛出ConcurrentModificationException
另外通过迭代器自带的方法去add()或remove()是不会改变modCount的。
ArrayList和LinkedLIst的区别
- 底层数据结构：
- ArrayList底层使用Object数组
- LinkedList使用双向链表（JDK1.6之前为循环链表，JDK取消了循环）
- 插入和删除元素：
- ArrayList采用数组，执行
add(E element)在末尾添加删除元素时为O(1)，执行add(int index,E element)在指定位置i插入和删除元素时间复杂度就为O(n)。
- ArrayList采用数组，执行
- LinkedList采用链表，所以对于
add(E e)方法的插入，删除元素时间复杂度不受元素位置的影响，近似 O(1)，如果是要在指定位置i插入和删除元素的话（(add(int index, E element)） 时间复杂度近似为o(n))因为需要先移动到指定位置再插入。
- LinkedList采用链表，所以对于
- 是否支持快速随机访问：
ArrayList支持快速随机访问。 - 内存空间占用：
- ArrayLIst空间浪费主要体现在list列表的结尾会预留一定的容量空间
- LinkedList的空间花费是在每一个元素都要消耗比ArrayList更多的空间（因为在存放前指针和后指针）
RandomAccess接口作用
RandomAccess（以下简称RA）为标记接口，实际上接口内没有定义任何东西。
RA标记了这个类具有随机访问的功能。
比如在binarySearch()中，如果判断该类是RA的实例，则调用indexedBinarySearch()方法，如果不是，则调用iteratorBinarySearch()方法。
容器的线程安全如何解决
- 使用Collections工具类下的synchronized方法将容器变为线程安全容器
- 使用
java.util.concurrent包中的并发容器ConcurrentHashMap：可以看做线程安全的HashMapCopyOnWriteArrayList：可以看做线程安全的ArrayList，适合读多写少的场景ConcurrentLinkedQueue：并发非阻塞队列，使用链表实现。BlockingQueue：表示阻塞队列，可以用于数据共享的通道ConcurrentSkipListMap：跳表的实现。
HashMap和HashTable的区别
- HashMap线程不安全，HashTable线程安全，因为HashTable内部的方法基本都经过Synchronized的修饰
- 因为线程安全的问题，HashMap效率比较高一些。
- HashMap可以存储key和value为null的键值对，但null作为key只能有一个，null为value可以有多个。而HashTable不允许有key和value为null，否则抛出NullPointerException
- 初始容量大小和每次扩容量大小不同：
- 若不指定容量初始值，HashTable默认初始化大小为11，之后每次扩容，容量变为原来大小的2n+1
- 若不指定容量初始值，HashMap初始大小为16，之后每次扩容为原来的两倍。
- 在创建时，HashTable会直接使用参数给定的大小，而HashMap会扩大为大于这个数的最小二的幂次方。
- JDK1.8HashMap在哈希桶中的链表如果长度大于阈值（默认为8），并且当前数组长度小于64就会将该链表转化为红黑树。而HashTable没有这样的机制。
HashSet如何检查重复
- 先计算对象的hashcode来判断是否有重复，如果没有相同Hashcode的对象，就认为没有重复。
- 如果有相同HashCode的对象，这是会调用
equals()方法来检测HashCode相同的对象是否真的相同。
HashSet使用HashMap实现，因HashMap的Key须唯一，所以可以将我们需要存放的数据放到Key，而所有的value对应一个内部的对象PRESENT即可。
private static final Object PRESENT = new Object();
为什么要设置一个PRESENT?因为hashset的add方法通过return map.put(e, PRESENT)==null来判断插入是否成功，而HashMap对于覆盖的情况是返回oldvalue，对于插入是返回null，但如果插入的value为null，则无论是插入还是覆盖都为true，所以要使用一个虚拟值PRESENT来区别一下
HashMap实现
JDK1.8之前
JDK1.8之前底层使用的是数组+链表，将key的hashcode经过扰动函数处理后得出hash值，再将hash值按位与上数组的长度掩码得出当前元素在数组的存放位置，若数组该位置不为空则比较key是否相等，相等的话则直接覆盖，不相等的话且该位置存在链表，就使用拉链法，一边遍历一边比对key是否相等，相等则覆盖，若遍历到链表尾，说明没有key相等值覆盖的情况，这时则直接插入。
JDK1.8之后
主要改动在解决Hash冲突上，当链表长度大于阈值（默认为8），并且当前数组长度大于等于64，会将链表转换为红黑树以减少搜索时间，若数组长度小于64，优先对数组进行扩容。
HashMap的长度为什么是2的幂次方
Hash值是以整型存储，取值范围和整型的范围一样，这个值可能过于大所有不能直接拿来直接用，我们需要的是Hash值限制在数组长度之内，这样就能通过hash确定对象在数组的位置。所以采用的做法是保证HashMap长度为2的幂次方，再将长度减一和hash做与运算，这样就得出在数组的存放位置。之所以不用hash取余数组长度，是因为取余运算相较于二进制的与运算，运算效率不够高。
ConcurrentHashMap底层实现
JDK1.7
JDK1.7采用Segment分段锁和HashEntry数组组成，将数组分为一段一段并给每段数据分配锁，不同线程需要对HashEntry数组中的数据修改时，必须先获得对应的Segment锁，通过这样实现并发。
JDK1.8
取消分段锁，采用CAS和synchronized来保证线程安全，数据结构和HashMap的结构类似，采用Node数组+链表或红黑树，链表长度超过阈值并且数组长度大于等于64会转换为红黑树。synchronized锁只锁住Node的头结点，故只要不产生哈希冲突，就不会有锁阻塞，并发程度提高。
若有收获，就点个赞吧
0 人点赞
