?系列文章：

? ? ? ? ? ? ? ? ?1.? ?先導(dǎo)片--Map&Set之二叉搜索樹(shù)

? ? ? ? ? ? ? ? ?2.? ?Map&Set之相關(guān)概念

目錄

1.搜索

1.1 概念和場(chǎng)景

1.2 模型

2.Map的使用

2.1 關(guān)于Map的說(shuō)明

2.2 關(guān)于Map.Entry的說(shuō)明

2.3 Map的常用方法說(shuō)明

3.Set的說(shuō)明

3.1關(guān)于Set說(shuō)明

3.2 常見(jiàn)方法說(shuō)明

---

1.搜索

1.1 概念和場(chǎng)景

Map和Set是專(zhuān)門(mén)用于搜索的容器或數(shù)據(jù)結(jié)構(gòu)，它們的搜索效率取決于具體的實(shí)例化子類(lèi)。傳統(tǒng)的搜索方式包括直接遍歷和二分查找，但它們有一些限制。

1. 直接遍歷：時(shí)間復(fù)雜度為O(N)，當(dāng)元素?cái)?shù)量較多時(shí)效率較低。
2. 二分查找：時(shí)間復(fù)雜度為O(log N)，但前提是序列必須是有序的。

這些方法更適合靜態(tài)類(lèi)型的查找，即在查找過(guò)程中不會(huì)進(jìn)行插入和刪除操作。然而，現(xiàn)實(shí)生活中的查找需求可能更加復(fù)雜，例如：

1. 根據(jù)姓名查詢(xún)考試成績(jī)
2. 不重復(fù)集合，需要先檢查關(guān)鍵字是否已經(jīng)存在于集合中

在這些情況下，直接遍歷和二分查找可能不太適用，因?yàn)樗鼈儫o(wú)法很好地處理動(dòng)態(tài)查找的需求。所以，我們將介紹一種適合動(dòng)態(tài)查找的集合容器：Map和Set。

1.2 模型

在搜索數(shù)據(jù)時(shí)，我們通常將需要查找的數(shù)據(jù)稱(chēng)為關(guān)鍵字（Key），而與之對(duì)應(yīng)的數(shù)據(jù)稱(chēng)為值（Value）。這種鍵值對(duì)的結(jié)構(gòu)被稱(chēng)為Key-value。根據(jù)實(shí)際需求，我們可以使用不同的模型來(lái)存儲(chǔ)和處理這些鍵值對(duì)：

• 純 Key 模型：例如，當(dāng)我們需要快速查找某個(gè)名字是否在某個(gè)班級(jí)中時(shí)，我們只需要知道名字這個(gè)關(guān)鍵字即可。在這種情況下，我們只需要存儲(chǔ)關(guān)鍵字，而不需要存儲(chǔ)與之對(duì)應(yīng)的值

• Key-Value 模型：例如，當(dāng)我們需要統(tǒng)計(jì)文件中每個(gè)單詞出現(xiàn)的次數(shù)時(shí)，我們需要同時(shí)存儲(chǔ)單詞（關(guān)鍵字）和它們出現(xiàn)的次數(shù)（值）。在這種情況下，我們需要存儲(chǔ)鍵值對(duì)，即每個(gè)單詞及其對(duì)應(yīng)的次數(shù)。

Map是一種用于存儲(chǔ)鍵值對(duì)的數(shù)據(jù)結(jié)構(gòu)，它允許我們通過(guò)關(guān)鍵字快速查找對(duì)應(yīng)的值。Set則是一種只存儲(chǔ)關(guān)鍵字的數(shù)據(jù)結(jié)構(gòu)，它主要用于檢查某個(gè)元素是否存在于集合中。

2.Map的使用

map官方文檔

Map (Java Platform SE 8 ) (oracle.com)https://docs.oracle.com/javase/8/docs/api/java/util/Map.html

2.1 關(guān)于Map的說(shuō)明

Map是一個(gè)接口類(lèi)，該類(lèi)沒(méi)有繼承Collection，Map類(lèi)中存儲(chǔ)是<K，V>結(jié)構(gòu)的鍵值對(duì)，并且K一定是唯一的，不能重復(fù)。

2.2 關(guān)于Map.Entry的說(shuō)明

