Оптимизация алгоритма Two Sum: ускорение поиска пар чисел с помощью хеш-таблиц

昨天我們看了插補搜尋法，今天我們要來看雜湊表 (又名哈希表)，還記得我們之前Leetcode實作的Two Sum嗎? 今天要來學怎麼讓他變得更快~ 雜湊函式是一個將輸入的 Key 轉換成數值的函式，這個數值可以用來決定資料在雜湊表中的位置 最常見的做法，是把輸入值除以陣列大小再取餘數 : h(k) = k % m k : 是輸入的鍵值(key)m : 是陣列的大小%(mod) : 是取餘數運算 舉例來說 : 假設陣列大小 m = 7，要存放的數字是 10 22 31: h(10) = 10 % 7 = 3 h(22) = 22 % 7 = 1 h(31) = 31 % 7 = 3 但10 跟 31 算出來的雜湊值一樣都是3 這種情況稱為碰撞(Collision)，是雜湊函式(Hash function)設計裡幾乎無法完全避免的問題， 等一下會介紹怎麼處理它。 把 key 平方，再取中間幾位數字當作雜湊值。 例如 : k = 512, k^2 = 262144 取中間 2位 : 21，所以 h(512) = 21。 將較長的 key 切割成數段 平均長度 的部分(最後一段不用) 位移折疊法(shift floding) : 相加後 mod bucket的數量即為索引 邊界折疊法(floading at the boundaries) : 將特定段落反轉後再相加 實務上常常需要對字串做雜湊(雜湊表的鍵值可能是名字、單字)。常見做法是把字串每個字元轉成對應數字(如ASCII碼)，再加權組合，這個做法稱為 多項式滾動雜湊函數（polynomial rolling hash function）: p 是一個質數(通常選31 or 53)s[i] 是字串第 i 個字元的數值 每個字元依照位置乘上不同權重，這樣即使兩個字串只是字元順序不同，雜湊值通常也會不同(例如 "ab" 跟 "ba" 雜湊值不同) 有興趣可以觀看以下文章 : String Hashing — CP-Algorithms，這邊就不細講了怕資訊量太大~ 雜湊表（Hash Table）是一種利用 雜湊函式（Hash Function） 來儲存資料的資料結構。 透過一個函式，將資料轉換成陣列中的索引位置（Index），再把資料存放到對應的位置，透過這種方式，我們可以快速找到資料的位置 假設今天有一個大小為 10 的陣列 索引：0 1 2 3 4 5 6 7 8 9 我們設計一個雜湊函式 hash(key) = key % 10 15 % 10 = 5 代表 15 要放到索引 5 因為很難設計一個近乎完美的雜湊，所以碰撞和溢位是不可免的 所以這邊來介紹幾種解決方法 鏈結串列法 (Chaining) 陣列的每個位置，不是直接存一個值，而是存一個鏈結串列。發生碰撞時，新資料就直接接到對應位置的鏈結串列後面 重新雜湊法(rehashing) 當雜湊表中的資料越來越多時，發生碰撞(Collision)的機率也會增加，這時候可以建立一個更大的雜湊表，將原本的資料重新計算位置、重新放入新的表格。 例如原本的表格大小是 10，資料增加後建立更大的表格 : 30 所以原本的 h(k) = k % 10 會變成：h(k) = k % 30，因此原本的資料需要重新計算位置 #include <unordered_map> unordered_map<string, int> map; 兩個 int 分別為(key)鍵值 和 (value) 如果key 為字串 unordered_map<string, int> score; score["Amy"] = 90; score["Bob"] = 85; score["Nina"] = 95; 複習 給定一個整數陣列 nums，以及一個整數 target，請找出陣列中兩個數字，使它們的和等於 target，並回傳這兩個數字的索引（index）。 我們之前已經寫過O(n²)解法 這次要把他優化到 O(n) class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> map; for(int i = 0; i < nums.size(); i++){ int pos = target - nums[i]; if(map.find(pos) != map.end()){ return {map[pos], i}; } map[nums[i]] = i; } return {}; } }; 參考資料和書籍