Java面试-集合

时间：2020-07-13 21:08:32 阅读：63 评论：0 收藏：0 [点我收藏+]

Collection
- List
  - ArrayList
  - Vector
  - LinkedList
- Set
  - HshSet
  - TreeSet
  - LinkedHashSet
- Queue　　
Map
- HashMap
- ConcurrentHashMap
- HashTable
- TreeMap
- LinkedHashMap

1. Colection

1.1 List

1.1.1 ArrayList

底层由数组实现；
插入代价大：O(n)；
适合进行查询操作：O(1)；
线程不安全；
实例化ArrayLisr时不初始化容量，第一次调用add()方法时进行长度初始化，初始长度：10；
扩容：容量不足时扩容，使用向右移位，则为当前容量的1.5倍；
```
int newCapacity = oldCapacity + (oldCapacity >> 1);
```

1.1.2 Vector

底层由数组实现；
支持线程同步（synchronized）；
效率低于ArrayList（由于支持线程同步）
初始化时则初始化容量：10；
扩容：每次扩容为原来两倍；
```
int newCapacity = oldCapacity * 2;
```

1.1.2 LinkedList

链表结构
插入、删除操作速度快O(n)；

1.2 Set

1.2.1 HashSet

不按照存入顺序存储　
当 hashcode相等 && equals返回true 时使用链表向下顺延；

1.2.2 TreeSet

1.2.3 LinkedHshSet

2 Map

2.1 HashMap

2.1.1 java 7

非线程安全
底层实现：数组+链表
重要参数：
- Capacity：数组容量，保持2ⁿ，初始值为16，扩容后为当前容量2倍；（为什么为2ⁿ：为了使散列更均匀，极端情况下查询效率将由O(1)下降为O(n)）
- LoadFactor：负载因子，默认为0.75；
- Threadhold：扩容阈值，Threadhold = Capacity * LoadFactor，当存储量超过扩容阈值时，Hashmap将进行扩容。

2.1.2 java 8

非线程安全
底层实现：数组+链表+红黑树
引入红黑树，查询效率由O(n)下降为O(logn)
HashMap之put方法流程 ^[1]：

1、put(key, value)中直接调用了内部的putVal方法，并且先对key进行了hash操作；

2、putVal方法中，先检查HashMap数据结构中的索引数组表是否位空，如果是的话则进行一次resize操作；

3、以HashMap索引数组表的长度减一与key的hash值进行与运算，得出在数组中的索引，如果索引指定的位置值为空，则新建一个k-v的新节点；

4、如果不满足的3的条件，则说明索引指定的数组位置的已经存在内容，这个时候称之碰撞出现；

5、在上面判断流程走完之后，计算HashMap全局的modCount值，以便对外部并发的迭代操作提供修改的Fail-fast判断提供依据，于此同时增加map中的记录数，并判断记录数是否触及容量扩充的阈值，触及则进行一轮resize操作；

6、在步骤4中出现碰撞情况时，从步骤7开始展开新一轮逻辑判断和处理；

7、判断key索引到的节点（暂且称作被碰撞节点）的hash、key是否和当前待插入节点（新节点）的一致，如果是一致的话，则先保存记录下该节点；如果新旧节点的内容不一致时，则再看被碰撞节点是否是树（TreeNode）类型，如果是树类型的话，则按照树的操作去追加新节点内容；如果被碰撞节点不是树类型，则说明当前发生的碰撞在链表中（此时链表尚未转为红黑树），此时进入一轮循环处理逻辑中；

8、循环中，先判断被碰撞节点的后继节点是否为空，为空则将新节点作为后继节点，作为后继节点之后并判断当前链表长度是否超过最大允许链表长度8，如果大于的话，需要进行一轮是否转树的操作；如果在一开始后继节点不为空，则先判断后继节点是否与新节点相同，相同的话就记录并跳出循环；如果两个条件判断都满足则继续循环，直至进入某一个条件判断然后跳出循环；

9、步骤8中转树的操作treeifyBin，如果map的索引表为空或者当前索引表长度还小于64（最大转红黑树的索引数组表长度），那么进行resize操作就行了；否则，如果被碰撞节点不为空，那么就顺着被碰撞节点这条树往后新增该新节点；

10、最后，回到那个被记住的被碰撞节点，如果它不为空，默认情况下，新节点的值将会替换被碰撞节点的值，同时返回被碰撞节点的值（V）。