最近在梳理一些關於java的概念，這篇文章是最近筆記中關於基礎數據結構的部分，因為記錄筆記的時候思路比較天馬行空，所以不知道這篇文章的思路能不能清晰，姑且總結下將要涉及到的方面（jdk1.8）（另外畢竟是自己的理解，如果能指出錯誤，不勝感激）：
基礎數據結構繼承關係圖
相關接口的一些解讀
iterable和iterator的異同
map接口中值的注意的地方
collection類族和map類族
基礎數據結構接口繼承關係圖
關於接口的一些解讀
我們就解釋和基礎數據結構關係比較密切的接口iterable、iterator、map。除了這三個接口之外，其實還有比較重要的接口比如comparator、enumeration、spliterator，在一些具體的基礎數據結構中為了滿足不同的功能需求，有選擇得繼承了這些接口，他們的功能就和他們得名字一樣，值得一提的是spliterator接口，這是在1.8中新加入的一個接口，基本數據結構基本上都繼承了這個接口，該接口的功能是產生一組分割後的可迭代對象，這些對象是原來數據集的一個子集，這樣做的好處在與對原數據集的處理可以等價為對這些分割後數據集的處理，而對這些數據集的處理是可以並行進行的，從而實現了對多線程或者多核或者分佈式編程的支持（當然這是一個非常複雜的部分，也是java8中最亮眼的新特性）。還需要注意的是Collection接口直接繼承了iterable接口，以實現collection類族的可迭代，但是map是沒有繼承iterable接口的，也就是說不能通過iterable中的方法遍歷map類族（map類族有相應的遍歷方法，在後面會提到），下面詳細介紹一些接口。
iterable接口
該接口在文檔中的說明是：
實現此接口允許對象成為“for-each loop”語句的目標
可以看到其中比較重要的一個方法iterator()，該方法返回一個類型為T的迭代器，所以實際上iterable接口並沒有直接實現對象的可迭代，而是通過iterator的邏輯來實現對象的迭代。
iterator
可以看到兩個比較重要的函數，hasNext()和next()通過這兩個函數就可以實現一個對象的可迭代化。至於他的實現邏輯在下面部分將做詳細闡述。
iterator和iterable的關係和區別
如果說iterable接口的目標是實現對象的可迭代，那麼iterator就是iterable選擇的一種方法，也就是說iterator是一種普適的、與具體集合鬆耦合的迭代邏輯。比如說對於一個arrayList，該類繼承了iterable接口，為了實現該接口，我們需要實現arrayList的迭代方式，如果我們使用以下代碼：
在這段代碼中使用了arraylist.length,即與具體對象是緊耦合的，但是我們無從得知將來實例化的對象是怎麼樣的，也就是說arraylist參數是變化且未知的，而如果採用固定值會造成數組訪問越界或者數組訪問不全的問題，這就導致了無法實現arraylist的可迭代。但是換種方式來思考，我們是如何遍歷鏈表的，在遍歷鏈表的時候我們可以無需關心鏈表的具體結構，我們只需要問程序，還有下一個嗎，如果程序回答有，那麼我們就進行處理，如果回答沒有，那麼我們就結束處理，而iterator則採用了與這個相似的邏輯，通過hasNext()和next()即可以實現集合的遍歷，這種遍歷邏輯擺脫了對於具體對象的依耐，所以iterable採用了這種邏輯來實現對象的可遍歷性。那麼為什麼collection接口不直接繼承iterator接口而繼承iterable接口呢，這就不得不佩服sun的大佬們，前面提到了iterable中有一個方法為iterator()方法，該方法是一個工廠方法，返回一個類型為T的迭代器，採用的是iterator的迭代邏輯，這樣做有什麼好處呢，在實際代碼環境中，我們對一個可迭代對象的迭代訪問不管是時間還是次數都是隨機的，可能我們需要對一個可迭代對象同時進行迭代訪問，如果我們只是實現iterator接口，iterator會在原始數據上使用指針進行標記，表示我們訪問的位置，但是當我們並行迭代訪問的時候，指針的移動會受並行迭代的影響，造成指針標記位置的錯誤，而繼承iterable使用iterator()方法則可以解決這個問題，iterator()是一個工廠方法，會返回一個迭代器，當需要對對象迭代訪問的時候，即生成一個對應的迭代器，該次迭代訪問所有操作對應該次迭代器，當需要並行迭代訪問的時候，生成多個迭代器，每個迭代訪問的操作在其對應的迭代器上被記錄，指針由該迭代器維護，從而實現了並行迭代訪問。
map接口
在map接口中已經定義了絕大部分map的操作，具體的功能可以看看上面的圖，有些注意的地方放在後面具體的實現類中解釋。
具體類繼承關係圖
首先從圖中可以看到，java基礎數據結構主要由兩個基礎的類，分別是AbstractCollection和AbstractMap,他們是java共同基類Object的子類，分別是collection結構和map類結構的基類。
collection類族
AbstractCollection:
其繼承了Iterable和Collection接口，並實現了絕大部分的功能，但是沒有實現iterator和size方法，所以他依舊是一個抽象類，他為整個collection類族定義了一個基調，在他的基礎上如果要實現一個不可修改的集合類，只需要實現iterator和size方法即可，如果要實現一個可修改類，只需要額外覆蓋方法add並實現iterator中的remove方法（這些方法在接口中已經被定義了）。該類提供了操作集合的基礎方法（注意其中的兩個abstract聲明的方法）：
在AbstractCollection的基礎上，衍生出了AbstractLIst,AbstractQueue,AbstractSet,ArrayDeque
AbstractList為整個List類族定義了基調，collection沒有對集合的順序作具體的要求，但是list指明瞭集合中元素都是由順序的，提供了List類族訪問的基礎函數：
後面實現具體的list的時候，如果該list不可變，則只需要實現get和size就好，如果列表元素可變，則需要額外實現set，如果列表大小可變，則需要實現add和remove。下面看看具體實現的list的異同。
ArrayList是最常用的List實現類，允許所有元素，包括null。內部是通過數組實現的，它允許對元素進行快速隨機訪問。數組的缺點是每個元素之間不能有間隔，當數組大小不滿足時需要增加存儲能力，就要講已經有數組的數據複製到新的存儲空間中。當從ArrayList的中間位置插入或者刪除元素時，需要對數組進行復制、移動、代價比較高。因此，它適合隨機查找和遍歷，不適合插入和刪除。
Vector與ArrayList一樣，也是通過數組實現的，不同的是它支持線程的同步，即某一時刻只有一個線程能夠寫Vector，避免多線程同時寫而引起的不一致性，但實現同步需要很高的花費，因此，訪問它比訪問ArrayList慢。statck是對vector的擴展，使其支持使一個vector對象成為一個堆棧對象（先進先出）
LinkedList是用鏈表結構存儲數據的，很適合數據的動態插入和刪除，隨機訪問和遍歷速度比較慢。另外，他還提供了List接口中沒有定義的方法，專門用於操作表頭和表尾元素，可以當作堆棧、隊列和雙向隊列使用。
AbstractQueue：是隊列的抽象定義，其定義了一些隊列的基本操作，和AbstractCollection相比，AbstractQueue不允許元素為null，如果不能滿足這個要求，則應該使用AbstractCollection而不是AbstractQueue，目前繼承並實現了該抽象類的類只有PriorityQueue，這是一個帶有優先級的隊列，除了滿足元素不能是null之外，還需要滿足元素具有可比性，因為要維持元素的優先級，就需要對元素進行比較，確定順序。如果沒有指定優先級順序，則默認最小值為頭部。
然後使AbstractSet，該抽象類定義的set與數學上的集合相似，需要滿足一個比較重要的特性，互異性，就是說set中不能存在兩個一樣的值（擁有相同的hashcode），沒有對無序性作要求（treeset就是一個有序的set，但是這和我們常說的順序不同，treeset的順序指的是按照一定的排序算法排出的順序，而不是我們插入數據時的順序，所以在set中時沒有get(i)方法的，即不能按照索引進行訪問的，本來set是沒有索引這個概念的。）此類不會覆蓋AbstractCollection類中的任何實現。 它只是添加了equals和hashCode的實現，這是為了實現AbstractSet規定的互異性，通過將比較需要加入的元素的hasocode值是否和set中其他元素的hashcode值相等，如果相等，則拒絕插入，拋出異常。
實現AbstractSet的有EnumSet、HashSet(它有一個子類LinkedHashSet)，TreeSet，下面比較一下他們的異同點：
EnumSet比較少見，文檔上是這樣描述的：是一個與枚舉類型一起使用的專用 Set 實現。枚舉set中所有元素都必須來自單個枚舉類型（即必須是同類型，且該類型是Enum的子類）。 枚舉類型在創建 set 時顯式或隱式地指定。枚舉 set 在內部表示為位向量。 此表示形式非常緊湊且高效。此類的空間和時間性能應該很好，足以用作傳統上基於 int 的“位標誌”的替換形式，具有高品質、類型安全的優勢。也就是說比其他的set類型效率高上很多。而HashSet作用類似與arrayList，只是元素不能重複（沒有順序，如果要保持插入時迭代順序需要使用LinkedHashSet,需要按要求實現排序需要使用TreeSet），當然他們的底層實現也是不同的。
ArrayDeque是更高效的stack，java推薦的堆棧使用對象由stack變為了ArrayDeque。
下面是一些常用數據結構的一些性質中介，treeset我也不知道到底支不支持null
Map類族
AbstractMap
其定義的方法如下：
先介紹以下map的底層實現，map是一個數組和鏈表混合使用實現的一種數據結構，所以他在增刪改查方面的性能比較平衡，map是一個鍵值對集合，大部分map是沒有順序的，所以沒有按索引訪問的方法，但是treeMap是有順序的，但是這個順序不是數據插入的順序，而是按我們指定的排序方式所產生的順序，如果需要map有數據插入的順序，需要使用linkedHashMap。
下面介紹以下使用比較多的hashMap以及它和hashTable的關係：
hashTable是線程安全但不支持null的hashMap。
hashMap主要有以下方法：
map寫的比較少，主要它和collection可以類比，之後有機會再補充吧。
學習過程中遇到什麼問題或者想獲取學習資源的話，歡迎加入Java學習交流群346942462，我們一起學Java！