一.集合常见原理问题
1、集合初始化的容量为多少？集合容量因子为多少？
2、集合的底层数据结构是什么？
3、集合增删改查的方法如何实现？
4、集合如何扩容？
5、集合的快速失败机制？怎么避免？
6、集合的独有特性？
首先了解下快速失败机制是什么？
就是在迭代的时候不能对集合做修改，否则会抛concurrentModifyException，java.util包下面的所有的集合类都是快速失败的。
下面介绍下几个常见的集合。
一、ArrayList
1.arrayList的初始化容量是10，不存在容量因子。
2.底层是数组结构。
3.用的对数组操作的增删改查，利于arraycopy方法对数组进行移动位置赋值，remove方法会让下标到数组末尾的元素向前移动一个单位，并把最后一位的值置空，方便GC，对应数组的修改操作都会有一个modCount做++记录，内部迭代时expectCount = modCount,然后判断expectCount == modCount从而判断是不是并发修改过。
4.每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。数组扩容通过一个公开的方法ensureCapacity(int minCapacity)来实现。在实际添加大量元素前，我也可以使用ensureCapacity来手动增加ArrayList实例的容量，以减少递增式再分配的数量。数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。
5.存在快速失败机制，可以通过调用arrayList内部迭代器的remove方法，避免快速失败。
6.常用的可变长度数组list，遍历方便，查询方便，保留插入顺序性。List接口的可变数组非同步实现，并允许包括null在内的所有元素。
二、LinkedList
1.LinkedList的初始化容量是一个header一个节点，用于表示一个空的链表。链表结构可以一直递加数据。
2.底层是双向链表结构。
3.对链表节点的指向操作。get操作是一个二分查找，判断节点index是小于链表长度/2还是大于，小于则从链表头遍历，大于则从链表尾部遍历。
4.链表结构不用考虑扩容问题。
5.存在快速失败机制，可通过内部迭代器的remove方法，避免快速失败。
6.链表结构插入方便，LinkedList是List接口的双向链表非同步实现，并允许包括null在内的所有元素。
三、HashMap
1.HashMap的初始化容量是16，容量因子是0.75。hash取模来保证分布均匀，为了提高效率，初始化时HashMap的容量总是2的n次方，即底层数组的长度总是为2的n次方，当length总是 2 的n次方时，jdk1.7使用hash& (length-1)运算等价于对length取模，也就是hash%length，但是&比%具有更高的效率，定位到index后进行插入操作,jdk1.8后改为hash&length，提高了效率，在进行扩容的时候，重新定位的index的链表顺序是不变的，1.7会变成倒叙，且1.8原来的index位置不会变。
2.底层是数组加单链表，1.8以后是当链表的长度超度8时，转换成数组加红黑树。
3.计算hashcode，再进行操作。插入操作是在表头插入。
4.在插入新值的时候，如果当前的 size 已经达到了阈值，并且要插入的数组位置上已经有元素，那么就会触发扩容，扩容后，数组大小为原来的 2 倍。因为为双倍扩容，所有当把旧值分配到新的数组上时，会将原来 table[i] 中的链表的所有节点，分拆到新的数组的 newTable[i] 和 newTable[i + oldLength] 位置上，如原来 table[0] 处的链表中的所有元素会被分配到新数组中 newTable[0] 和 newTable[16] 这两个位置。
5.存在快速失败机制，也可以用内部迭代器的remove方法，避免快速失败。
6.查找O(1),HashMap是基于哈希表的Map接口的非同步实现，允许使用null值和null键，但不保证映射的顺序。HashMap进行数组扩容需要重新计算扩容后每个元素在数组中的位置，很耗性能。
四、Hashtable
1.Hashtable的初始化容量是11，容量因子是0.75。
2.底层是数组加单链表。
3.同hashmap.
4.调整Hashtable的长度，将长度变成原来的(2倍+1)。
5.存在快速失败机制，也可以用内部迭代器的remove方法，避免快速失败。
6.Hashtable是基于哈希表的Map接口的同步实现，不允许使用null值和null键。synchronized是针对整张Hash表的，即每次锁住整张表让线程独占。
五、ConcurrentHashMap
1.ConcurrentHashMap初始化16个segment,也即16个锁，cap就是segment里HashEntry数组的长度，初始化为1，容量因子为0.75。为了能通过按位与的哈希算法来定位segments数组的索引，必须保证segments数组的长度是2的N次方。因此性能比hashtable快16倍。
针对1.8发现因为没segment,纯用volatile HashEntry，则初始化长度也为16，也即cap=16,容量因子为0.75。
2.底层是Segment+hashEntry实现，hashEntry类似hashmap。1.8用volatile HashEntry。
3.用的ReentrantLock，读写锁分类。所有的操作都是先定位segment,定位进行再哈希，其目的是为了减少哈希冲突，使元素能够均匀的分布在不同的Segment上，从而提高容器的存取效率。segments[(hash >>> segmentShift) & segmentMask]。1.8去掉了定位segment的步骤，直接计算hash值定位。
hashEntry里的value的值用voliate修饰，避免了加锁，其他属性用final修饰，保证了不可变，因此，put操作是在表头操作，remove操作则需要将要删除节点的前面所有节点整个复制一遍，最后一个节点指向要删除结点的下一个结点。
4.同hashmap。扩容也是2倍，迁移数据比较复杂，可细细研究。
5.不存在快速失败机制。
6.使用的片段分离锁技术。ConcurrentHashMap完全允许多个读操作并发进行，读操作并不需要加锁。如果使用传统的技术，如HashMap中的实现，如果允许可以在hash链的中间添加或删除元素，读操作不加锁将得到不一致的数据。ConcurrentHashMap实现技术是保证HashEntry几乎是不可变的
jdk1.8的修改
改进一：取消segments字段，直接采用transient volatile HashEntry<K,V>[] table保存数据，采用table数组元素作为锁，从而实现了对每一行数据进行加锁，进一步减少并发冲突的概率。
改进二：将原先table数组＋单向链表的数据结构，变更为table数组＋单向链表＋红黑树的结构。对于hash表来说，最核心的能力在于将key hash之后能均匀的分布在数组中。如果hash之后散列的很均匀，那么table数组中的每个队列长度主要为0或者1。但实际情况并非总是如此理想，虽然ConcurrentHashMap类默认的加载因子为0.75，但是在数据量过大或者运气不佳的情况下，还是会存在一些队列长度过长的情况，如果还是采用单向列表方式，那么查询某个节点的时间复杂度为O(n)；因此，对于个数超过8(默认值)的列表，jdk1.8中采用了红黑树的结构，那么查询的时间复杂度可以降低到O(logN)，可以改进性能。
六、HashSet
1.HashSet初始化容量为16，容量因子为0.75，实际是它是一个hashmap实例。
2.底层结果是hashmap。
3.封装了hashmap的方法，不是key-value，只关注Key，内部实现默认value,保证了key不重复。
4.同hashmap。扩容也是2倍。
5.存在快速失败机制，也可以用内部迭代器的remove方法，避免快速失败。
6.HashSet由哈希表(实际上是一个HashMap实例)支持，不保证set的迭代顺序，并允许使用null元素。
七、LinkedHashMap
1.LinkedHashMap初始化容量为16，容量因子为0.75，因为继承hashmap,accessOrder=false，默认是插入排序。
2.底层使用哈希表与双向链表。
3. LinkedHashMap重写了父类HashMap的get方法，实际在调用父类getEntry()方法取得查找的元素后，再判断当排序模式accessOrder为true时，记录访问顺序，将最新访问的元素添加到双向链表的表头，并从原来的位置删除。由于的链表的增加、删除操作是常量级的，故并不会带来性能的损失。// 记录访问顺序（e.recordAccess(this); ）
LinkedHashMap并未重写父类HashMap的put方法，而是重写了父类HashMap的put方法调用的子方法void addEntry(int hash, K key, V value, int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex)，提供了自己特有的双向链接列表的实现
4.同hashmap。扩容也是2倍。
5.存在快速失败机制，可通过内部迭代器的remove方法，避免快速失败。
6.LinkedHashMap继承于HashMap，它是非同步，允许使用null值和null键。
基本操作与父类HashMap相似，通过重写HashMap相关方法，重新定义了数组中保存的元素Entry，来实现自己的链接列表特性。该Entry除了保存当前对象的引用外，还保存了其上一个元素before和下一个元素after的引用，从而构成了双向链接列表。
两个排序， LinkedHashMap定义了排序模式accessOrder，该属性为boolean型变量，对于访问顺序，为true；对于插入顺序，则为false。
removeEldestEntry方法
在LinkedHashMap中默认返回是false，当需要实现LRU算法的时候继承LinkedHashMap的子类重写这个方法即可，accessOrder 需要初始化为true.
八、LinkedHashSet
1.继承HashSet,初始化容量为16，容量因子为0.75.
2.底层构造一个LinkedHashMap来实现，在相关操作上与父类HashSet的操作相同，直接调用父类HashSet的方法即可
3.封装LinkedHashMap方法，只关注key。
4.同LinkedHashMap。扩容也是2倍。
5.存在快速失败机制，可通过内部迭代器的remove方法，避免快速失败。
6. LinkedHashSet是具有可预知迭代顺序的Set接口的哈希表和链接列表实现。此实现与HashSet的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可为插入顺序或是访问顺序。
网友评论