iT邦幫忙

2021 iThome 鐵人賽

DAY 13
0
Software Development

算法30天系列 第 13

Day.13 Hash map

任何語言都會提供這一種資料結構,像Golang的map
ex. var hash map[string]int

array是以int作為index key,但hash map可以用string或其他的型態去當index使用,時間速度也很快,新增刪除修改的時間複雜度都為O(1),所以寫程式的時候很常會用到。
簡單說一下它的原理!

以電腦的儲存方式要嘛就是連續跟非連續(array or pointer),map是array的一種延伸用法,大家看一下這張圖。
https://ithelp.ithome.com.tw/upload/images/20210921/20129767rBhvPZz0cm.png

一個hash map底下會有一個array,簡稱bucket(桶子),它是用來放val的,array的key都是int,那我們的key要用string那怎麼辦?
這時候會設計一個hash function把string hash成int的index,找到對應的bucket,只要確保算法在同樣的input有同樣的output,就可以用key val的方便存取值了。

如圖,現在有4個bucket,hash function就是把string的第一個值轉成ASCII code再去mod(%)4,像dog的d ASCII code是100,100%4數值剛好是0,而且每次hash出來的結果都不會變,這樣我們就可以把dog存在bucket 1。

現在要存apple的key,97%4 index是1,放在bucket 2。但!如果這時候要存dig這個key怎麼辦?因為dig跟dog開頭一樣,最後hash的值一樣是0,但bucket 1之前已經被佔用了。這種情況叫Hash map collision,不一樣的key hash出一樣的結果。解法有好幾種,以下為大家介紹的是鏈結法。

簡單來說就是用鏈結來處理,bucket存放一條鏈結,當發生collision的時候,就把值串在鏈結就行了!
圖:
https://ithelp.ithome.com.tw/upload/images/20210921/20129767Sg7kI5FphP.png

你可能會想到,如果key很多都是d開頭的,鏈結不就一直串下去嗎?
對沒錯~讀取的速度就會從O(1)變為O(n),因為找到bucket了,還在從鏈結的頭一直往下找,所以bucket的數量跟hash function夠不夠平均是很重要的!當bucket夠多,hash夠平均,速度就會一直保持在O(1),我上面提到的例子只是簡化給大家理解,真實上的string hash function更為複雜,而且bucket的數量還會動態去擴充!

明天會把今天講的寫成code!


上一篇
Day.12 Queue
下一篇
Day.14 Hash map II
系列文
算法30天30

尚未有邦友留言

立即登入留言