Map.Entry<K, V> 是Map內(nèi)部實(shí)現(xiàn)的用來(lái)存放<key, value>鍵值對(duì)映射關(guān)系的內(nèi)部類(lèi)，該內(nèi)部類(lèi)中主要提供了<key, value>的獲取，value的設(shè)置以及Key的比較方式。

方法	解釋
K getKey()	返回entry中的key
V getValue()	返回entry中的value
V setValue(V value)	將鍵值對(duì)中的value替換為指定的value

注意：Map.Entry<K, V>并沒(méi)有提供設(shè)置Key的方法

2.3 Map的常用方法說(shuō)明

方法	解釋
V get(Object key)	返回 key 對(duì)應(yīng)的 value
V getOrDefault(Object key, V defaultValue)	返回 key 對(duì)應(yīng)的 value，key 不存在，返回默認(rèn)值
V put(K key, V value)	設(shè)置 key 對(duì)應(yīng)的 value
V remove(Object key)	刪除 key 對(duì)應(yīng)的映射關(guān)系
Set<K> keySet()	返回所有 key 的不重復(fù)集合
Collection<V> values()	返回所有 value 的可重復(fù)集合
Set<Map.Entry<K, V>> entrySet()	返回所有的 key-value 映射關(guān)系
boolean containsKey(Object key)	判斷是否包含 key
boolean containsValue(Object value)	判斷是否包含 value

1. Map是一個(gè)接口，不能直接實(shí)例化對(duì)象，如果要實(shí)例化對(duì)象只能實(shí)例化其實(shí)現(xiàn)類(lèi)TreeMap或者HashMap?

??

2. Map 中存儲(chǔ)的是鍵值對(duì)（Key-Value），其中 Key 是唯一的，而 Value 可以重復(fù)。
3. 可以將 Map 中的所有 Key 提取出來(lái)，并存儲(chǔ)到一個(gè) Set 中進(jìn)行訪(fǎng)問(wèn)（因?yàn)?Set 不允許重復(fù)元素）。
4. 可以將 Map 中的所有 Value 提取出來(lái)，并存儲(chǔ)到任何 Collection 子類(lèi)的集合中（Value 可能有重復(fù)）。
5. 在 Map 中，不能直接修改 Key，但可以修改 Value。如果要修改 Key，必須先刪除原有的鍵值對(duì)，然后再重新插入新的鍵值對(duì)。

3.Set的說(shuō)明

set官方文檔

Set (Java Platform SE 8 )https://docs.oracle.com/javase/8/docs/api/java/util/Set.html

3.1關(guān)于Set說(shuō)明

Set與Map主要的不同有兩點(diǎn)：Set是繼承自Collection的接口類(lèi)，Set中只存儲(chǔ)了Key。

3.2 常見(jiàn)方法說(shuō)明

方法	解釋
boolean add(E e)	添加元素，但重復(fù)元素不會(huì)被添加成功
void clear()	清空集合
boolean contains(Object o)	判斷 o 是否在集合中
Iterator<E> iterator()	返回迭代器
boolean remove(Object o)	刪除集合中的 o
int size()	返回set中元素的個(gè)數(shù)
boolean isEmpty()	檢測(cè)set是否為空，空返回true，否則返回false
Object[] toArray()	將set中的元素轉(zhuǎn)換為數(shù)組返回
boolean containsAll(Collection<?> c)	集合c中的元素是否在set中全部存在，是返回true，否則返回false
boolean addAll(Collection<? extends E> c)	將集合c中的元素添加到set中，可以達(dá)到去重的效果

1. Set 是一個(gè)繼承自 Collection 的接口類(lèi)，它專(zhuān)注于存儲(chǔ)唯一的元素。
2. 在 Set 中，僅存儲(chǔ) key（關(guān)鍵碼），并且這些 key 必須是唯一的。
3. Set 的底層實(shí)現(xiàn)通?；?Map，它利用 key 與一個(gè)固定的對(duì)象（如 Object 的默認(rèn)實(shí)例）作為鍵值對(duì)存入 Map。
4. Set 的核心功能是去除重復(fù)的元素，確保每個(gè)元素只出現(xiàn)一次。
5. 由于 Set 中的 key 必須唯一，任何對(duì) key 的修改都是不允許的。如果需要修改 key，只能先刪除原有的 key，然后再重新插入新的 key。
6. Set 不允許插入 null 作為 key，以確保 key 的完整性和唯一性。