集合类对比 集合类实现细节 LinkedHashSet使用介绍 PriorityQueue使用介绍

一、集合类对比

ArrayList、Vector、CopyOnWriteArrayList区别？

1、ArrayList动态空间增长率为50%，Vector动态空间增长率为100%；

2、Vector所有方法都是同步的，迭代器方法也是同步的，线程安全；

3、CopyOnWriteArrayList只有写操作是同步的，写操作都会重新创建一个数组；

4、CopyOnWriteArrayList适合读操作远多于写操作场景，比Vector性能高很多；

HashMap、LinkedHashMap、TreeMap、Hashtable区别？

1、HashMap使用哈希表存储数据，冲突数据使用链表存储，冲突数据更多则用红黑树；

2、IdentityHashMap存储数据时比较key是否同一个对象，expectedMaxSize初始最大容纳元素数量；

3、LinkedHashMap维护元素插入顺序，TreeMap保证元素排序；

4、Hashtable所有方法都是同步的，迭代器方法不同步，线程安全；

HashSet、LinkedHashSet、TreeSet、CopyOnWriteArraySet区别？

1、HashSet使用HashMap实现，LinkedHashSet使用LinkedHashMap实现，TreeSet使用TreeMap实现；

2、HashSet不维护元素插入顺序，LinkedHashSet维护元素插入顺序，TreeSet保证元素排序；

3、CopyOnWriteArraySet使用CopyOnWriteArrayList实现，适合数据量比较小的场景；

AbstractCollection实现细节：

1、AbstractCollection基本上被所有集合类继承；

2、Object[] toArray()，该方法创建一个数组进行元素拷贝；
3、T[] toArray(T[] a)，如果参数容量不够，则会创建一个数组；

ArrayList实现细节：

1、boolean contains(Object elem)，比较方法o==null ? get(i)==null : o.equals(get(i))

2、boolean containsAll(Collection<?> c)，是否包含集合中所有元素；

3、boolean remove(Object o)，最多移除一个元素；

4、boolean removeAll(Collection<?> c)，相同元素移除多个；
5、boolean retainAll(Collection<?> c)，相同元素保留多个；

HashMap实现细节：

1、initialCapacity底层数组长度，loadFactor加载因子；

2、threshold=capacity*loadFactor，size>threshold进行扩容；

Entry实现细节：

1、AbstractMap实现了Map接口的部分方法；

2、AbstractMap.SimpleEntry实现了Map.Entry接口；

3、AbstractMap.SimpleEntry比较方法同时比较key和value；

三、LinkedHashSet使用简介

1、LinkedHashSet使用双向链表维护元素插入顺序信息，插入顺序不受重新插入影响；

2、LinkedHashSet允许插入null元素；

3、LinkedHashSet多线程不安全；

4、System.identityHashCode获取对象默认哈希码，不受hashCode函数重载影响；

5、loadFactor加载因子，哈希表的填满程度，默认容量=initialCapacity*loadFactor=16*0.75=12；

6、加载因子越大空间利用率越大，但冲突高，查找效率低；

7、加载因子越小空间利用率越小，但冲突低，查找效率高；

代码示例：

public static void testLinkedSet() {
LinkedHashSet<String> set= new LinkedHashSet<String>();
set.add("name1");
set.add(null);
set.add("name2");
set.add("name1");
set.add(null);
Iterator<String> iter = set.iterator();
while (iter.hasNext()) {
System.out.println(iter.next());
}
}

输出结果：

name1
null
name2

四、PriorityQueue使用简介

class java.util.AbstractQueue implements Queue
1、E element()，获取队列顶部元素，如果队列为空则抛出NoSuchElementException；

2、E remove()，检索并移除元素，如果队列为空则抛出NoSuchElementException；

class java.util.PriorityQueue extends AbstractQueue
1、boolean add(E o)，插入元素；

2、boolean offer(E o)，插入元素；
3、E poll()，检索并移除元素；
4、E peek()，获取队列顶部元素；

5、boolean remove(Object o)，移除任意元素；

使用详解：

1、PriorityQueue不允许插入null元素，否则抛出NullPointerException；

2、使用二叉堆数据结构，插入和删除顶部元素时间为O(log(n))，获取顶部元素时间为O(1)；