Java的集合Collection Map

作者:课课家教育更新于： 2016-02-18 16:03:27

　　java集合由Collection Map两个接口派生而出,Collection代表序列式容器,Map代表关联式容器.

　　Collection

　　Collection作为List Queue Set等序列式容器的父接口, 提供了一些公共基础方法:

　　update相关方法:

　　boolean add(E e)

　　boolean addAll(Collection c)

　　void clear()

　　boolean remove(Object o)

　　boolean removeAll(Collection c)

　　boolean retainAll(Collection c)(取交集)

　　select相关方法

　　boolean contains(Object o)

　　boolean containsAll(Collection c)

　　Iterator iterator()

　　Object[] toArray()

　　T[] toArray(T[] a)

　　boolean iSEMpty()

　　int size()

　　详细可参考JDk文档

　　Iterator

　　iterator()方法返回一个迭代器Iterator.与其他容器主要用于存储数据不同,Iterator主要用于遍历容器.

　　Iterator隐藏了各类容器的底层实现细节,向应用程序提供了一个遍历容器的统一接口:

　　方法释义

　　boolean hasNext()Returns true if the iteration has more elements.

　　E next()Returns the next element in the iteration.

　　void remove()Removes from the underlying collection the last element returned by this iterator (optional operation).

　　注意: 当遍历Collection时不要使用Collection自带的remove方法删除数据,确实需要删除时,需要使用Iterator提供的remove.

