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

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

以電腦的儲存方式要嘛就是連續跟非連續(array or pointer)，map是array的一種延伸用法，大家看一下這張圖。

一個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的時候，就把值串在鏈結就行了！
圖:

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

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