記錄學習內容。看網路上大大們的文章和影片，做些紀錄。
以下內容大多來自網路上大大們的文章。
還不了解，內容可能有錯誤。

教學來源:

Hash Table：Intro(簡介)
http://alrightchiu.github.io/SecondRound/hash-tableintrojian-jie.html

就算在平衡的Binary Search Tree(二元搜尋樹) 找資料，也要花O(logN)

Hash Table 的目標 就是 把 找資料 改成只要花O(1)

最簡單的想法就是陣列 。

array[0] = A
array [1] = B
array [2] = C

key 就是索引 0、1、2
Value 就是array[0] 、array [1] 、array [1] 。A、B、C

如果 我要找 key= 2 的 資料 。只要 array [2] 就可以找到 。所以花O(1)

但是 array 是連續的
今天變成
key (索引) : 0、20 、50
Value : array[0] 、array [20]、array [50] ，甲、乙、丙

明明只有3個key ，我還是要 創建一個 有51個int 空間的陣列 。

int array [50];
array[0] = 甲
array[20] = 乙
array[50] = 丙

所以要來想辦法 ，減少空間。

教學舉了一個例子:

key (索引) : 37、2、11、47
Value : array[37] 、array [2]、array [11]、array [47]，甲、乙、丙、丁

Key 先經過 一個 function ， 這個function 叫做Hash Function

這個function 的 目的 就是 把 key 變得越小越均勻 。

假如 經過這個funtion後 :

輸入37
輸出 0

輸入2
輸出 2

輸入11
輸出 5

輸入47
輸出 12

所以 原本的key (索引) : 37、2、11、47
變成 key (索引) : 0、2、5、12

原本的Value : array[37] 、array [2]、array [11]、array [47]，甲、乙、丙、丁
變成: array[0] 、array [2]、array [5]、array [12]，甲、乙、丙、丁

原本需要 array  48格 int 的空間 ，現在只需要13 格的空間 。

總結:

Hash Table和Direct Access Table的差別在於Hash Function。

Hash Table 只是多了 一個 function ，把key值改變。

看一下程式:

在java 類似的東西 應該是HashMap

Java HashMap
https://www.w3schools.com/java/java_hashmap.asp

練一下Java HashMap，

        HashMap<String, String> capitalCities = new HashMap<String, String>();
        capitalCities.put("England", "London");

Key 值 想成陣列 的索引
Value 想成 陣列的值

這邊的key值代表國家
value 代表城市

如果有兩個一樣的key值 ，新的key的value 會覆蓋舊的value。

像是可以改名字:

hashmap.put("myname", "A");
hashmap.put("myname", "B");

get 輸入-- >key值 ，輸出-- >value

capitalCities.get("England");

containsKey 可以確認key 在不在hashmap

https://leetcode.com/problems/two-sum/solution/

給一個陣列nums = [2,7,11,15]
目標是找到 兩個數字 相加 等於target = 9
所以 把數字2,7,11,15 當 key值 。
索引 0 、1、2、3 當value 值 。

迴圈到數字7的時候:
 9 – 7 = 2 ，為了要確認 2 在不在這個陣列 ，就用hashmap containsKey
，回傳true 就代表 在這個陣列 ， 然後 用 hashmap get方法 取得索引值(0 、1、2、3 ) ，就是答案了。

接著回到文章

什麼是Collision ? 碰撞

就是 array[0] = A和B
一個key 有兩個value 。
有兩種解決方法:

1 Chaining：使用Linked list把「Hashing到同一個slot」的資料串起來。
2 Open Addressing：使用Probing Method來尋找Table中「空的slot」存放資料。

第一種方法: 把後面的值 ，用 Linked list 資料結構 存 。
array[0] = A和B ，原本是存一個字母A ， 改成存Linked list ，A節點-- >B節點。

第二種方法: 找空的地方擺 :
array[0] = A和B 變成 array[0] = A、 array[1] =B

接著講了

Hash Function介紹 :

要想辦法讓 key 經過 Hash Function 後的 key 平均分佈(uniform distributed)

有兩類型的Hash Function:

m是指Table(陣列)的大小 ，
Division Method：m有限制，但是比較快。
Multiplication Method：m沒有限制，但是比較慢。

Division Method :就是取餘數的方法 。
假如table(陣列)的大小是8 (能夠裝8個東西)，
那 就會 除以 8 ，取餘數
因為 8 的餘數有0 1 2 3 4 5 6 7 ，剛好8個

這會造成一個問題:

例如「a_count、b_count、c_count」
例如 57 、67、47
除以 8 ，取餘數 後 ，會都是7 。
最後面幾個數一樣的，經過Division Method ，會變成都是7 這個key

會造成key集中在7 ，這就是Division Method的缺點 。
我們還是希望能讓key 均勻分布。

所以Multiplication Method 方法 有降低 這個問題

文章中的這張圖，代表步驟:
1 選一個A ，介於0到1之間的數字
2 原本的key是4 ，跟A相乘 ，寫成KA
3 KA取 分數部分
4 分數部分 乘 table大小(陣列大小)
5 取 整數部分 。就是新的key

看不太懂，先跳過，就是原本的key ，2進位表示時。
要讓每個01 ，都盡量 參加到 hash function

之後有看教學:
Hash Tables Playlist
https://www.youtube.com/playlist?list=PLDV1Zeh2NRsDH5Wq-Vk5tDb8gH03cULZS