java集合與數(shù)據(jù)結(jié)構(gòu)

這里嘗試將java集合中的概念與數(shù)據(jù)結(jié)構(gòu)中的概念相結(jié)合傻丝，以便更好的記憶。

集合框架體系圖

概述：

Collection接口:集合類的基本接口诉儒，List桑滩、Set和Queue接口都繼承自它。
Map接口：映射表的基礎(chǔ)接口
Iterator接口：迭代器，可以通過迭代器遍歷集合中的數(shù)據(jù)

集合框架接口圖.png

此外运准，由上圖可知幌氮，還有一個(gè)Iterable接口，它是Collection的父接口胁澳。
實(shí)現(xiàn)Iterable接口的類的對象可以成為 for-each 循環(huán)的目標(biāo)该互，所以可以得出結(jié)論：對于標(biāo)準(zhǔn)類庫中的任何集合都可以使用 “ for-each ”循環(huán)。
例如：

List<Object> list = new ArrayList();
for (Object obj: list){}

此外韭畸，數(shù)組也可以使用 for-each 循環(huán)遍歷宇智，如下：

Object[] list = new Object[10];
for (Object obj: list){}

下面開始詳細(xì)介紹常用的幾個(gè)集合：

List集合

java.util.List 接口繼承自 Collection 接口，是單列集合的一個(gè)重要分支胰丁，習(xí)慣性地會(huì)將實(shí)現(xiàn)了 List 接口的對象稱為List集合随橘。在List集合中允許出現(xiàn)重復(fù)的元素，所有的元素是以一種線性方式進(jìn)行存儲(chǔ)的锦庸，在程序中可以通過索引來訪問集合中的指定元素机蔗。另外，List集合還有一個(gè)特點(diǎn)就是元素有序甘萧，即元素的存入順序和取出順序一致萝嘁。
這里容易想到List集合這個(gè)概念和數(shù)據(jù)結(jié)構(gòu)中的線性表是很相似的。（List接口中的方法大多為抽象方法扬卷，這與線性表是邏輯結(jié)構(gòu)對應(yīng)牙言。可以這樣認(rèn)為怪得，List是帶索引的線性表）
java List一共三個(gè)實(shí)現(xiàn)類：分別是ArrayList 催什、Vector 和 LinkedList荞胡。

ArrayList（對應(yīng)于線性表的物理結(jié)構(gòu)——數(shù)組）

ArrayList 是實(shí)現(xiàn)了List接口的可擴(kuò)容數(shù)組（動(dòng)態(tài)數(shù)組）嫉你，它的內(nèi)部是基于數(shù)組實(shí)現(xiàn)的罕邀。它的具體定義如下：

public class ArrayList<E> extends AbstractList<E> implements List<E>,
RandomAccess, Cloneable, java.io.Serializable {...}

總結(jié)：

ArrayList 是最常用的 List 實(shí)現(xiàn)類搀矫，底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組抑片，查詢快亏推，增刪慢期犬。
ArrayList 不是線程安全的容器颜懊，如果多個(gè)線程中至少兩個(gè)線程修改了 ArrayList 的結(jié)構(gòu)的話就會(huì)導(dǎo)致線程安全問題财岔，作為替代條件可以使用線程安全的 List ，應(yīng)使用
Collections.synchronizedList河爹。

List list = Collections.synchronizedList(new ArrayList(...))

LinkedList（對應(yīng)線性表中的物理結(jié)構(gòu)——雙向鏈表）

LinkedList 是一個(gè)雙向鏈表匠璧，允許存儲(chǔ)任何元素（包括null）。它主要特性如下：

LinkedList 底層數(shù)據(jù)結(jié)構(gòu)是鏈表咸这，查詢慢夷恍，增刪快。
LinkedList 也不是線程安全的,若多個(gè)線程并發(fā)訪問鏈表,并且至少其中的一個(gè)線程修改了鏈表的結(jié)構(gòu),那么這個(gè)鏈表必須進(jìn)行外部加鎖媳维∧鹧或者使用

List list = Collections.synchronizedList(new LinkedList(...))

Vector

