【數據結構】Map與Set結構詳解

數據結構系列五：Map與Set(一)

一、接口的實現

1.方法上

2.成員上

二、Map的內外雙接口結構

1.實現

1.1外部Map接口的實現

1.1.1臨摹整體

1.1.2外部類實現整體

1.2內部Entry接口的實現

1.2.1臨摹內部

1.2.2內部類實現內部

2.關系

3.意義

3.1邏輯內聚

3.2訪問封裝

3.3成套對應

三、Map實現類的存儲結構

1.包裝節點對象

2.數據組織結構

2.1數組+鏈表/紅黑樹

2.1.1結構

2.1.2順序

2.1.3復雜度

2.2紅黑樹

2.2.1結構

2.2.2順序

2.2.3復雜度

四、Map接口里的方法使用

1.外接口Map

1.1查詢

1.1.1鍵查詢值(無默認值):

1.1.2鍵查詢值(有默認值):

1.2修改:

1.3刪除:

1.4判斷

1.4.1判斷鍵存在:

1.4.2判斷值存在:

1.5獲取

1.5.1獲取所有鍵:

1.5.2獲取所有值:

1.5.3獲取所有包裝節點:

2.內接口Entry

2.1獲取

2.1.1獲取節點的鍵:

2.1.2獲取節點的值:

2.2修改:

五、Set接口

1.復用性

2.定義分類

六、Set接口里的方法使用

1.獲取

1.1獲取所有元素:

1.2獲取元素個數:

1.3獲取迭代器:

2.添加

2.1添加一個元素:

2.2添加集合元素:

3.刪除:

4.判斷

4.1判斷是否空:

4.2判斷一個元素存在:

4.3判斷集合元素存在:

5.清空:

一、接口的實現

接口是在實現類子類里完整實現的

1.方法上

接口處在被使用范圍下時，在意義編譯的要求下，一定要被連接有此接口的實現類賦值向上轉型 使得里面的抽象方法都被重寫有意義上：

因為這些抽象方法都無方法體的，每個抽象方法設置?有點意義的也就只有形參類型、返回值類型，無完整意義的，所以抽象方法的完整實現是在實現類子類里完成的

2.成員上

接口里一般不會定義成員變量，更多時候成員變量都是在實現類子類這邊 結合臨摹要實現的抽象方法，在可創建的各樣對象中根據具體需求選擇針對性地自定義實現的，從而達到接口實現的多樣化，所以接口設置成在實現類里面創建成員變量是接口能多樣化實現的保障

二、Map的內外雙接口結構

public interface Map<K, V> {//外部Map整體接口//Map接口臨摹 從外部、握整體操作包裝節點：V put(K key, V value);V get(Object key);V remove(Object key);void putAll(Map<? extends K, ? extends V> m);void clear();...interface Entry<K, V> {//內部Entry局部接口//Entry接口臨摹 每個包裝節點對象自己對自身的操作：K getKey();V getValue();V setValue(V value);}
}

1.實現

1.1外部Map接口的實現

1.1.1臨摹整體

外部Map整體接口的抽象方法臨摹著從外部、握整體地能操作著?所有鍵值成對包裝單位體

1.1.2外部類實現整體

對應到具體實現類那邊，外部Map整體接口的實現類果真就額外有 操作所有包裝單位整體的入口成員變量，再配著?重寫著的操作整體的實現方法，外部Map整體接口的實現類(即實現類整體中不包含內部Entry實現類的外部Map實現類部分)實現了對包裝單位從整體的操作

1.2內部Entry接口的實現

1.2.1臨摹內部

內部Entry局部接口的抽象方法臨摹著 從內部包裝單位體自身對自己范圍內的內部操作

1.2.2內部類實現內部

對應到具體實現類那邊，內部Entry局部接口實現類就額外有 包裝單位自身的組成信息成員變量，配合著 重寫著的包裝單位自身內部操作實現方法，內部Entry局部接口實現類就也實現了它每創的包裝單位對象都能實現對自身信息的操作

2.關系

在每個Map實現類中，向整體Map接口向上轉型間接實例的從整體操作所有包裝單位的實例對象就只有它一個，而由它的內部類向上轉型Entry接口間接實例化的包裝單位對象創建得可就多了，即外部實現類Map一個實例對象管理著內部類Entry的許多實例對象

3.意義

3.1邏輯內聚

接口里面裝內部接口，內部接口Entry能訪問外部接口Map 就直接固定設置成相同的泛型參數K、V 直接保證上 從整體視角與個體視角管理包裝單位都要的類型恒統一

3.2訪問封裝

內部接口加層封裝于外部使用者接口里面，使內部接口受正確限訪問，包裝得更加針對且安全

3.3成套對應

外部接口實例化時，由于抽象相關的在去使用了的范圍內必須要重寫實現上其意義，因此外部接口的實現類也同時要求著去重寫實現有內部接口相關的所有抽象的東西，即也要求同時有去實例化內部接口 也實現它的意義，所以這也就使得有內部接口的接口實例化需要對應有內部類的實現類來實現，接口與類對應著實現的（接口的實例化都是間接的）

三、Map實現類的存儲結構

在Map對應實現類的引用管理對象體系中，最上層Map實現類的實例對象 通過分層向下管理來組織基本節點對象的數據組織結構 或者由基本對象節點自連串自己組織成數據組織結構，實現著最上層類引用對象管理著成組織數據結構中的每個單位基本節點對象