　　/**

　　* @author jifang

　　* @since 16/1/25 上午9:59.

　　public class RemoveClient {

　　Collection collection = new ArrayList<>();

　　@Before

　　public void setUp() {

　　Random random = new Random();

　　for (int i = 0; i < 10; ++i) {

　　collection.add(random.nextInt(i + 1));

　　@Test

　　public void client() {

　　System.out.print("before:");

　　for (Iterator iterator = collection.iterator(); iterator.hasNext(); ) {

　　Integer integer = iterator.next();

　　System.out.printf(" %d", integer);

　　if (integer == 0) {

　　//collection.remove(i);

　　iterator.remove();

　　System.out.printf("%n after:");

　　for (Integer integer : collection) {

　　System.out.printf(" %d", integer);

　　Java 1.5提供foreach循环使得代码更加简洁,但实际foreach迭代容器元素底层也是用的Iterator,这一点可以在调试时看得很清楚.

　　List

　　List代表有序/可重复集合,因此List在Collection的基础上添加了根据索引来操作元素的方法:

　　方法描述

　　void add(int index, E element)Inserts the specified element at the specified position in this list (optional operation).

　　E get(int index)Returns the element at the specified position in this list.

　　int indexOf(Object o)Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.

　　int lastIndexOf(Object o)Returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element.

　　E remove(int index)Removes the element at the specified position in this list (optional operation).

　　E set(int index, E element)Replaces the element at the specified position in this list with the specified element (optional operation).

　　List subList(int fromIndex, int toIndex)Returns a view of the portion of this list between the specified fromIndex, inclusive, and toIndex, exclusive.

　　List判断两个元素是否相等是通过equals()方法.

　　public int indexOf(Object o) {

　　if (o == null) {

　　for (int i = 0; i < size; i++)

　　if (elementData[i]==null)

　　return i;

　　} else {

　　for (int i = 0; i < size; i++)

　　if (o.equals(elementData[i]))

　　return i;

　　}

　　return -1;

　　ListIterator

　　List增加了返回ListIterator的方法:

　　方法描述

　　ListIterator listIterator()Returns a list iterator over the elements in this list (in proper sequence).

　　ListIterator listIterator(int index)Returns a list iterator over the elements in this list (in proper sequence), starting at the specified position in the list.

　　ListIterator继承自Iterator,专门用于操作List, 在Iterator的基础上增加了如下方法:

　　方法描述

　　void add(E e)Inserts the specified element into the list (optional operation).

　　void set(E e)Replaces the last element returned by next() or previous() with the specified element (optional operation).

　　boolean hasPrevious()Returns true if this list iterator has more elements when traversing the list in the reverse direction.

　　E previous()Returns the previous element in the list and moves the cursor position backwards.

　　int previousIndex()Returns the index of the element that would be returned by a subsequent call to previous().

　　int nextIndex()Returns the index of the element that would be returned by a subsequent call to next().

　　与Iterator相比增加了前向迭代 获取迭代元素index 以及add set的功能.

　　ArrayList

　　ArrayList是List基于数组的实现,它封装了一个动态自增长/允许再分配的Object[]数组:

　　/**

　　* The array buffer into which the elements of the ArrayList are stored.

　　* The capacity of the ArrayList is the length of this array buffer. Any

　　* empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to

　　* DEFAULT_CAPACITY when the first element is added.

　　private transient Object[] elementData;

　　ArrayList可以使用initialCapacity参数来设置该数组的初始长度ArrayList(int initialCapacity),或者使用默认长度DEFAULT_CAPACITY = 10; 当添加元素超过elementData数组容量时,ArrayList会重新分配数组, 以容纳新元素:

　　* appends the specified element to the end of this list.

　　* @param e element to be appended to this list

　　* @return true (as specified by {@link Collection#add})

　　public boolean add(E e) {

　　ensureCapacityInternal(size + 1); // Increments modCount!!

　　elementData[size++] = e;

　　return true;

　　private void ensureCapacityInternal(int minCapacity) {

　　if (elementData == EMPTY_ELEMENTDATA) {

　　minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);

　　ensureExplicitCapacity(minCapacity);

　　private void ensureExplicitCapacity(int minCapacity) {

　　modCount++;

　　// overflow-conscious code

　　if (minCapacity - elementData.length > 0)

　　grow(minCapacity);

　　* Increases the capacity to ensure that it can hold at least the

　　* number of elements specified by the minimum capacity argument.

　　* @param minCapacity the desired minimum capacity

　　private void grow(int minCapacity) {

　　// overflow-conscious code

　　int oldCapacity = elementData.length;

　　int newCapacity = oldCapacity + (oldCapacity >> 1);

　　if (newCapacity - minCapacity < 0)

　　newCapacity = minCapacity;

　　if (newCapacity - MAX_ARRAY_SIZE > 0)

　　newCapacity = hugeCapacity(minCapacity);

　　// minCapacity is usually close to size, so this is a win:

　　elementData = Arrays.copyOf(elementData, newCapacity);

　　如果在创建时就知道ArrayList的容量,最好同时指定initialCapacity的大小,以避免重新分配数组,耗费性能.

　　ArrayList还提供如下方法来调整initialCapacity大小:

　　方法描述

　　void ensureCapacity(int minCapacity)Increases the capacity of this ArrayList instance, if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity argument.

　　void trimToSize()Trims the capacity of this ArrayList instance to be the list’s current size.

　　工具类Arrays还提供了一个static方法List asList(T... a), 该方法可以把数组或N个对象转换成一个List集合, 这个List集合并不是普通的ArrayList,而是Arrays内部实现的一个Arrays.ArrayList(一个固定长度的List,不可对该集合做add/remove操作).

　　关于ArrayList实现原理还可以参考ArrayList源码解析

　　LinkedList

　　LinkedList是基于双向链表实现的List,虽然可以根据索引来访问集合中的元素,但性能不高(平均时间复杂度为O(N)),但其插入/删除操作非常迅速(尤其是在头尾,平均时间复杂度为O(1));除此之外,LinkedList还实现了Deque接口,因此还可以当成[双端]队列/栈来使用.

　　关于LinkedList的实现原理还可以参考 [1.LinkedList源码解析, 2. 双向循环链表的设计与实现]

　　* @author jifang

　　* @since 16/1/23 下午9:07.

　　public class ListClient {

　　private Random random = new Random();

　　@Test

　　public void client() {

　　List list = new LinkedList<>();

　　for (int i = 0; i < 10; ++i) {

　　list.add(random.nextInt(i + 1));

　　for (ListIterator i = list.listIterator(); i.hasNext(); ) {

　　if (i.next() == 0) {

　　i.set(188);

　　i.add(-1);

　　System.out.println(list);

　　Queue

　　Queue用于模拟队列,队列是一种先进先出/FIFO容器,新元素插到队尾(offer), 访问操作会返回队首元素(poll). 通常, 队列不允许随机访问队列中的元素:

　　方法描述

　　boolean add(E e)Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available.

　　boolean offer(E e)Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions.

　　E element()Retrieves, but does not remove, the head of this queue.

　　E peek()Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.

　　E poll()Retrieves and removes the head of this queue, or returns null if this queue is empty.

　　E remove()Retrieves and removes the head of this queue.

　　Queue有一个PriorityQueue实现类,另外Queue还有一个Deque子接口,代表可以从两端存取数据的队列(因此Deque可以当成Stack使用),Java为Deque提供了ArrayDeque和LinkedList两个实现类.

　　PriorityQueue

　　PriorityQueue并不是按照插入队列顺序进行排序,而是按照队列元素的大小(权重)进行排序, 因此element/peek/poll/remove返回的并不是最早进入队列的元素,而是队列中[权重]最小的元素:

　　* @author jifang

　　* @since 16/1/28 下午6:20.

　　public class QueueClient {

　　@Test

　　public void clientPriorityQueue() {

　　Random random = new Random();

　　Queue queue = new PriorityQueue<>();

　　for (int i = 0; i < 10; ++i) {

　　queue.add(random.nextInt(100));

　　}

　　// 无序

　　System.out.print("iterator:");

　　for (Integer i : queue) {

　　System.out.printf(" %d", i);

　　}

　　System.out.println();

　　// 有序

　　System.out.print("pool:");

　　while (!queue.isEmpty()) {

　　System.out.printf(" %d", queue.poll());

　　}

　　System.out.println();

　　可以看到遍历PriorityQueue得到的并不是有序序列, 因为PriorityQueue内部并不是一个按照顺序排序的数组, 而是一个二叉堆(详细可以参考[1. PriorityQueue源码解析, 2. 堆与堆排序 ]).

　　由于需要排序,PriorityQueue不允许插入null;

　　PriorityQueue的元素有两种排序方式

　　自然排序: 采用自然排序的元素必须实现了Comparable接口.

　　定制排序: 创建PriorityQueue时,传入一个Comparator实例,该对象负责对元素进行排序,采用定制排序时不要求队列元素实现Comparable接口.

　　关于两种排序的详细内容可以参考下面关于TreeMap的讨论.

　　Deque-ArrayDeque

　　Java为Deque提供了两个实现类ArrayDeque(基于数组)与LinkedList(基于链表);由于ArrayDeque底层基于数组E[] elements实现,因此创建时可以指定一个numElements参数设置elements数组初始长度,如果不指定numElements参数,默认数组长度为16(关于ArrayDeque的实现原理可参考ArrayDeque源码解析).

　　@Test

　　public void asStack() {

　　Deque stack = new ArrayDeque<>();

　　for (int i = 0; i < 10; ++i) {

　　stack.push(i);

　　}

　　while (!stack.isEmpty()) {

　　System.out.println(stack.pop());

　　}

　　此外, LinkedList也实现了Deque接口,因此也可以作为Queue/Deque的实现类.

　　Map

　　Map用于保存具有映射关系的key-value数据,key和value之间存在单向一对一关系,通过指定的key,总能找到唯一确定的value.

　　update相关

　　V put(K key, V value)

　　void putAll(Map m)

　　V remove(Object key)

　　void clear()

　　select相关

　　V get(Object key)

　　Set keySet()

　　Collection values()

　　Set> entrySet()

　　boolean containsKey(Object key)

　　boolean containsValue(Object value)

　　boolean isEmpty()

　　int size()

　　Map内部定义一个Map.Entry接口,封装key-value对,Entry提供如下方法:

　　方法描述

　　K getKey()Returns the key corresponding to this entry.

　　V getValue()Returns the value corresponding to this entry.

　　V setValue(V value)Replaces the value corresponding to this entry with the specified value (optional operation).

　　HashMap

　　HashMap是基于hash算法的Map实现(用它代替Hashtable),针对key-value的插入/检索,这种形式具有最稳定的性能(O(1)),还可通过构造器对这一性能进行调整.

　　为了成功在HashMap中存取数据,key对象必须实现hashCode()与equals()方法,HashMap先通过key的hashCode()定位到元素所在桶,如果两个元素在同一个桶,再用equals()进行判断是否相等.如果两个对象的hashCode()相同,但equals()不同, 则将两个对象放在同一个桶的不同链表位置(这样会导致hash效率下降).如果两个对象通过equals()返回true, 但这hashCode()不同,则非常有可能导致HashMap将这两个对象分配在不同桶中,从而使这两个对象都添加成功,这就与Map规则冲突了.(关于HashMap详细原理可以参考: [1. 哈希表的设计与实现, 2.HashMap源码解析]).

　　建议: 如果两个对象通过equals()方法比较返回true, 则两个对象的hashCode()值也相同.

　　hashCode()重写规则:

　　运行过程中, 同一个对象多次调用hashCode()应具有相同返回值;

　　当两个对象通过equals()比较返回true时, hashCode()应具有相同返回值;

　　对象中用作equals()比较标准的实例变量, 都应该用于计算hashCode().

　　hashCode()重写方法:

　　将每个有意义的实例变量都计算出一个int的hashcode值.

　　类型计算方式

　　booleanhashCode = (true ? 1 : 0);

　　floathashCode = Float.floatToIntBits(f);

　　doublelong value = Double.doubleToLongBits(f);

　　hashCode = (int)(value^(value>>>32));

　　int/short/bytehashCode = (int)i;

　　longhashCode = (int)(l^(l>>>32));

　　引用类型hashCode = object.hashCode();

　　用上面计算出来的多个hashcode组合计算成一个最终的hashcode,为了避免直接相加产生偶然相等,可以为各个hashcode乘以任意一个质数再相加:

　　String实现

　　public int hashCode() {

　　int h = hash;

　　if (h == 0 && value.length > 0) {

　　char val[] = value;

　　for (int i = 0; i < value.length; i++) {

　　h = 31 * h + val[i];

　　}

　　hash = h;

　　}

　　return h;

　　}

　　String的hashCode()方法做了一些优化, 叫闪存散列码, 详见数据结构与算法分析 : Java语言描述

　　自定义Bean

　　/**

　　* @author jifang

　　* @since 16/1/13下午7:50.

　　*/