Vector 同 ArrayList 一樣遏暴，都是基于數(shù)組實(shí)現(xiàn)的，只不過 Vector 是一個(gè)線程安全的容器指黎，它對內(nèi)部的每個(gè)方法都簡單粗暴的上鎖朋凉，避免了多線程引起的安全性問題，但是通常這種同步方式需要的開銷比較大醋安。因此杂彭，訪問元素的效率要遠(yuǎn)遠(yuǎn)低于 ArrayList 。
還有吓揪，ArrayList 擴(kuò)容后數(shù)組長度會(huì)增加50%亲怠，而 Vector 擴(kuò)容長度后數(shù)組會(huì)增加一倍。

Set集合

Set 注重獨(dú)一無二的性質(zhì),該體系集合用于存儲(chǔ)無序(存入和取出的順序不一定相同)元素柠辞，值不能重復(fù)团秽。對象的相等性本質(zhì)是對象由 hashCode 值（java 是依據(jù)對象的內(nèi)存地址計(jì)算出的此序號(hào)）判斷的，如果想要讓兩個(gè)不同的對象視為相等的钾腺，就必須覆蓋 Object 的 hashCode 方法和 equals 方法徙垫。

HashSet（對應(yīng)的數(shù)據(jù)結(jié)構(gòu)為Hash表）

哈希表邊存放的是哈希值。HashSet 存儲(chǔ)元素的順序并不是按照存入時(shí)的順序（和 List 顯然不同）而是按照哈希值來存的所以取數(shù)據(jù)也是按照哈希值取得放棒。元素的哈希值是通過元素的 hashcode 方法來獲取的, HashSet 首先判斷兩個(gè)元素的哈希值姻报，如果哈希值一樣，接著會(huì)比較 equals 方法如果 equls 結(jié)果為 true 间螟，HashSet 就視為同一個(gè)元素吴旋。如果equals 為 false 就不是同一個(gè)元素。

哈希值相同 equals 為 false 的元素（即同義詞）是如何存儲(chǔ)呢厢破，就是在同樣的哈希值下順延（可以認(rèn)為哈希值相同的元素放在一個(gè)哈希桶中）荣瑟。也就是哈希值一樣的存一列。如圖 1 表示 hashCode 值不相同的情況摩泪；圖 2 表示 hashCode 值相同笆焰，但 equals 不相同的情況。

圖1和圖2.png

TreeSet（對應(yīng)的數(shù)據(jù)結(jié)構(gòu)為二叉樹）

TreeSet()是使用二叉樹（紅黑樹）的原理對新 add() 的對象按照指定的順序排序（升序见坑、降序）嚷掠，每增加一個(gè)對象都會(huì)進(jìn)行排序，將對象插入的二叉樹指定的位置荞驴。
Integer 和 String 對象都可以進(jìn)行默認(rèn)的 TreeSet 排序不皆，而自定義類的對象是不可以的，自己定義的類必須實(shí)現(xiàn)Comparable 接口熊楼，并且覆寫相應(yīng)的 compareTo()函數(shù)霹娄，才可以正常使用。
注意這個(gè)實(shí)現(xiàn)不是線程安全的。如果多線程并發(fā)訪問 TreeSet 犬耻，并且至少一個(gè)線程修改了 TreeSet 踩晶，必須進(jìn)行外部加鎖≌泶牛或者使用

SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...))

LinkedHashSet

對于 LinkedHashSet 而言合瓢，它繼承于 HashSet、又基于 LinkedHashMap 來實(shí)現(xiàn)的透典。LinkedHashSet 底層使用 LinkedHashMap 來保存所有元素晴楔，它繼承與 HashSet，其所有的方法操作上又與 HashSet 相同峭咒，因此LinkedHashSet 的實(shí)現(xiàn)上非常簡單税弃，只提供了四個(gè)構(gòu)造方法，并通過傳遞一個(gè)標(biāo)識(shí)參數(shù)凑队，調(diào)用父類的構(gòu)造器则果，底層構(gòu)造一個(gè) LinkedHashMap 來實(shí)現(xiàn)，在相關(guān)操作上與父類 HashSet 的操作相同漩氨，直接調(diào)用父類 HashSet 的方法即可西壮。

