擁抱「資料結構」的「演算法」(17) - 集合和映射

 

前言

講完雜湊之後，接著來認識最後兩個常見的資料結構：集合和映射，剛好他們也都可以延伸使用到 HashMap與 HashSet

---

生活常識

生活中有哪些東西具有唯一性呢？例如全世界找不到第二個你XD，我們的常常使用的身分證與車牌號碼，也都具有唯一性的，所以可以快速辨別身分

圖片來源:https://www.pexels.com/zh-tw/photo/132774/

你有使用網路字典的習慣嗎？當我們輸入某個字詞，按下搜尋之後，網頁就會顯示相關的說明文字，字典內含有大量的資料，如何快速找到字詞的相關解釋，關鍵字就十分重要

或是像 office word 中的目錄功能或一般閱讀書籍的目錄，也可以讓我們快速查找相關內容以及對應的頁碼

圖片來源:microsoft

---

專業知識 - 集合 Collection

會儲存多筆資料，像是陣列(Array)、串列(List)與 HashSet 都是集合的一種，今天會特別介紹一下 HashSet

集合的特性

• 排序性：會自動將資料由小至大排序 (例如：SortedSet)
• 順序性：資料會以某種順序儲存資料 (例如：List)
• 重覆性：資料是否允許重覆 (例如：List 允許重覆，HashSet 不允許重覆)
• 鍵值：可使用鍵值來存取資料，每個集合中的元素都有自己的鍵值，鍵值具唯一性

---

專業知識 - HashSet

是一種實作集合(Collection)的類別

特性

• 無排序
• 無順序
• 資料不可重覆，可以含有空元素
• 無鍵值

程式碼

下面用 C# 的 HashSet 類別來操作給大家看，我們將數字0 ~ 10各別除以 5 在取餘數將資料存入 HashSet 與 串列 List 中，會發現資料若已經存在 HashSet 中，則不會重覆新增

數字	除以 5 取餘數
0	0
1	1
2	2
3	3
4	4
5	0
6	1
7	2
8	3
9	4
10	0

HashSet<int> set = new HashSet<int>(); //宣告一個集合
List<int> list = new List<int>(); //宣告一個串列
for (int i = 0; i <= 10; i++) // i = 0 ~ 10 
{
    set.Add(i % 5); // i 除以 5 取餘數，將值存入集合中
	list.Add(i % 5); // i 除以 5 取餘數，將值存入串列中
}

輸出結果：HashSet 資料不重覆，List 資料可重覆

實際應用

資料不可重覆的特性可以用在比對不同資料之間的交集與聯集

HashSet<int> set1 = new HashSet<int>() { 1, 5, 7 }; //宣告一個集合含有 1, 5, 7
HashSet<int> set2 = new HashSet<int>() { 5, 6, 7 };  //宣告一個集合含有 5, 6, 7
set1.IntersectWith(set2); // 取得這兩個集合的交集
foreach (var data in set1) // 將交集的資料印出來
{
Console.WriteLine(data);
}

輸出結果：
5
7

---

專業知識 - 映射 Map / 字典 Dictionary

Map 可以讓我們使用鍵快速的找到對應的內容，也就是我們常稱的鍵值對(key-value pairs)，是索引鍵和內容的集合，常用 Map < K, V >表示

特性

• 鍵值不能重覆，每個鍵值只能對應一個內容
• 內容可以重覆，不同鍵值，可存放別的鍵值存放過的內容
• 可各別操作鍵值或內容

程式碼

下面使用 C# 的 Dictionay 類別來操作給大家看，Java 的 HashMap 也是類似的行為，資料無順序性，無排序性，而TreeMap 的資料則會由小至大排序

var items = new Dictionary<string, string>(); //建立 Dictionary
items.Add("0912333444", "小明"); //以電話做為key，姓名為value
items.Add("0912555777", "小美");
items.Add("0912222111", "小乖"); //有兩筆小乖的電話，只要鍵值不同就可以新增
items.Add("0912222888", "小乖");

foreach(var data in items){ //將全部的資料印出來
    Console.WriteLine("Key:" + data.Key + ",Value:" + data.Value);
}

//直接透過電話(鍵值)撈取姓名(內容)
Console.WriteLine("0912333444是" + items["0912333444"] + "的電話");

輸出結果：可以看到每個電話可以對應到一個姓名，也可以針對某個鍵值快速撈取資料，另外撈取所有電話(鍵值)出來使用也是沒問題的哦

是不是跟昨天的班級血型表格長得很相似，都含有一個鍵與內容，差別在於 Dictionary 為非執行緒安全，同時被多人存取或更新時，內容易有問題，而 Hash Table 為執行緒安全

---

今日小結

映射是使用率很高的一種資料結構，由其可透過鍵值搜尋資料的方式真的很方便，一定要記得它XD

---

今日謎題

我們常說一個人的態度，決定一個人的高度，請問你知道態度的英文 ATTITUDE，它英文單字換成數字後，全部加起來，總分是多少嗎？

昨日解謎

一串神秘數字：25, 5, 19, 8, 4, 15
一個公式 H(x) = x mod 8 ( B 指的就是桶的數量，儲存空間可以存 8 筆資料，1 筆為 1 桶， 8 筆共 8 桶)

數字	數字除以 8 取餘數 = 索引值	索引對應到的內容
25	1	Y
5	5	E
19	3	S
8	0	I
4	4	D
15	7	O

小美回覆男友的求婚：YES I DO，你答對了嗎？