常见集合容器类简单总结
1 常见集合类,容器汇总如下:
1 collection集合类
List 列表,有序,可重复
Queue 队列,有序,可重复
Set 集合,不可重复
-
- List
Vector ,比较早的集合类了,是JDK1.0版本添加的类,他继承于AbstractList,实现了接口库List,RandomAccess,和Cloneable。
Vector实现了List,所以它能够为队列提供:增加,删除,修改,遍历等操作。
Vector实现RandomAccess接口,他使队列能够快速访问(即通过索引值就能访问得到)。
Vector实现了Cloneable接口,他使队列能够被克隆。
Vector和ArrayList不同,他的操作是线程安全的。
底层很多方法都是加了synchronized锁的。
ArrayList
ArrayList其实是一个数组队列,其实是一个动态数组;和JAVA的数组相比,他能够动态的变化,他继承于AbstractList,而且还实现了List,RandomAccess,Cloneable,Serializable接口。
ArrayList实现了List接口,为自己提供了,添加、删除、清空、修改、遍历等功能。
ArrayList实现了RandomAccess接口,为数组队列提供了随机访问的功能(在队列中,访问某个节点都必须按照先后顺序),就是通过元素的序号访问到元素的值(ArrayList中还有Iterator迭代访问)
ArrayList 实现了Cloneable接口,即覆盖了函数clone(),能被克隆。
ArrayList 实现java.io.Serializable接口,这意味着ArrayList支持序列化,能通过序列化去传输。
但是ArrayList不是线程安全的。
- LinkedList是一个继承于AbstractSequentialList的双向链表。也可以当做堆栈、队列、双端队列进行操作。
- LinkedList实现List接口,能够对LinkedList实现基本的操作。
- LinkedList实现Deque接口即能将LinkedList当做双端端口使用
- LinkedList不是同步的
- LinkedList实现了Cloneable接口,能够对LinkedList实现克隆。
- LinkedList实现了Serializable接口,能够支持序列化操作。
- LinkedList继承于AbstractSequentialList,并且实现了Dequeue接口。
- LinkedList包含两个重要的成员:header 和 size。header是双向链表的表头,它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量: previous, next, element。其中,previous是该节点的上一个节点,next是该节点的下一个节点,element是该节点所包含的值。 size是双向链表中节点的个数。
LinkedList实际上是通过双向链表去实现的。既然是双向链表,那么它的顺序访问会非常高效,而随机访问效率比较低。
区别:
1.ArrayList是实现了基于动态数组的数据结构,LinkedList是基于链表结构。
2.对于随机访问的get和set方法,ArrayList要优于LinkedList,因为LinkedList要移动指针。
3.对于新增和删除操作add和remove,LinkedList比较占优势,因为ArrayList要移动数据。
优缺点:
1.对ArrayList和LinkedList而言,在列表末尾增加一个元素所花的开销都是固定的。对 ArrayList而言,主要是在内部数组中增加一项,指向所添加的元素,偶尔可能会导致对数组重新进行分配;而对LinkedList而言,这个开销是 统一的,分配一个内部Entry对象。
2.在ArrayList集合中添加或者删除一个元素时,当前的列表所所有的元素都会被移动。而LinkedList集合中添加或者删除一个元素的开销是固定的。
3.LinkedList集合不支持 高效的随机随机访问(RandomAccess),因为可能产生二次项的行为。
4.ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间,而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间
查询操作频繁时用ArrayList,增删操作频繁时用LinkedList。
2 Set
HashSet
HashSet按照Hash算法来存储结合中的元素,因此具有良好的存取和查找的性能。简单的说,HashMap的底层实现是“基于拉链法的散列表”.
LinkedHashSet:使用连表来维护元素,因为需要维护元素的插入顺序,所以性能略低,低于HashSet。
TreeSet:采用红黑树的数据结构来存储集合元素,并且支持两种排序方法,自然排序和定制排序。注意:使用TreeSet时,保证添加的对象全都实现了Comparable接口,否则会添加失败,并且抛出ClassCastExecption异常。简单一句话,如果想要TreeSet正常运行,只能添加同一种类型的对象。
Queue
Queue集合,用于模拟队列的“先进先出的结构”,而且PriorityQueue实现类是一个比较标准的实现类,之所以说是比较标准的,是因为元素并不是按照添加的顺序来排序的,而是按照队列元素大小进行排序的。
Deque接口是Queue的子接口,他代表了一个双端队列,Deque接口的典型实现类:ArrayDeque,是基于数组来实现的,底层数组长度为16
再来说说这个LinkedList,既可以当成队列,也可以当成栈来用。
-ArrayBlockingQueue :由数组支持的有界队列。基于数组的阻塞循环队列,先进先出原则排序。
-LinkedBlockingQueue:由链接节点支持的可选有界队列。基于链表的队列,先进先出排序元素。
-PriorityBlockingQueue:由优先级堆支持的*优先级队列。PriorityBlockingQueue是对PriorityQueue的再次包装,是基于堆数据结构的,当资源耗尽,避免out of memory,添加会阻塞,空队列取元素也会阻塞。
-DelayQueue:由优先级堆支持的、基于时间的调度队列。(基于PriorityQueue来实现的)是一个存放Delayed 元素的*阻塞队列,只有在延迟期满时才能从中提取元素。
-SynchronousQueue:一个利用BlockingQueue接口的简单聚集(rendezvous)机制。元素就直接在消费者和生产者之间传递,永远不会加入到阻塞队列中。
CocurrentLinkedQueue
ConcurrentLinkedQueue是一个基于链表实现的非阻塞队列,
ConcurrentLinkedQueue是一种队列数据结构,数据是FIFO(first input first out)的, 内部采用CAS实现高并发读写安全,而木有采用锁的机制。
Map
HashTable ,HashMap
- Hashtable和HashMap一样都是一个散列表,存储内容也是键值对(Key-Value)映射,区别就是,Hashtable是同步的的,说明Hashtable是线程安全的;Hashtable的键值对也是无序的;但是他的key值、value值,不能为null。底层方法都加了synchronized锁的
- Hashtable继承于Dictionary,实现了Map,Cloneable,java.io.serializable。
- Hashtable的实例的性能受2个因素影响:初始容量和加载因子,并且加载因子默认值也是0.75,和HashMap是一样的。
4 . 但HashMap 是线程不安全的。
针对线程安全的问题,后续又出了
Collections.synchronizedMap(new HashMap<UUID, UUID>());
Collections.synchronizedList(new ArrayList<>());
都是方法加了锁的实现。
public int size() {
synchronized (mutex) {return m.size();}
}
public boolean isEmpty() {
synchronized (mutex) {return m.isEmpty();}
}
public boolean containsKey(Object key) {
synchronized (mutex) {return m.containsKey(key);}
}
public boolean containsValue(Object value) {
synchronized (mutex) {return m.containsValue(value);}
}
public V get(Object key) {
synchronized (mutex) {return m.get(key);}
}
public V put(K key, V value) {
synchronized (mutex) {return m.put(key, value);}
}
public V remove(Object key) {
synchronized (mutex) {return m.remove(key);}
}
public void putAll(Map<? extends K, ? extends V> map) {
synchronized (mutex) {m.putAll(map);}
}
public void clear() {
synchronized (mutex) {m.clear();}
}
Collections.synchronizedList(new ArrayList<>());
public int hashCode() {
synchronized (mutex) {return list.hashCode();}
}
public E get(int index) {
synchronized (mutex) {return list.get(index);}
}
public E set(int index, E element) {
synchronized (mutex) {return list.set(index, element);}
}
public void add(int index, E element) {
synchronized (mutex) {list.add(index, element);}
}
public E remove(int index) {
synchronized (mutex) {return list.remove(index);}
}
public int indexOf(Object o) {
synchronized (mutex) {return list.indexOf(o);}
}
public int lastIndexOf(Object o) {
synchronized (mutex) {return list.lastIndexOf(o);}
}
public boolean addAll(int index, Collection<? extends E> c) {
synchronized (mutex) {return list.addAll(index, c);}
}
由于集合,容器类太多,这里只是简单总结一下,后续在细化讲解。