Map 接口

集是一個(gè)集合，它可以快速地查找現(xiàn)有的元素叫惊。但是款青，要查看一個(gè)元素，需要有要查找元素的精確副本霍狰。這不是一種非常通用的査找方式抡草。通常，我們知道某些鍵的信息蔗坯，并想要查找與之對應(yīng)的元素康震。映射（map) 數(shù)據(jù)結(jié)構(gòu)就是為此設(shè)計(jì)的。映射用來存放鍵 / 值對宾濒。如果提供了鍵腿短，就能夠查找到值。例如绘梦，有一張關(guān)于員工信息的記錄表橘忱，鍵為員工 ID，值為 Employee 對象谚咬。

Java 類庫為映射提供了兩個(gè)通用的實(shí)現(xiàn)：HashMap 和 TreeMap鹦付。這兩個(gè)類都實(shí)現(xiàn)了 Map 接口尚粘。

散列映射對鍵進(jìn)行散列择卦，樹映射用鍵的整體順序?qū)υ剡M(jìn)行排序，并將其組織成搜索樹。散列或比較函數(shù)只能作用于鍵秉继。與鍵關(guān)聯(lián)的值不能進(jìn)行散列或比較祈噪。

應(yīng)該選擇散列映射還是樹映射呢？與集一樣尚辑，散列稍微快一些辑鲤，如果不需要按照排列順序訪問鍵，就最好選擇散列杠茬。

HashMap

下列代碼將為存儲(chǔ)的員工信息建立一個(gè)散列映射：