　　public class Bean implements Serializable {

　　private static final long serialVersionUID = 2975296536292876992L;

　　private boolean isUsed;

　　private double rate;

　　private String name;

　　@Override

　　public int hashCode() {

　　long rateHash = Double.doubleToLongBits(rate);

　　int isUsedHash = isUsed ? 1 : 0;

　　int nameHash = name.hashCode();

　　return nameHash * 11 + (int) (rateHash ^ (rateHash >>> 32)) * 13 + isUsedHash;

　　HashMap的主要实现逻辑:

　　* Associates the specified value with the specified key in this map.

　　* If the map previously contained a mapping for the key, the old

　　* value is replaced.

　　*

　　* @param key key with which the specified value is to be associated

　　* @param value value to be associated with the specified key

　　* @return the previous value associated with key, or

　　* null if there was no mapping for key.

　　* (A null return can also indicate that the map

　　* previously associated null with key.)

　　public V put(K key, V value) {

　　if (table == EMPTY_TABLE) {

　　inflateTable(threshold);

　　if (key == null)

　　return putForNullKey(value);

　　int hash = hash(key);

　　int i = indexFor(hash, table.length);

　　for (Entry e = table[i]; e != null; e = e.next) {

　　Object k;

　　if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {

　　V oldValue = e.value;

　　e.value = value;

　　e.recordAccess(this);

　　return oldValue;

　　}

　　modCount++;

　　addEntry(hash, key, value, i);

　　return null;

　　* Adds a new entry with the specified key, value and hash code to

　　* the specified bucket. It is the responsibility of this

　　* method to resize the table if appropriate.

　　* Subclass overrides this to alter the behavior of put method.

　　void addEntry(int hash, K key, V value, int bucketIndex) {

　　if ((size >= threshold) && (null != table[bucketIndex])) {

　　resize(2 * table.length);

　　hash = (null != key) ? hash(key) : 0;

　　bucketIndex = indexFor(hash, table.length);

　　createEntry(hash, key, value, bucketIndex);

　　* Like addEntry except that this version is used when creating entries

　　* as part of Map construction or "pseudo-construction" (cloning,

　　* deserialization). This version needn‘t worry about resizing the table.

　　* Subclass overrides this to alter the behavior of HashMap(Map),

　　* clone, and readObject.

　　void createEntry(int hash, K key, V value, int bucketIndex) {

　　Entry e = table[bucketIndex];

　　table[bucketIndex] = new Entry<>(hash, key, value, e);

　　size++;

　　注意

　　当向Map类容器(如HashMap TreeMap 或后面的HashSet TreeSet)中添加可变对象时,必须十分小心,如果修改Map中的key,有可能导致该key与集合中的其他key相等,从而导致无法准确访问该key-value.因此尽量不要使用可变对象作为Map的key,或不要修改作为key的对象(Set的value于此类同)

　　Map还支持containsValue()方法来判断一个value是否存在于Map中, 但该方法会遍历所有的桶查找这个值, 因此性能较差, 不推荐使用

　　public boolean containsValue(Object value) {

　　if (value == null)

　　return containsNullValue();

　　Entry[] tab = table;

　　for (int i = 0; i < tab.length ; i++)

　　for (Entry e = tab[i] ; e != null ; e = e.next)

　　if (value.equals(e.value))

　　return true;

　　return false;

　　* Special-case code for containsValue with null argument

　　private boolean containsNullValue() {

　　Entry[] tab = table;

　　for (int i = 0; i < tab.length ; i++)

　　for (Entry e = tab[i] ; e != null ; e = e.next)

　　if (e.value == null)

　　return true;

　　return false;

　　LinkedHashMap

　　LinkedHashMap使用双向链表来维护key-value插入顺序,因此性能略低于HashMap,但在需要顺序迭代Map的场景下会有非常好的效率.

　　LinkedHashMap提供的addEntry()方法与HashMap有所不同,当使用LinkedHashMap的put()时, 会从HashMap调回到LinkedHashMap的addEntry()方法,将新元素添加到链表尾:

　　* This override alters behavior of superclass put method. It causes newly

　　* allocated entry to get inserted at the end of the linked list and

　　* removes the eldest entry if appropriate.

　　void addEntry(int hash, K key, V value, int bucketIndex) {

　　super.addEntry(hash, key, value, bucketIndex);

　　// Remove eldest entry if instructed

　　Entry eldest = header.after;

　　if (removeEldestEntry(eldest)) {

　　removeEntryForKey(eldest.key);

　　* This override differs from addEntry in that it doesn‘t resize the

　　* table or remove the eldest entry.

　　void createEntry(int hash, K key, V value, int bucketIndex) {

　　HashMap.Entry old = table[bucketIndex];

　　Entry e = new Entry<>(hash, key, value, old);

　　table[bucketIndex] = e;

　　e.addBefore(header);

　　size++;

　　使用LinkedHashMap统计word出现次数

　　* @author jifang

　　* @since 16/1/28 上午10:33.

　　public class MapClient {

　　private Random random = new Random();

　　@Test

　　public void clientLinkedHashMap() {

　　Map map = new LinkedHashMap<>();

　　System.out.print("insert key:");

　　for (int i = 0; i < 20; ++i) {

　　String key = String.valueOf(random.nextInt(10));

　　System.out.printf(" %s", key);

　　if (map.get(key) == null) {

　　map.put(key, 1);

　　} else {

　　map.put(key, map.get(key) + 1);

　　System.out.printf("%n iterator:");

　　for (Map.Entry entry : map.entrySet()) {

　　System.out.printf("