iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 7
1
Software Development

Golang入門到進階實戰系列 第 7

Day7 資料結構Map

前言

在上一篇文章中,我們介紹了兩個線性的資料結構:數組和切片。在本文中,我們會介紹另一種在計算機科學裡常用的資料結構-哈希表(Hash Table)。

哈希表是一種儲存鍵/值對(keuy/value)的資料結構,在哈希表裡,我們會利用一些方法將將鍵映射到物件身上,鍵值之間的連繫關系就是哈希。哈希表有不同的實現方式,但是它們都擁有快速查找、新壞和刪除的特性。Go語言提供了一個內建的map型態。

哈希表

哈希函數

哈希表的關鍵在於哈希函數的選擇。我們會希望找到一個哈希函數,透過此函數將不同鍵映射到唯一的索引上,
https://ithelp.ithome.com.tw/upload/images/20190922/20120698rOIRCbvowz.png
但是這種映射是一種壓縮轉換,也就是輸出的Hash值範圍通常遠小於輸入範圍,不同的蛉入可能會Hash到同一個輸出。因此哈希表在實際使用時,理想狀態是不可能達到的。

兩個不同的輸入值,經過哈希函數計算出同樣的哈希值的現象稱為碰撞。
https://ithelp.ithome.com.tw/upload/images/20190922/20120698bI0wSL81gp.png

常見的哈希函數

  • 直接定址法:直接以鍵值k或者k加上某個常數c作為哈希值。
  • 數字分析法:提取鍵值中取值比較均勻的數字作為哈希值。
  • 除留餘數法:將鍵字除以某個不大於哈希表長度m,所得餘數即為哈希值
  • 分段疊加法:按照哈希表地址位數,將關鍵字分成位數相等的幾部分,然後將這幾部分相加,總和捨棄最高位後的結果即為哈希值。
  • 平分取中法:當鍵值各個部分分佈都不均勻時,可以求出它的平方值,然後按照需求取中間的幾位作為哈希值。
  • 偽隨機數法:採用一個偽隨機數當作哈希函數

碰撞解決

衡量一個哈希函數的重要指標就是發生碰撞的機率,還有發生碰撞後的解決方案。常見的碰撞解決方案如下:

  • 開放定址法:
    當哈希函數發生時,就去尋找下一個空的哈希地址,只要哈希表足夠大,空的哈希地址總能找到並將之記錄下來。
  • 鏈結地址法:
    將哈希表的每個單元都視為鏈表的頭結點,當衝突發生時就把該鍵值增加在以哈希值為頭結點的鏈表尾部。
  • 再哈希法
    衝突發生時,用其他哈希函數再計算另一個哈希函數地址,重覆計算到衝突不再產生為止。
  • 建立公共溢出區:
    將哈希表分為基本表和溢出表,發生衝突的鍵值都放入溢出表裡。

Map的使用

宣告與初始化

Go語言裡,宣告map物件的語法如下:

var m map [<KeyType>]ValueType

其中key必須為可以哈希的資料型態,value可以是任何的資料型態,包括map。
Map類似切片,屬於一種reference type,當m宣告後未賦值時,默認值為nil。

將map物件初始化需要用到map函數

//宣告一個m為map型態
var m map [int]int
//將m初始化
m=make(map[int]int)

如何使用

使用map需要注意的地方

  • map是無序的,每次print出來的map都不一樣,它必須通過key獲取value,而不是index。
  • map是無序的,和slice一樣,也是一種引用類型。
  • map可以使用內建的len函數,它會返回所擁有的key數量。
  • map並非thread-safe,在多個go-routine存取時必須使用mutex lock機制。
  • map的初始化可以通過key:val的方式,同時map內置會判斷是否存在key。

使用delete可以刪除map的元素:

// 初始化一個map物件
support := map[string]float32{"C":3.0, "Go":1.12, "Python":3.7, "Java":10 }
// 查調map有兩個返回,value和ok,當key不存在於map裡時,ok為false,反之ok為true。
version, ok := rating["Java"]
if ok {
    fmt.Println("We are supporting the Java %d",version)
} else {
    fmt.Println("We are not supporting Java yet")
}

delete(rating, "C") //從map裡頭刪除C的鍵值對

另外map是引用類型,多個變數操作同一個map物件時要小心

m := make(map[string]string)
m["Hello"] = "Bonjour"
m1 := m
m1["Hello"] = "Salut"

fmt.Println(m["Hello"]) //輸出: Salut

上一篇
Day6 資料結構 Array & Slice
下一篇
Day8 資料結構 Struct
系列文
Golang入門到進階實戰30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言