1.包裝節點對象

Map數據結構里面的基本操作單位是 關鍵字對象與值對象對應兩合并成的一個鍵值對包裝對象(String與Integer兩合并包裝成一個對象)，而其它數據結構的基本操作單位都是一個底層直接對象(以Integer一個對象為基本操作單位)

2.數據組織結構

2.1數組+鏈表/紅黑樹

2.1.1結構

HashMap用數組+鏈表/紅黑樹的數據組織結構組織包裝節點對象：

將包裝節點的鍵值通過哈希函數計算映射到數組索引 來確定存放，每個數組元素哈希桶里面都是存放包裝節點自實現作的一個鏈表頭節點或者根節點

包裝節點映射到數組同一位置時，節點會自連接組織連接進桶里存放，到鏈表過長時 此數組元素哈希桶里面的鏈表節點 都會通過Node類extend繼承擴展轉為TreeNode類 全部轉為紅黑樹節點轉化成裝紅黑樹的哈希桶結構(提高查詢效率)來繼續存放在此數組索引位置

2.1.2順序

通過哈希函數計算映射索引來確定元素在數組位置的，元素們用此函數來確定的位置之間是無序的

2.1.3復雜度

一次哈希函數計算映射就能鎖定元素位置，數據操作查插刪的時間復雜度都是O(1)，哈希結構的存儲能實現數據的極速操作

2.2紅黑樹

2.2.1結構

TreeMap中，通過在包裝單位里面定義自己自連串組織結構，包裝單位們能自組織成紅黑樹的結構(一種自平衡的二叉搜索樹)

2.2.2順序

包裝單位按照鍵值的順序有序地在樹中存儲

2.2.3復雜度

通過比較搜索來確定元素的，數據操作查插刪的時間復雜度都是O(logN)，即樹的高度次

四、Map接口里的方法使用

Map接口里只有抽象方法的臨摹，抽象方法的實現、成員變量的定義存在、數據結構的組織都是在實現類TreeMap、HashMap中才有去實現的

1.外接口Map

外部接口對應實現的外部類 完成從外部整體對自己里面創建的所有包裝節點的整體操作：

1.1查詢

1.1.1鍵查詢值(無默認值):

t/hMap.get(Object key);

—> return V

鍵查詢獲取此map實現類創建的包裝節點數據組織結構里某鍵值對象對應的包裝節點里的值

1.1.2鍵查詢值(有默認值):

t/hMap.get(Object key,V defaultValue);

—> return V

鍵查詢獲取此map實現類里面的此鍵對應的包裝節點的值，如果此創建的數據節點結構中沒有此鍵值的包裝節點，則返回默認值

1.2修改:

t/hMap.put(K key,V value);

—> return V

修改設置實現類map里面創建存儲的某鍵對應的包裝節點里的值

1.3刪除:

t/hMap.remove(Object key)

—> return V

鍵查詢刪除 map里面對應的包裝節點，并將此包裝節點里的值對象返回

1.4判斷

1.4.1判斷鍵存在:

t/hMap.containsKey(Object key);

—> return boolean

判斷map實現類里面創建的所有包裝節點中是否含有此鍵對象

1.4.2判斷值存在:

t/hMap.containsValue(Object value);

—> return boolean

判斷map實現類里面創建的所有包裝節點中是否含有此值對象

1.5獲取

1.5.1獲取所有鍵:

t/hMap.keySet();

—> return Set<K>

將map實現類里面創建的所有包裝節點的鍵對象存放在Set集合中返回獲取

1.5.2獲取所有值:

t/hMap.values();

—> return Collection<V>

將map實現類里面創建的所有包裝節點的值對象存放在Collection集合中返回獲取（Set集合里面不會存放重復的值，value的值是可有重復的，就不要用Set集合接收來用Collection集合接收了）

1.5.3獲取所有包裝節點:

t/hMap.entrySet();

—> return Set<Map.Entry<K,V>>

將map實現類里面創建的所有包裝節點向上轉型回接口類型的包裝節點，存放在Set集合中返回獲取

2.內接口Entry

內部接口對應實現的內部類 完成從內部每個包裝節點對自身的操作，HashMap實現類里面用Node內部類 對應實現Entry內部接口，TreeMap實現類里面用Entry內部類 來對應實現Entry內部接口：

2.1獲取

2.1.1獲取節點的鍵:

t/hEntry.getKey();

—> return K

獲取該包裝節點里面裝的鍵對象

2.1.2獲取節點的值:

t/hEntry.getValue();

—> return V

獲取該包裝節點里面裝的值對象

2.2修改:

t/hEntry.setValue(V value);

—> return V

將該包裝節點里面的值對象修改設置為指定值對象

五、Set接口

1.復用性

Set與Map結構都是一樣的，只是Set使用時 它的基本節點鍵值包裝對象里面的值對象統一設置成了Object類對象來填充，相當于 不管查詢意義的Object 連著存儲，實現的也就是只針對鍵對象的不重復數據的存儲，它里面的元素實際上就是包裝節點下的鍵值

2.定義分類

Set實現類的底層也都是復用Map實現類的那套，定義的基本操作對象也都還是包裝節點，但已忽略掉了值對象，相當于只存一個不會重復的鍵對象節點了，所以在集合中把它單獨定義分類出來視為元素了，所以在集合中它的接口Set、它的實現類TreeSet、TreeMap都是定義在Collection接口下的