Java-Collection学习分享

方法说明：

有序集合
可以通过下标访问元素，get()
可以有重复的数据
可以有空数据，且可以有多个空数据

问题：
1、linkedList和ArrayList的区别：
（1）数据结构：linkedList是基于双向链表，ArrayList是基于数组。
（2）读写性能：ArrayList随机访问性能更快。尾部插入性能无差异，中间插入linkedList性能更快。
（3）扩容机制：ArrayList空间不足时需要扩容，初始是10，每次扩容1.5倍，即15。
（4）空间占用：linkedList占用空间更大。

2、linkedList的随机访问：
如果下标小于size的一半，则从首端开始遍历；否则从尾端开始遍历。

3、Vector：
Vector和ArrayList相似，但是Vector是同步的，因为Vector中的方法都是synchronized方法。

无序集合
不可以通过下标访问元素
不可以有重复的数据
只可以有一个空数据

问题：
1、Set如何判断是否重复：
根据boolean equals(Object o);和int hashCode();两个方法来判断。先执行hashCode方法，如果返回值在集合中已存在，则继续执行equals方法，如果返回true，则证明该元素在集合中已经存在，此时将新的元素覆盖老的元素；否则证明该元素在集合中不存在，此时直接将新的元素加入集合。

队列是一种先进先出（Firsr In First Out）的线性表，简称FIFO。只允许在队尾进行插入操作，在队头进行删除操作。
有序集合
不可以通过下标访问元素
可以有重复的数据
可以有空数据，且可以有多个空数据

问题：
1、Deque：
Deque支持在两端插入和移除元素，Java官方推荐使用Deque替代Stack使用。

2、PriorityQueue：
优先队列，能保证每次取出的元素都是队列中权值最小的。元素权值可以是元素本身的自然顺序，也可以通过构造时传入的比较器（Comparator）来决定。

有序集合
不可以通过下标访问元素
可以有重复的数据
可以有空数据，且可以有多个空数据

Map和Collection两者在代码上看没有什么关系，但是map可以产生Collection或与Collection相关的东西：Map.keySet()、Map.entrySet()、Map.values()。

HashMap采用数组+链表进行存储。
HashMap的主干是一个哈希表（数组）。将key传入哈希函数得到哈希值，即该元素在哈希表中的位置。当不同的key的哈希值相同时，出现了哈希冲突问题，采用链地址法解决此问题。

// HashMap部分属性
// 哈希表
transient Node[] table;

// 阈值 threshold = table.length * loadFactor
int threshold;

// 负载因子
final float loadFactor;

哈希表默认大小为16，当哈希表中的元素数量超过threshold，则对哈希表进行扩容，大小变成原来的两倍。

问题
1、为什么扩容为之前的两倍？

当哈希表被首次使用时，才进行初始化，避免初始化后不使用而造成的浪费问题。

当链表中的元素数量大于等于8，且哈希表的大小大于等于64时（避免在哈希表建立初期，多个键值对恰好被放入了同一个链表中而导致不必要的转化），将链表改造成红黑树。

问题
1、为什么要树化？
链表的插入删除时间复杂度是O(1)，但是查询时间复杂度是O(n)；红黑树的插入、删除、查询的最差时间复杂度为O(logn)，如果哈希冲突比较严重时，提升查询的性能，避免 hash 攻击，造成安全问题。

linkedHashMap和HashMap相似，不同的点在于linkedHashMap维持了元素的插入顺序。

linkedHashMap通过before和after来维持元素的插入顺序。
当指定accessOrder=true时，linkedHashMap按照访问顺序排序，即每次访问一个元素之后，都会将该元素放到尾端。
补充：linkedHashMap和TreeMap的有序是不一样的，TreeMap是按照key排序。

参考较多且杂，如果有雷同的，请联系我加上参考地址。