Map<String, Employee>staff = new HashMap<>();
// HashMap implements Map
Employee harry = new Employee("Harry Hacker");
staff.put(”987-98-9996", harry);

每當(dāng)往映射中添加對象時(shí)月褥，必須同時(shí)提供一個(gè)鍵。在這里瓢喉，鍵是一個(gè)字符串宁赤，對應(yīng)的值是 Employee 對象。
要想檢索一個(gè)對象栓票，必須使用（因而决左，必須記住）一個(gè)鍵走贪。

String id = "987-98-9996"; 
e = staff,get(id);// gets harry

如果在映射中沒有與給定鍵對應(yīng)的信息佛猛， get 將返回 null。

總結(jié)：

HashMap 是一個(gè)利用哈希表原理來存儲(chǔ)元素的集合坠狡，并且允許空的 key-value 鍵值對继找。
HashMap 不是線程安全的,而 Hashtable 是線程安全的容器。
可以使用 Collections.synchronizedMap(new HashMap(...)) 來構(gòu)造一個(gè)線程安全的 HashMap逃沿。
在java7中其底層是由數(shù)組+鏈表組成的码荔，到了java8是由數(shù)組+鏈表+紅黑樹組成。

TreeMap

TreeMap 實(shí)現(xiàn) SortedMap 接口感挥，能夠把它保存的記錄根據(jù)鍵排序缩搅，默認(rèn)是按鍵值的升序排序，也可以指定排序的比較器（通過 Comparator 進(jìn)行定制排序）触幼，當(dāng)用 Iterator 遍歷 TreeMap 時(shí)硼瓣，得到的記錄是排過序的。

如果使用排序的映射置谦，建議使用 TreeMap堂鲤。

在使用 TreeMap 時(shí)，key 必須實(shí)現(xiàn)Comparable 接口或者在構(gòu)造 TreeMap 傳入自定義的 Comparator媒峡，否則會(huì)在運(yùn)行時(shí)拋出 java.lang.ClassCastException 類型的異常瘟栖。

LinkedHashMap（記錄插入順序）

LinkedHashMap 是 HashMap 的一個(gè)子類，保存了記錄的插入順序谅阿，在用 Iterator 遍歷LinkedHashMap 時(shí)半哟，先得到的記錄肯定是先插入的酬滤，也可以在構(gòu)造時(shí)帶參數(shù)，按照訪問次序排序寓涨。

Collections 類

java.utils.Collections 是集合工具類盯串，用來對集合進(jìn)行操作。部分方法如下：

public static <T> boolean addAll(Collection<T> c, T... elements) :往集合中添加一些元素戒良。
public static void shuffle(List<?> list) 打亂順序 :打亂集合順序体捏。
public static <T> void sort(List<T> list) :將集合中元素按照默認(rèn)規(guī)則排序。
public static <T> void sort(List<T> list糯崎，Comparator<? super T> ) :將集合中元素按照指定規(guī)則排序几缭。

代碼演示

public class CollectionsDemo { 
  public static void main(String[] args) {             
    ArrayList<Integer> list = new ArrayList<Integer>(); 
    //原來寫法 
    //list.add(12); 
    //list.add(14); 
    //list.add(15); 
    //list.add(1000); 
    //采用工具類完成往集合中添加元素     
    Collections.addAll(list, 5, 222, 1，2); 
    System.out.println(list); 
    //排序方法 
    Collections.sort(list); 
    System.out.println(list); 
  } 
}
結(jié)果： 
[5, 222, 1, 2] 
[1, 2, 5, 222]

代碼演示之后沃呢，發(fā)現(xiàn)我們的集合按照順序進(jìn)行了排列奏司，可是這樣的順序是采用默認(rèn)的順序，如果想要指定順序那該怎么辦呢樟插？

我們發(fā)現(xiàn)還有個(gè)方法沒有講韵洋， public static <T> void sort(List<T> list，Comparator<? super T> ) :將集合中元素按照指定規(guī)則排序黄锤。接下來講解一下指定規(guī)則的排列搪缨。

Comparator比較器

在JAVA中提供了兩種比較大小的方式，一種是比較死板的采用 java.lang.Comparable 接口去實(shí)現(xiàn)鸵熟，一種是靈活的當(dāng)我需要做排序的時(shí)候再去選擇的 java.util.Comparator 接口來完成副编。

那么我們采用的 public static <T> void sort(List<T> list) 這個(gè)方法完成的排序，實(shí)際上要求了被排序的類型需要實(shí)現(xiàn)Comparable接口完成比較的功能流强，在String類型上如下：

public final class String implements java.io.Serializable, Comparable<String>, CharSequence {

String類實(shí)現(xiàn)了這個(gè)接口痹届，并完成了比較規(guī)則的定義，但是這樣就把這種規(guī)則寫死了打月，那比如我想要字符串按照第一個(gè)字符降序排列队腐，那么這樣就要修改String的源代碼，這是不可能的了奏篙，那么這個(gè)時(shí)候我們可以使用 public static <T> void sort(List<T> list柴淘，Comparator<? super T> ) 方法靈活的完成，這個(gè)里面就涉及到了 Comparator 這個(gè)接口秘通，位于位于java.util包下为严，排序是comparator能實(shí)現(xiàn)的功能之一,該接口代表一個(gè)比較器，比較器具有可比性肺稀！顧名思義就是做排序的第股，通俗地講需要比較兩個(gè)對象誰排在前誰排在后，那么比較的方法就是：

public int compare(String o1, String o2) ：比較其兩個(gè)參數(shù)的順序话原。

兩個(gè)對象比較的結(jié)果有三種：大于夕吻，等于诲锹，小于。
如果要按照升序排序梭冠，則o1 小于o2，返回（負(fù)數(shù)）改备，相等返回0控漠，01大于02返回（正數(shù)）如果要按照降序排序則o1 小于o2，返回（正數(shù)）悬钳，相等返回0盐捷，01大于02返回（負(fù)數(shù)）

操作如下：

public class CollectionsDemo3 { 
  public static void main(String[] args) { 
    ArrayList<String> list = new ArrayList<String>();                 
    list.add("cba"); 
    list.add("aba"); 
    list.add("sba");
    list.add("nba"); 
    //排序方法 按照第一個(gè)單詞的降序 
    Collections.sort(list, new Comparator<String>() {
      @Override 
      public int compare(String o1, String o2) { 
          return o2.charAt(0) ‐ o1.charAt(0); 
      } 
  }); 
  System.out.println(list); 
  } 
}

結(jié)果如下：

[sba, nba, cba, aba]

集合實(shí)現(xiàn)類特征圖

集合實(shí)現(xiàn)類特征圖.png