一、Hash Map
1.1 基本觀念介紹
- Hash map 是儲存 (key, value) 這種 mapping 關係的一種資料結構 (當數據儲存在記憶體中時，決定數據的順序和位置的稱之為資料結構)
- 各語言 / library 基本上有其 hash function，如有需要也可以自行建置
- 語言不同名稱也會不同，但基本上 Hash map == Hash table == Hash object == Hash dictionary
(https://vhanda.in/blog/2012/07/shared-memory-hash-table/)
舉例來說，如果我們有 n 個數字要儲存時，通常會用 array 來存。 存好後如果我們拿到另一個數字 37，要判斷這個數字有沒有在 array 裡面，那我們就得跟 array 裡的元素一個個比較，這時 time complexcity 就會是 O(n)；下次再換查另一個數字時， time complexcity 又就會是 O(n)。 但如果已經先建立好 hash table，之後如果要查數字 37 時，建立 hash map 時雖然 time complexcity 會是 O(n)，但查詢的 time complexcity 就只會是 O(1)。 不過 O(1) 還是理論值，insert、search、lookup、delete 都有可能造成 time complexcity 是 O(n) (請看 example 3) 。
範例 1 是自己建置一個 hash table ，當然這是很隨便的寫法，非常容易有 collision (下節會提到)，如前面所提到的在各語言 / library 基本上已經有其 hash function，不需要自己再建置。
Example 1:
- Hash function: \n -> n % 7 // The method to put the data to the specific buckets
- According to the hash function we determined, so there is 7 buckets: 0, 1, ... , 6
- Then insert (37, 8)
- And 37 % 7 = 2 // Bucket 2
- Put pair (37, 8) in bucket 2 // 37 is key and 8 is the value
範例 2 是要再塞新的 (key, value) 進去。
Example 2 :
- If we want to insert (44, 9)
- Then 44 % 7 = 2 // Bucket 2
- Put pair (44, 9) in bucket 2
- Then the bucket 2 will store: [(37, 8), (44, 9)]
範例 3 是如果我們想查詢 value == 44 時。
已經知道要找什麼 (lookup)，比如 value == 44，這時候 time complexcity 是 O(1)
還不知道要找什麼 (search)，比如設定 value > 3，這時候 time complexcity 是 O(n)。
Example 3 :
- If we want to lookup 44
- 44 % 7 = 2 // Check bucket 2
- Compare 44 with 37 // Not match
- Compare 44 with 44 // Match! Then return 9
1.2 Collision
指 hash function 在不同的 input 下，得到了相同的 output，導致儲存到同一個 bucket 記憶體位置上；比如剛剛的範例 1 和 2， (37, 8) 和 (44, 9) 因為建置條件設定的關係都放在同一個 bucket 裡了。
解決方式是 :
增加 hash table 的 bucket 數量 ⇒ 由於 hash table 的 size 並不是無限擴展的，在有限的記憶體空間下，還是會有 collision 發生的可能
在每個桶子中用一個 linked list 來儲存 value，這種方式稱為 Chaining (鏈結法)
絕大部分的語言已經處理好 collision，所以通常不用太過於擔心，但是如果有出現這個狀況，可以自製自己的 hash function。
1.3 Javascript Map
JavaScript 有兩種方式去建立 Hash map :
每個 Object 都是簡單的 JS Map， object 的 key 只能是字串 (string)
Map 跟 object 一樣，但 map 的 key 可以是任何資訊型態
- new Map() ⇒ creates the map
- map.set(key, value) ⇒ stores the value by the key
- map.get(key) ⇒ returns the value by the key, undefined if key doesn’t exist in map
- map.has(key) ⇒ returns true if the key exists, false otherwise
- map.delete(key) ⇒ removes the value by the key
- map.clear() ⇒ clears the map
1.4 實際運用範例
使用者提交試卷答案到伺服器時，假設得到一份有 question id 和 answer 的清單，
基本想法是先用一層迴圈比對伺服器端的題目列表，找出和 question id 相符的答案列表，
再用一層迴圈去比較前述得到的列表答案和使用者提交的 answer；
但如果題目量很高、或是使用者很多，則會造成運算量倍增且耗時。
這時候就可以用建立一個 Hash Map (其實這也就是 Database Indexing)，
將提交的答案 以 question Id 為 key，answer 為 value，
再去比對伺服器端的題目列表 for 迴圈比對 key，若一致則可以比對同一個 bucket 裡的 answer，進而計算分數。
二、解題思路 & 題目整理
- 題號 : 根據 LeetCode 題目出現的頻率, top interview 150 等整理的，但注意不代表這就涵蓋所有面試會考的題目。或你可以選擇 Grind 來安排你要刷的題目
- 難度 : 按照你現在想要的難度選擇刷題
- 重要性 : 比如說你注意到、或別人提到 Google 很常考這個題目之類，可以設定你覺得相對的重要性，之後可以拿來篩選用
- 第一次是否解出來 : 紀錄解題是否第一次就成功，若不成功可能需要複習
- 解題思路 : 題目的思路過程，寫大綱就好不用寫很詳細
- 其他解法 : 若解出來是否還可以想到其他解法，或是看到別人提供了更好的解法便記錄下來，在面試時還可以提出自己有不同解法
- 學到技巧 : 如此題可以用 two pointer 來解，寫下來下次遇到別的題目就可以知道說我多一個解法可以想想看可不可行
- 複習次數 : 用來記錄第一次解不出來的題目之練習次數
- 複習筆記 : 有可能再做一次還是解不出來，那可寫下這次癥結點是什麼，怎麼解決的，盡量完全理解解法，讓自己如果再做一次題目時若還是卡住，可以看筆記或是回想筆記試圖解出來
- 上次解題時間 : 可用來篩選下次該複習的題目
沒有留言:
張貼留言