[toc]

Java 類庫中的集合接口和迭代器

集合接口及迭代器

• 集合類的基本接口是：Collection

public interface Collection<E>{// 集合改變返回 true，否則返回 falseboolean add();boolean addAll();// 返回一個迭代器Iterator<E> iterator();int size();boolean isEmpty();// 集合中包含了和 obj 相等的對象，那么返回 trueboolean contains(Object obj);// 如果集合中包含 other 集合中的所有元素，那么返回 trueboolean containsAll(Collect<?> other);// 從這個集合中刪除等于 obj 的對象，如果有匹配的對象，返回 trueboolean remove(Object obj);// 從這個集合中刪除 other 中存在的元素，如果這個調用改變了集合，那么返回 trueboolean removeAll(Collect<?> other);void clear();// 從這個集合中刪除所有與 other 這個集合中的元素不同的元素，如果這個調用改變了集合，那么返回 trueboolean retainAll(Collection<?> other);Object[] toArray();<T> T[] toArray(T[] a);} 復制代碼

• 迭代器

public interface Iterator<E>{// 反復調用，可以逐個訪問集合中的每個元素(配合 hasNext() 這個方法)E next();boolean hasNext();// 刪除上次調用 next() 返回的元素,沒有調用 next() 方法，調用 remove() 則會報 IllegalStateException 異常void remove();} 復制代碼

• 迭代器的用法
  • 用法 1
  Collection<String> c = ....;Iterator<String> iterator = c.iterator();while(iterator.hasNext()){String element = iterator.next();iterator.remove();// todo something} 復制代碼
  • 用法 2：java SE 5.0 之后的寫法，for each 循環操作
  Collection<String> c = ....;for(String element : c){// todo something} 復制代碼

  “for each” 循環可以與任何實現了 Iterable 接口的對象一起工作

---

集合概覽圖

具體的集合實現

ArrayList

簡介

• 繼承于 AbstractList，實現了 List，是一個數組隊列，提供添加、刪除、修改、遍歷的功能
• 實現了 RandomAccess 接口，提供隨機訪問的功能
• 實現了 Cloneable 接口，提供了克隆功能
• 實現了 java.io.Serializable 接口，提供序列化功能

定義

java.lang.Object? java.util.AbstractCollection<E>? java.util.AbstractList<E>? java.util.ArrayList<E>public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable {} 復制代碼

特性

• 關于 ArrayList 是線程不安全的，那么 ArrayList 只能在單線程中使用，如果需要多線程使用的話，那么可以使用 Vector?；蛘呤且韵路绞?/li>

// 將其包裝成線程安全List list = Collections.synchronizedList(new ArrayList()); 復制代碼

• ArrayList 是一個動態數組隊列，它能高效的隨機訪問元素和順序遍歷，但對于插入和刪除效率會比較低，因為需要涉及到數組的移動。

擴容

• ArrayList 是一個動態的數組，那么一開始數組的大小是固定的（默認的話為 10），當向 ArrayList 中插入某個數組時，size 的值剛好為容量的大小，那么就會觸發擴容的操作。擴容的方式是重新創建一個新的數組，拷貝原來的數據到新的數組中，并將新的元素插入到新的數組中，舊的數組則會被垃圾回收。
• 默認容量：10
• 擴容規則

  • JDK 1.6 及之前

    int newCapacity = (oldCapacity * 3)/2 + 1; 復制代碼

  • JDK 1.7 及之后

    int newCapacity = oldCapacity + (oldCapacity >> 1); 復制代碼

  • JDK 1.8

    private void grow(int minCapacity) {// overflow-conscious codeint 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); }private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE; } 復制代碼

toArray()

• 2 種實現

Object[] toArray()<T> T[] toArray(T[] contents) 復制代碼

• 關于 “java.lang.ClassCastException”異常 toArray() 會拋出異常是因為 toArray() 返回的是 Object[] 數組，將 Object[] 轉換為其它類型(如如，將Object[]轉換為的Integer[])則會拋出“java.lang.ClassCastException”異常，因為Java不支持向下轉型。
• 關于轉換為數組的方式

// toArray(T[] contents)調用方式一 public static Integer[] vectorToArray1(ArrayList<Integer> v) {Integer[] newText = new Integer[v.size()];v.toArray(newText);return newText; } // toArray(T[] contents)調用方式二。最常用！ public static Integer[] vectorToArray2(ArrayList<Integer> v) {Integer[] newText = (Integer[])v.toArray(new Integer[0]);return newText; } // toArray(T[] contents)調用方式三 public static Integer[] vectorToArray3(ArrayList<Integer> v) {Integer[] newText = new Integer[v.size()];Integer[] newStrings = (Integer[])v.toArray(newText);return newStrings; } 復制代碼

注意點

• 多線程的話不使用 ArrayList，而是使用 Vector。

LinkedList

一種可以在任意位置進行高效插入及刪除的操作的有序序列

簡介

• 繼承了 AbstractSequentialList 的雙向鏈表，因此 LinkedList 是可以被當做堆棧、列表和雙端列表進行操作
• 實現 List 接口，進行隊列的操作
• 實現 Cloneable 接口，可以進行克隆操作
• 實現 Deque 接口，可以進行雙端隊列操作
• 實現 java.io.Serializable 接口，可以實現序列化
• 非同步的

定義

java.lang.Object? java.util.AbstractCollection<E>? java.util.AbstractList<E>? java.util.AbstractSequentialList<E>? java.util.LinkedList<E>public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable 復制代碼

特性

• 順序訪問的效率高，但是隨機訪問的效率比較低
• 刪除及添加的操作效率高
• 不同步（線程不安全）

將LinkedList當作 LIFO(后進先出)的堆棧示例

public static void useLinkedListAsLIFO() {System.out.println("\nuseLinkedListAsLIFO");// 新建一個LinkedListLinkedList stack = new LinkedList();// 將1,2,3,4添加到堆棧中stack.push("1");stack.push("2");stack.push("3");stack.push("4");// 打印“?！盨ystem.out.println("stack:"+stack);// 刪除“棧頂元素”System.out.println("stack.pop():"+stack.pop());// 取出“棧頂元素”System.out.println("stack.peek():"+stack.peek());// 打印“?！盨ystem.out.println("stack:"+stack);} 復制代碼

將LinkedList當作 FIFO(先進先出)的隊列

public static void useLinkedListAsFIFO() {System.out.println("\nuseLinkedListAsFIFO");// 新建一個LinkedListLinkedList queue = new LinkedList();// 將10,20,30,40添加到隊列。每次都是插入到末尾queue.add("10");queue.add("20");queue.add("30");queue.add("40");// 打印“隊列”System.out.println("queue:"+queue);// 刪除(隊列的第一個元素)System.out.println("queue.remove():"+queue.remove());// 讀取(隊列的第一個元素)System.out.println("queue.element():"+queue.element());// 打印“隊列”System.out.println("queue:"+queue);} 復制代碼

HashMap（JDK 1.7 及之前）

簡介

HashMap 它是基于 hash 表的 Map 接口實現，以 key-value 的形式存在的，HashMap 總是以 key-value 的形式存在的，系統會通過計算 key 的 hash 值來定位 key-value 的存儲位置的，我們可以快速的通過 key 來存取 value;

定義

public class HashMap<K,V>extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable 復制代碼

數據結構

關于 HashMap 的數據結構，底層的話還是數組的，只不過數組的每一項就是一個鏈表

構造函數的源碼

public HashMap(int initialCapacity, float loadFactor) {//初始容量不能<0if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: "+ initialCapacity);//初始容量不能 > 最大容量值，HashMap的最大容量值為2^30if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;//負載因子不能 < 0if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: "+ loadFactor);// 計算出大于 initialCapacity 的最小的 2 的 n 次方值。int capacity = 1;while (capacity < initialCapacity)capacity <<= 1;this.loadFactor = loadFactor;//設置HashMap的容量極限，當HashMap的容量達到該極限時就會進行擴容操作threshold = (int) (capacity * loadFactor);//初始化table數組table = new Entry[capacity];init();} 復制代碼

Entry 的源碼

static class Entry<K,V> implements Map.Entry<K,V> {final K key;V value;Entry<K,V> next;final int hash;/*** Creates new entry.*/Entry(int h, K k, V v, Entry<K,V> n) {value = v;next = n;key = k;hash = h;}.......} 復制代碼

Entry 是 HashMap 的內部類，其中包含了 key，value 和 下一個 Entry，以及 hash 值，正因為有這下才構成了數組的項為一個列表。

容量、加載因子、臨界值及哈希沖突

• 容量：table 數組的大小，一般默認為 16

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 復制代碼

• 加載因子：表示 table 數組的飽和程度
  • 加載因子越大,填滿的元素越多,空間利用率越高，但沖突的機會加大了。 反之;
  • 加載因子越小,填滿的元素越少,沖突的機會減小,但空間浪費多了。
• 臨界值：
  • 為了避免造成哈希沖突率，那么當 HashMap 的數組長度達到一個臨界值的時候就會觸發擴容，把所有的元素重新計算 hash 值，再放到擴容后的容器中，這是一個比較耗時的操作。
    • 臨界值由加載因子及當前的容量來決定，默認情況下 16*0.75=12 就會觸發擴容
  DEFAULT_INITIAL_CAPACITY*DEFAULT_LOAD_FACTOR 復制代碼

哈希沖突

在關鍵字的 hash 地址上已經有了記錄，那么這就是哈希沖突 復制代碼

• 解決沖突的方法
  • 開放定址法
  • 再哈希法
  • 建立一個公共溢出區
  • 鏈地址法（拉鏈法）

存儲實現：put(key,value)

public V put(K key, V value) {//當key為null，調用putForNullKey方法，保存null與table第一個位置中，這是HashMap允許為null的原因if (key == null)return putForNullKey(value);//計算key的hash值int hash = hash(key.hashCode()); ------(1)//計算key hash 值在 table 數組中的位置int i = indexFor(hash, table.length); ------(2)//從i出開始迭代 e,找到 key 保存的位置for (Entry<K, V> e = table[i]; e != null; e = e.next) {Object k;//判斷該條鏈上是否有hash值相同的(key相同)//若存在相同，則直接覆蓋value，返回舊valueif (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = e.value; //舊值 = 新值e.value = value;e.recordAccess(this);return oldValue; //返回舊值}}//修改次數增加1modCount++;//將 key、value 添加至i位置處addEntry(hash, key, value, i);return null;} 復制代碼

（1）處代碼實現：技術 hash 值

static int hash(int h) {h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);} 復制代碼

（2）處代碼實現：根據 hash 值計算出 key 在 table 數組中所對應的位置

static int indexFor(int h, int length) {return h & (length-1);} 復制代碼

（3）將節點插入表頭

void addEntry(int hash, K key, V value, int bucketIndex) {//獲取bucketIndex處的EntryEntry<K, V> e = table[bucketIndex];//將新創建的 Entry 放入 bucketIndex 索引處，并讓新的 Entry 指向原來的 Entry table[bucketIndex] = new Entry<K, V>(hash, key, value, e);//若HashMap中元素的個數超過極限了，則容量擴大兩倍if (size++ >= threshold)resize(2 * table.length);} 復制代碼

存儲步驟：

• step 1：判斷 key 是否為 null，若為 null，那么直接調用 putForNullKey 方法（table[0] 的數組項），否則進入 step2；
• step 2：計算 key 的 hash 值
• step 3：計算 key 的 hash 值在 table 數組中的位置 index
• step 4：在 table[index] 項中迭代，找出 key 的存儲位置，如果存在則替換就的值，并將舊的值返回，如果不存在對應的 key 的存儲位置，則進入 step5;
• step 5：將 key-value 放在 table[index] 的鏈表頭

擴容問題

隨著 HashMap 中的元素越來越多，發生 hash 沖突的概率越來越大，鏈表的長度越來越長，查找的效率就越來越低；這樣我們就必須在 HashMap 的某個臨界值進行擴容處理。擴容的方式：重新創建一個新的 table 數組，重新計算 key 的 hash 值，并放入新的 table 數組中，這樣的操作是比較耗時的，如果我們能夠預知 HashMap 中的大小時，我們可以指定 HashMap 中的元素個數。

• 讀取實現：get(key) 通過 key 的 hash 值找到在 table 數組中的索引處的 Entry，然后返回該 key 對應的 value 即可。

public V get(Object key) {// 若為null，調用getForNullKey方法返回相對應的valueif (key == null)return getForNullKey();// 根據該 key 的 hashCode 值計算它的 hash 碼 int hash = hash(key.hashCode());// 取出 table 數組中指定索引處的值for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {Object k;//若搜索的key與查找的key相同，則返回相對應的valueif (e.hash == hash && ((k = e.key) == key || key.equals(k)))return e.value;}return null;} 復制代碼

HashMap 非同步

HashMap 是線程不安全的，我們可以通過 Collections 的靜態方法 SynchronizedMap 來獲取線程安全的 HashMap

Map map = Collections.SynchronizedMap(new HashMap<>(); 復制代碼

LinkedHashMap

介紹

• LinkedHashMap 是 HashMap 的子類，因此 LinkedHashMap 擁有 HashMap 中的所有特性，但是 HashMap 的迭代是沒有順序的。LinkedHashMap 通過維護一個雙鏈表來保證迭代的順序（插入順序或者訪問順序），但是同時也增加了時間和空間的開銷。

數據結構

• HashMap(數組+鏈表)+雙鏈表

雙鏈表

``` /*** HashMap.Node subclass for normal LinkedHashMap entries.*/ static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {LinkedHashMapEntry<K,V> before, after;LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {super(hash, key, value, next);} }``` 復制代碼

重要變量

• head：雙鏈表頭部，保存最早插入的元素。
• tail：雙鏈表的尾部，保存最近插入的元素。
• accessOrder：訪問順序（true：訪問順序迭代；false：插入順序迭代）

重要函數

// Callbacks to allow LinkedHashMap post-actions// 訪問元素之后void afterNodeAccess(Node<K,V> p) { }// 插入節點之后void afterNodeInsertion(boolean evict) { }// 刪除節點之后void afterNodeRemoval(Node<K,V> p) { } 復制代碼

HashMap 和 HashTable 的區別

HashTable 和 HashMap 都實現了 Map 接口，他們的主要區別在于線程安全、速度。

• HashMap 可以接受 key 為 null，HashTable 不可以接受 key 為 null
• HashMap 是線程不安全（非 synchronize），HashTable 是線程安全的（synchronize)。synchronize 代表著每一次在一個線程中修改 HashTable 中的數據時，都需要獲得同步鎖，其他的線程要修改 HashTable 中的數據時，需要等待同步鎖被釋放才能進行。
• HashMap 的迭代器是 Iterator，HashTable 的迭代器是 enumerator。
• 在單線程的操作中，HashMap 的操作速度要比 HashTable 快，因為 HashTable 是 synchronize 的，所以會有同步鎖的獲取和釋放過程。

HashSet

• 介紹
• HashSet 是基于 HashMap 實現的，底層是使用 HashMap 來保存數組的

參考資料

數據結構之紅黑樹

LinkedHashSet

徹頭徹尾理解 LinkedHashMap

LinkedList 的詳細介紹

總結

以上是生活随笔為你收集整理的Java 基础 - 各项集合实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。