第11章 集合

11.1 數(shù)組與集合

11.1.1數(shù)組

• 邏輯結(jié)構(gòu)：線性的
• 物理結(jié)構(gòu)：順序的存儲結(jié)構(gòu)
• 申請內(nèi)存：一次申請一大段連續(xù)的空間，一旦申請到了，內(nèi)存就固定了。
• 存儲特點：所有數(shù)據(jù)存儲在這個連續(xù)的空間中，數(shù)組中的每一個元素都是一個具體的數(shù)據(jù)（或?qū)ο螅?，所有?shù)據(jù)都緊密排布，不能有間隔。
• 

• 操作
  • 查詢：每一個元素都有一個數(shù)值下標(biāo)，可以通過下標(biāo)瞬間定位到某個元素
  • 增加：
    • 從尾部增加：數(shù)組名[total++]=新元素
    • 從其他位置插入：先把index位置開始所有元素后移，然后數(shù)組名[index]=新元素
  • 刪除：先把index后面的元素前移，然后數(shù)組名[total--]=null
  • 改：直接數(shù)組名[index]=新元素
• 優(yōu)缺點
  • 優(yōu)點：查詢效率高
  • 缺點：添加/刪除效率低，因為都涉及到移動元素；無法直接獲取有效元素的個數(shù)，需要total來輔助
• 使用范圍：查詢操作遠(yuǎn)多于插入和刪除操作的場景

11.1.2集合

為了可以滿足用戶數(shù)據(jù)更多種的邏輯關(guān)系，而設(shè)計的一系列的不同于數(shù)組的可變的聚合的抽象數(shù)據(jù)類型。

總的特點：

1、只能存對象

2、容量可以自動調(diào)節(jié)

3、可以直接獲取有效元素的個數(shù)：size()

 

1、集合的幾個常用接口

2、詳細(xì)描述

• Collection 層次結(jié)構(gòu)中的根接口。Collection 表示一組對象，這些對象也稱為 collection 的元素。一些 collection 允許有重復(fù)的元素，而另一些則不允許。一些 collection 是有序的，而另一些則是無序的。JDK 不提供此接口的任何直接實現(xiàn)：它提供更具體的子接口（如 Set 和 List）實現(xiàn)。此接口通常用來傳遞 collection，并在需要最大普遍性的地方操作這些 collection。
  • List：有序的 collection（也稱為序列）。此接口的用戶可以對列表中每個元素的插入位置進(jìn)行精確地控制。用戶可以根據(jù)元素的整數(shù)索引（在列表中的位置）訪問元素，并搜索列表中的元素。
  • Set：一個不包含重復(fù)元素的 collection。更確切地講，set 不包含滿足equals(e2) 的元素對 e1 和 e2，并且最多包含一個 null 元素。正如其名稱所暗示的，此接口模仿了數(shù)學(xué)上的 set 抽象。
    • SortedSet進(jìn)一步提供關(guān)于元素的總體排序 的 Set。這些元素使用其自然順序進(jìn)行排序，或者根據(jù)通常在創(chuàng)建有序 set 時提供的 Comparator進(jìn)行排序。該 set 的迭代器將按元素升序遍歷 set。提供了一些附加的操作來利用這種排序。（此接口是 SortedMap 的 set 對應(yīng)接口）。
  • Map：將鍵映射到值的對象。一個映射不能包含重復(fù)的鍵；每個鍵最多只能映射到一個值。 Map 接口提供三種collection 視圖，允許以鍵集、值集或鍵-值映射關(guān)系集的形式查看某個映射的內(nèi)容。映射順序 定義為迭代器在映射的 collection 視圖上返回其元素的順序。某些映射實現(xiàn)可明確保證其順序，如 TreeMap 類；另一些映射實現(xiàn)則不保證順序，如 HashMap 類。
    • SortedMap進(jìn)一步提供關(guān)于鍵的總體排序 的 Map。該映射是根據(jù)其鍵的自然順序進(jìn)行排序的，或者根據(jù)通常在創(chuàng)建有序映射時提供的 Comparator 進(jìn)行排序。對有序映射的 collection 視圖（由 entrySet、keySet 和 values 方法返回）進(jìn)行迭代時，此順序就會反映出來。要采用此排序方式，還需要提供一些其他操作（此接口是 SortedSet 的對應(yīng)映射）。

 

3、概況總結(jié)

• Collection接口：定義了存取一組對象的方法，其子接口Set和List分別定義了存儲方式
  • Set：中的數(shù)據(jù)對象沒有順序且不可以重復(fù)
  • List：中的數(shù)據(jù)對象有順序且可以重復(fù)

Map接口定義了存儲“鍵（key）-值（value）映射對”的方法