顯示具有 hash function 標籤的文章。 顯示所有文章
顯示具有 hash function 標籤的文章。 顯示所有文章

2022/03/22

簡單輕鬆十分鐘學會 Hash Map (雜湊表) 刷 LeetCode

先來個地獄梗 emtional damage!

一、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) 。