iT邦幫忙

第 12 屆 iT 邦幫忙鐵人賽

DAY 17
0
Software Development

擁抱「資料結構」的「演算法」系列 第 17

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

前言

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


生活常識

生活中有哪些東西具有唯一性呢?例如全世界找不到第二個你XD,我們的常常使用的身分證車牌號碼,也都具有唯一性的,所以可以快速辨別身分
https://ithelp.ithome.com.tw/upload/images/20201001/20129841KyOdN2g2XS.png
圖片來源:https://www.pexels.com/zh-tw/photo/132774/

你有使用網路字典的習慣嗎?當我們輸入某個字詞,按下搜尋之後,網頁就會顯示相關的說明文字,字典內含有大量的資料,如何快速找到字詞的相關解釋,關鍵字就十分重要
https://ithelp.ithome.com.tw/upload/images/20200930/201298411WLbhz5cFA.png

或是像 office word 中的目錄功能或一般閱讀書籍的目錄,也可以讓我們快速查找相關內容以及對應的頁碼
https://ithelp.ithome.com.tw/upload/images/20201006/20129841AyqvYMxsDR.png
圖片來源: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 資料可重覆
https://ithelp.ithome.com.tw/upload/images/20201001/20129841CCMo6DS0U7.png

實際應用

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

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

https://ithelp.ithome.com.tw/upload/images/20201001/20129841f0DprQZJOa.png


專業知識 - 映射 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"] + "的電話");

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

https://ithelp.ithome.com.tw/upload/images/20201001/20129841bToehH3WrM.png

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


今日小結

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


今日謎題

我們常說一個人的態度,決定一個人的高度,請問你知道態度的英文 ATTITUDE,它英文單字換成數字後,全部加起來,總分是多少嗎?
https://ithelp.ithome.com.tw/upload/images/20201001/20129841QSSy2bVzKs.png

昨日解謎

一串神秘數字: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,你答對了嗎?


上一篇
擁抱「資料結構」的「演算法」(16) - 雜湊 Hash
下一篇
擁抱「資料結構」的「演算法」(18) - 何謂演算法 Algorithm
系列文
擁抱「資料結構」的「演算法」30

尚未有邦友留言

立即登入留言