collection集合 位址_有容乃大--Java 集合（List/Set/Map）

1. Collection

Collection 是所有集合類的父接口，它定義了集合類最基本的操作方法：

Collection 接口

2. List

清單（List）實作了Collection，并擁有自己的特性：可以有重複元素，且是有序的，以元素添加順序為序。該類集合中有索引【角标】。

ArrayList 底層資料結構是數組存儲，查詢速度快，但是增删改慢，非線程安全，長度大約0.5倍增長（len += len>>1）

ArrayList 用法

ArrayList 實作原理

LinkedList 底層資料鍊結構是表結構，增删改速度快，但查詢慢，非線程安全，連結清單長度即為元素長度。

LinkedList 用法

Vector 底層實作與ArrayList一樣，但是線程同步的，相比于ArrayList，查詢增删都慢，長度1倍增長。

Stack 繼承于 Vector ，實作了一種後進先出（LIFO）的資料結構，棧。

3. Set

集（Set）也實作了 Collection 接口，它與清單的差別在于，不允許與重複元素，且元素是無序的（元素的有序性是指與插入順序一緻）。這類集合中沒有索引。

Set有兩種實作類，且底層都是用Map實作的：

HashSet：底層用HashMap實作，元素存在map的key中（key, new Object()），元素無序。

TreeSet： 底層用TreeMap實作，元素存在map的key中（key, new Object()），元素無序，但是元素是升序排列的。

HashSet

底層資料： 底層使用哈希表作為資料結構。

　　　　　　　　　　元素唯一性： 是通過元素的兩個方法： hashCode 和 equals 來完成的。

　　　　　　　　　　　　　　如果兩個元素的HashCode值相同，就會判斷equals是否為true。

　　　　　　　　　　　　　　如果兩個元素的HashCode值不同，就不會調用equals方法。

　　　　　　注意：對于判斷元素是否存在、删除等操作，都依賴于元素的hashCode、equals等方法。

　　　　　　哈希表：給定表M，存在函數f(key)，對任意給定的關鍵字值key，代入函數後若能得到包含該關鍵字的記錄在表中的位址，

　　　　　　　　則稱表M為哈希(Hash)表，函數f(key)為哈希(Hash) 函數。

　　　　　　（哈希值與記憶體位址值之間的關系：預設的哈希值是記憶體位址值計算的哈希值，但是隻是為了給人看的，真正在

　　　　　　記憶體中還是依靠記憶體位址值來進行運算的，而不是哈希值）

TreeSet

底層資料結構： 二叉樹 （保證元素唯一性的方法是保證compareTo 方法return 0）

　　　　　　比較方式：

方式一、就是讓元素自己具有比較性，元素需要實作comparable接口，重寫其中得compareTo方法，這個排序叫做自然排序（預設排序）

　　　　　　　　　　　　　　1、 無序性（按照輸入元素類中自定義的compareTo方法來排定存儲對象。）

　　　　　　　　　　　　　　2、 單一性（通過判斷元素類中自定義的compareTo方法放回值是否為0來判斷元素是否相等。）

　　　　　　　　　　　　　　3、 讓需要存入到TreeSet中的元素，實作comparable接口，該接口中定義了一個public int compareTo方法

　　　　　　　　　　　　　　4、 compareTo 方法：我們需要在類定義中重寫該方法， public int compareTo，

　　　　　　　　　　　　使得： 當有e.compareTo(e1)時，

　　　　　　　　　　　　　　如果e大于e1則傳回正數，當e小于e1則傳回負數， 等于則傳回0.

　　　　　　　　　　　　　　　　而且當有e等于e1時， 可以定義附屬判斷條件來判斷 兩個對象的大小。

　　　　注意：TreeSet 本情況的所有的底層比較原理隻是調用了元素的compareTo方法，與 equals等方法都無關。

　　　　　　　　　　　　　　（add、contains、remove等需要用到比較的方法）

　　　　　　是以我們定義所有的比較都傳回正數，那麼靠周遊疊代器取出的元素順序和存入順序一樣。

　　　　　　如果定義所有的比較都傳回負數，那麼靠周遊疊代器去除的元素順序和存入的順序相反。

　　　　　　如果定義所有比較都傳回0 ，那麼就隻能存入一個元素，最後也隻能取出一個元素。

　　　　方式二、當元素自身沒有比較性或者具有的比較性不是自身所需要的，那麼就要讓集合自身具有比較性。

　　　　　　　　　　那麼就要在集合一初始化時定義比較方式（也就是調用集合的構造方法）

　　　　　　　　1、 無序性（按照集合執行個體化的時候的比較器來排布元素的存儲順序。）

　　　　　　　　2、 單一性（通過集合的比較器的compare方法傳回值是否為0 來判斷元素是否相等。）

　　　　　　　　3、 定義一個比價器的類，使其實作comparator接口， 重寫覆寫其中的 int compare(T o1, T o2) 方法。

　　　　　　　　4、 compare 方法：我們需要在比較器類定義中重寫該方法，int compare(Object o1, Object o2)，

　　　　　　使得： 我們在該方法中比較兩個對象，或者比較其對象的方法，或者直接定義一個數值傳回。

　　　　　　　　　 當傳回值為正時代表o1大于o2，當傳回值為負時代表o1小于o2，傳回值為0 則代表兩個對象相等。

　　　　　　　　　而且當初步判斷有o1等于o1時， 可以定義附屬判斷條件來判斷 兩個對象的大小。

　　　　　　注意：TreeSet 本情況的所有的底層比較原理隻是調用了集合比較器的compare方法，與 元素equals等方法都無關。

　　　　　　　　　　（add、contains、remove等需要用到比較的方法）

　　　　　　　　是以我們定義所有的比較都傳回正數，那麼靠周遊疊代器取出的元素順序和存入順序一樣。

　　　　　　　　如果定義所有的比較都傳回負數，那麼靠周遊疊代器去除的元素順序和存入的順序相反。

　　　　　　　　　　如果定義所有比較都傳回0 ，那麼就隻能存入一個元素，最後也隻能取出一個元素。

4. Map

映射（Map）沒有實作 Collection 接口，它的每一項都是成對存儲的，（key, value）。存儲的每一個資料都有一個對應的關鍵字key，key 是唯一的。

key雖然決定了資料在映射中存儲的位置，檢索資料時，需要提供相應的Key。但是并不是靠key本身來确定的，而是使用了一種散列（hashing）技術來處理，産生一個被稱為散列碼（hash code）的整數值，它通常作為一個偏置量，該偏置量是相對于資料存儲位置與map記憶體起始位置的偏移，由此來确定（key, value）的存儲位置。

理想情況下，散列處理應該産生給定範圍内均勻分布的值，而且每個關鍵字應得到不同的散列碼。

Map有多種實作：

HashMap：非線程安全，底層為散清單，允許存儲一個 null key，和多個 null value。

HashTable：線程安全，執行效率較低。所有的 key 必須非null。為了能更高效的工作，所有的類必須實作 equal()和 hashcode()方法。

LinkedHashMap：非線程安全，底層實作為散清單，能夠保證元素的插入順序（相對于讀取而言的）。

WeakHashMap：非線程安全，底層實作為散清單，當某個鍵不在被引用時，其對應的鍵值對可能會對GC回收，從map中清除。

TreeMap：底層為二叉樹結構，元素按key值升序排列，不是按插入順序。