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

2016-10-26 22:28:00
admin
原创 1394
摘要:集合类对比 集合类实现细节 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)

发表评论
评论通过审核之后才会显示。