关于Java Collection的几个常用实现类的总结
ArrayList
ArrayList实现了List接口,并且实现了该接口的所有可选操作(replaceAll
,spliterator
,sort
)。
它的大小是可以动态变化的,相当于一个可变长度的数组,它可以存储任何类型的对象,包括null。
The size, isEmpty, get, set,
iterator, and listIterator operations run in constant
time. The add operation runs in amortized constant time,
that is, adding n elements requires O(n) time. All of the other operations
run in linear time (roughly speaking).
size
, isEmpty
, get
, set
, iterator
, listIterator
这些方法的时间复杂度都是都是O(1),add(E e)
的时间复杂度是O(1),add(int index, E element)
的时间复杂度是O(n),其他的方法大多数都是线性时间复杂度O(n)。
该类不是线程安全的,假设要在多线程环境下使用ArrayList,需要使用外部同步
保证对ArrayList的修改对其他线程可见,也可以使用Collections.synchronizedList
方法使得ArrayList的实例变成线程安全的,
比如List list = Collections.synchronizedList(new ArrayList(...))
fail-fast
在调用iterator
或者listIterator
创建了一个迭代器对象之后,假如在使用该迭代器访问元素的过程中通过除了迭代器对象的remove
和add
结构化修改了(一般除了set方法外的修改都是结构化修改)ArrayList里面的元素,就会抛出ConcurrentModificationException
异常。
在没有被正确同步的情况下,该机制有可能会失效。
成员变量
/** |
构造方法
|
常用方法
public void ensureCapacity(int minCapacity)
增加ArrayList的容量public boolean isEmpty()
public boolean contains(Object o)
public int indexOf(Object o)
public int lastIndexOf(Object o)
public E set(int index, E element)
public E get(int index)
public int size()
public boolean add(E e)
public void add(int index, E element)
public E remove(int index)
public boolean remove(Object o)
public void clear()
public boolean addAll(Collection<? extends E> c)
public boolean addAll(int index, Collection<? extends E> c)
从原集合的index位置开始添加c的元素,原集合的index位置后面的元素将移动到最后面public boolean removeAll(Collection<?> c)
public boolean retainAll(Collection<?> c)
交集(仅保留在ArrayList对象和c里面均存在的元素)public Iterator
iterator() public ListIterator
listIterator()
Vector
Vector
类是线程安全的,因此多线程环境下使用Vector
不需要外部同步。它的结构和ArrayList
类似,
可以说它是ArrayList
的线程安全的版本。
成员变量
/** |
构造函数
|
常用方法
public synchronized void setSize(int newSize)
设置链表的elementCount,如果要设置的elementCount比当前的elementCount要大,则往里面填充null对象,否则将清空要设置的大小以外的元素public synchronized int capacity()
获取当前的容量(elementData.length)public synchronized int size()
获取当前存储的元素个数(elementCount)public synchronized boolean isEmpty()
public Enumeration
elements()
返回当前存储元素对象的枚举,和Iterator功能差不多,用于遍历存储的元素。public boolean contains(Object o)
public int indexOf(Object o)
获取特定对象在链表中首次出现的索引,若元素不在链表中则返回-1public synchronized int indexOf(Object o, int index)
从指定位置(index)开始获取特定对象在链表中首次出现的索引,不存在返回-1public synchronized int lastIndexOf(Object o)
public synchronized int lastIndexOf(Object o, int index)
public synchronized E elementAt(int index)
public synchronized E firstElement()
public synchronized E lastElement()
public synchronized void setElementAt(E obj, int index)
public synchronized void removeElementAt(int index)
public synchronized void insertElementAt(E obj, int index)
public synchronized void addElement(E obj)
添加一个元素到尾部public synchronized boolean removeElement(Object obj)
public synchronized void removeAllElements()
public synchronized E get(int index)
public synchronized E set(int index, E element)
public synchronized boolean add(E e)
public boolean remove(Object o)
public void add(int index, E element)
public synchronized E remove(int index)
public void clear()
public synchronized boolean containsAll(Collection<?> c)
如果链表包含c中的所以元素,则返回truepublic synchronized boolean addAll(Collection<? extends E> c)
public synchronized boolean addAll(int index, Collection<? extends E> c)
public synchronized boolean removeAll(Collection<?> c)
public synchronized boolean retainAll(Collection<?> c)
取交集(在该链表和c中均包含的元素)
LinkedList
LinkedList实现了List和Deque接口,它允许存放任何类型的对象,包括null,该类不是线程安全的。
使用索引去访问存储的元素时,将从第一个节点开始遍历到相对应的节点,而不是直接通过索引就能取出元素,因为底层结构改变了,
变成了一个个通过next和prev变量相连接的Node,Node的结构如下:private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
成员变量
transient int size = 0; //存储的元素个数 |
构造方法
/** |
常用方法
public E getFirst()
public E getLast()
public E removeFirst()
public E removeLast()
public void addFirst(E e)
public void addLast(E e)
public boolean contains(Object o)
public int size()
public boolean add(E e)
添加一个元素到链表的尾部public boolean remove(Object o)
移除特定元素(假设有多个相同的元素,将移除在链表最前面出现的元素)public boolean addAll(Collection<? extends E> c)
public boolean addAll(int index, Collection<? extends E> c)
public void clear()
public E get(int index)
public E set(int index, E element)
public void add(int index, E element)
public E remove(int index)
public int indexOf(Object o)
public int lastIndexOf(Object o)
public E peek()
取最后面的元素,只是获取该元素,不移除,当元素不存在时,返回nullpublic E peekFirst()
public E peekLast()
public E element()
和peek方法一样,不过当元素不存在时候,抛出NoSuchElementExceptionpublic E poll()
获取并移除最后面的元素,当元素不存在时,返回nullpublic E pollFirst()
public E pollLast()
public E remove()
和poll方法一样,不过当元素不存在时候,抛出NoSuchElementExceptionpublic boolean offer(E e)
添加元素到最后面public boolean offerFirst(E e)
添加元素到最前面public boolean offerLast(E e)
添加元素到最后面public void push(E e)
添加元素到最前面public E pop()
弹出最前面的元素,push和pop是栈的方法,因为前面的push是添加元素到最前面的,所以现在pop也应该弹出
最前面的元素才符合FIFOpublic boolean removeFirstOccurrence(Object o)
移除第一次出现的特定元素,从fistNode开始到lastNode结束public boolean removeLastOccurrence(Object o)
CopyOnWriteArrayList
和ArrayList类似,不过它是线程安全的,它对的add
和set
等操作都将重新复制原来的数组元素并创建新的数组,
因此开销非常大,一般只用来遍历和查找元素,如果要频繁地增加或改动元素则不应该使用该类。它允许插入null元素。
成员变量
/** The lock protecting all mutators */ |
构造方法
/** |
常用方法
参考ArrayList
List总结
ArrayList
不是线程安全的,Vector
是线程安全的ArayList
的查找操作只需要常数时间,LinkedList
则需要线性时间LinkedList
同时实现了List
和Deque
接口List
中可以包含重复的元素CopyOnWriteArrayList
一般用于多线程中频繁地访问元素的情景
HashMap
HashMap
的实现已经在前几篇博客介绍过了。HashMap
不是线程安全的,它可以存放null键值对
构造函数
|
常用方法
public int size()
public boolean isEmpty()
public V get(Object key)
public boolean containsKey(Object key)
public V put(K key, V value)
public void putAll(Map<? extends K, ? extends V> m)
public V remove(Object key)
public void clear()
public boolean containsValue(Object value)
public Set
keySet()
获取存储的所有键值对的键的Set对象,因为键是没有重复的,因此返回一个Set对象,而不是Listpublic Collection
values()
获取存储的所有键值对的值的Collection对象,因为值可以是可以重复的任意对象,因此返回一个Collection对象public Set<Map.Entry<K,V>> entrySet()
获取存储的所有键值对,键值对被封装进一个Set对象后返回public V getOrDefault(Object key, V defaultValue)
获取某个key的值,如果key不存在则返回默认值(defaultValue)public V putIfAbsent(K key, V value)
当要存放的键值对的键不存在于Map中时才将键值对存放进Map中public boolean remove(Object key, Object value)
当指定的值和要移除的键值对的值相匹配时才移除该键值对public boolean replace(K key, V oldValue, V newValue)
public V replace(K key, V value)
LinkedHashMap
LinkedHashMap
继承了HashMap
并且实现了Map
接口,它的迭代顺序是可预测的(通过它的iterator方法得到的迭代器迭代对象的时候是按照元素插入的时间顺序进行迭代的)。
它一般用来复制Map对象,并能保证复制后的对象的元素顺序和复制前的对象一致。
构造方法
/** |
常用方法
和HashMap一致
Hashtable
Hashtable
功能和HashMap差不多,但Hashtable是线程安全的。Hashtable的实现也在这里介绍过了。
它不能存放null键值对。
构造方法
|
常用方法
public synchronized int size()
public synchronized boolean isEmpty()
public synchronized Enumeration
keys()
获取存储的所有键值对的键,封装成Enumeration类型后返回public synchronized Enumeration
elements()
获取存储的所有键值对的值,封装成Enumeration类型后返回public synchronized boolean contains(Object value)
public boolean containsValue(Object value)
public synchronized boolean containsKey(Object key)
public synchronized V get(Object key)
public synchronized V put(K key, V value)
public synchronized V remove(Object key)
public synchronized boolean remove(Object key, Object value)
当key和value都与Map里面对象的元素匹配时才移除元素public synchronized void putAll(Map<? extends K, ? extends V> t)
public synchronized void clear()
public Set
keySet() public Set<Map.Entry<K,V>> entrySet()
public Collection
values() public synchronized V getOrDefault(Object key, V defaultValue)
public synchronized V putIfAbsent(K key, V value)
public synchronized boolean replace(K key, V oldValue, V newValue)
public synchronized V replace(K key, V value)
TreeMap
TreeMap
是以红黑色为底层结构的Map借口实现类,功能和其他的Map实现了基本一致。该类不是线程安全的,
要在多线程中使用它需要使用外部同步。它不能存放为null的键,但可以存放为null的值
This implementation provides guaranteed log(n) time cost for the
{@code containsKey}, {@code get}, {@code put} and {@code remove}
operations
containsKey
, get
,put
,remove
等方法的时间复杂度是O(log(n))。该类存储的元素是有序的,
一般通过自然顺序进行排序,如果在构造函数中提供了自定义的Comparator,则按照自定义的Comparator进行排序。
成员变量
/** |
构造函数
/** |
常用方法
public int size()
public boolean containsKey(Object key)
public boolean containsValue(Object value)
public V get(Object key)
public Comparator<? super K> comparator()
获取自定义的Comparatorpublic K firstKey()
public K lastKey()
public void putAll(Map<? extends K, ? extends V> map)
public V put(K key, V value)
public V remove(Object key)
public void clear()
public Map.Entry<K,V> firstEntry()
获取第一个键值对的Entry对象public Map.Entry<K,V> lastEntry()
获取最后一个键值对的Entry对象public Map.Entry<K,V> pollFirstEntry()
移除并返回Map中最前面的一个元素public Map.Entry<K,V> pollLastEntry()
移除并返回Map中最后面的一个元素public Map.Entry<K,V> lowerEntry(K key)
返回key小于指定key的键值对,返回的键值对的键同时也是Map中的最大的键public K lowerKey(K key)
返回key小于指定key的键,返回的键同时也是Map中的最大的键public Map.Entry<K,V> floorEntry(K key)
返回key小于或等于指定key的键值对,返回的键值对的键同时也是Map中的最大的键public K floorKey(K key)
返回key小于等于指定key的键,返回的键同时也是Map中的最大的键public Map.Entry<K,V> ceilingEntry(K key)
返回key大于或等于指定key的键值对,返回的键值对的键同时也是Map中的最小的键public K ceilingKey(K key)
返回key大于等于指定key的键,返回的键同时也是Map中的最小的键public Map.Entry<K,V> higherEntry(K key)
返回key大于指定key的键值对,返回的键值对的键同时也是Map中的最小的键public K higherKey(K key)
返回key大于指定key的键,返回的键同时也是Map中的最小的键public Set
keySet() public NavigableSet
navigableKeySet()
返回Map中的所有key,key按照原本的顺序排列,封装成NavigableSet类型后返回public NavigableSet
descendingKeySet()
返回Map中的所有key,key按照降序排列,封装成NavigableSet类型后返回public Collection
values()
返回Map中的所有值,值按照升序排列,封装成Collection类型后返回public Set<Map.Entry<K,V>> entrySet()
返回Map中的所有键值对,按照升序排列,封装成Set类型后返回public NavigableMap<K, V> descendingMap()
返回Map中所有键值对,按照倒叙排列,封装成NavigableMap类型后返回public boolean replace(K key, V oldValue, V newValue)
当指定的key和oldValue和Map中的key-value都对应时替换oldValue为newValuepublic V replace(K key, V value)
替换指定key的value
ConcurrentHashMap
这是线程安全版的HashMap
,主要在并发环境下使用,它是线程安全的。它的实现比HashMap
要复杂很多,
由于使用了CAS来实现同步,在并发环境它的性能要比Hashtable高很多,因此在并发环境下建议使用ConcurrentHashMap
,
它不允许存放null键值对。
成员变量
/* ---------------- Constants -------------- */ |
构造函数
|
常用方法
常用方法和Hashtable一样
IdentityHashMap
IdentityHashMap
是一种特殊的Map,它的特别之处在于,在判断两个key是否相等的时候,
只有当key1 == key2的时候(使用==
操作符)才认为这两个key是相等的,因此它的判断方式是判断引用相等,而不是对象相等。
该类的详细用途可以查看文档
Map总结
ConcurrentHashMap
和Hashtable
是线程安全的,其它的不是ConcurrentHashMap
和Hashtable
不允许存放null键值对,HashMap
可以,TreeMap
可以不可存放null键,可以存放null值TreeMap
是有序(按照自然顺序或者用户自定义排序规则排序)的,其他的一般是无序的(如返回的Iterator
不保证迭代元素顺序一致)HashMap
和ConcurrentHashMap
在JDK1.8开始,在Hash冲突严重的时候会将链表结构转换成红黑树结构,因此它们的查找操作的最坏时间复杂度为O(log(n))
HashSet
HashSet
是Set
接口的一种Hash实现,和List
接口不同,Set
接口不包含重复的元素。HashSet
不保证迭代顺序,它不是线程安全的,允许添加null元素
成员变量
private transient HashMap<E,Object> map; |
构造方法
/** |
常用方法
public int size()
public boolean isEmpty()
public boolean contains(Object o)
public boolean add(E e)
添加一个元素到Set,如果该元素已经存在,则不添加public boolean remove(Object o)
public void clear()
TreeSet
NavigableSet
的一种实现,它的实现基于TreeMap
,其实就是没有值的TreeMap
,
它的元素是有序(按照自然顺序或者用户自定义的排序规则排序)的。
This implementation provides guaranteed log(n) time cost for the basic
operations ({@code add}, {@code remove} and {@code contains}).
add
,remove
,contains
等基本操作的时间复杂度均为log(n),它不是线程安全的。
成员变量
/** |
构造函数
/** |
常用方法
public Iterator
iterator() public Iterator
descendingIterator() public NavigableSet
descendingSet() public int size()
public boolean isEmpty()
public boolean contains(Object o)
public boolean add(E e)
public boolean remove(Object o)
public void clear()
LinkedHashSet
LinkedHashSet
的迭代是有序的(通过它的iterator方法得到的迭代器迭代元素的顺序和插入元素的时间顺序一致),
它继承了HashMap
类并实现了Set
接口,一般用来复制一个Set对象,并且要保持复制后的元素顺序和原来的Set对象一致,比如:void foo(Set s) {
Set copy = new LinkedHashSet(s);
...
}
成员变量
没有自己的成员变量
构造器
/**
* Constructs a new, empty linked hash set with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity of the linked hash set
* @param loadFactor the load factor of the linked hash set
* @throws IllegalArgumentException if the initial capacity is less
* than zero, or if the load factor is nonpositive
*/
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);
}
/**
* Constructs a new, empty linked hash set with the specified initial
* capacity and the default load factor (0.75).
*
* @param initialCapacity the initial capacity of the LinkedHashSet
* @throws IllegalArgumentException if the initial capacity is less
* than zero
*/
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);
}
/**
* Constructs a new, empty linked hash set with the default initial
* capacity (16) and load factor (0.75).
*/
public LinkedHashSet() {
super(16, .75f, true);
}
/**
* Constructs a new linked hash set with the same elements as the
* specified collection. The linked hash set is created with an initial
* capacity sufficient to hold the elements in the specified collection
* and the default load factor (0.75).
*
* @param c the collection whose elements are to be placed into
* this set
* @throws NullPointerException if the specified collection is null
*/
public LinkedHashSet(Collection<? extends E> c) {
super(Math.max(2*c.size(), 11), .75f, true);
addAll(c);
}
常用方法
继承了HashSet的方法
Set总结
Set
不包含重复元素HashSet
是无序的(迭代元素的时候不会按照插入元素的顺序进行迭代),TreeSet
和LinkedHashSet
是有序的