雜湊表面試題實戰#
雜湊表（Map/Set）是面試中最常用的資料結構之一，核心優勢是 O(1) 的查找效率。本節介紹三道經典面試題。
解題套路：遇到「查找」或「計數」問題，優先考慮使用雜湊表。
有效的字母異位詞 ↗#
題目#
判斷兩個字串是否為異位詞（Anagram）—— 字母相同、數量相同、順序可不同。
輸入：s = "anagram", t = "nagaram"
輸出：true排序法#
將兩個字串排序後比較。
fun isAnagram(s: String, t: String): Boolean {
return s.toCharArray().sorted() == t.toCharArray().sorted()
}- 時間複雜度：
O(n log n) - 空間複雜度：
O(n)
雜湊計數法#
統計每個字母出現的次數並比較。
fun isAnagram(s: String, t: String): Boolean {
if (s.length != t.length) return false
val count = HashMap<Char, Int>()
for (c in s) {
count[c] = count.getOrDefault(c, 0) + 1
}
for (c in t) {
val updated = count.getOrDefault(c, 0) - 1
count[c] = updated
if (updated < 0) return false
}
return true
}- 時間複雜度：
O(n) - 空間複雜度：
O(1)（最多 26 個字母）
陣列最佳化#
當字元集固定（如只有小寫字母）時，用陣列代替雜湊表。
陣列最佳化程式碼
fun isAnagram(s: String, t: String): Boolean {
if (s.length != t.length) return false
val count = IntArray(26)
for (c in s) {
count[c - 'a']++ // Char 相減得到 Int 位移
}
for (c in t) {
count[c - 'a']--
if (count[c - 'a'] < 0) return false
}
return true
}若題目未限制字元集（如包含 Unicode），應使用雜湊表而非固定大小陣列。
兩數之和 Two Sum ↗#
題目#
找出陣列中和為 target 的兩個數的下標。
輸入：nums = [2, 7, 11, 15], target = 9
輸出：[0, 1] // 因為 nums[0] + nums[1] = 9暴力法#
兩層迴圈枚舉所有組合。
- 時間複雜度：
O(n²) - 空間複雜度：
O(1)
雜湊表#
核心轉換：x + y = target ➡️ y = target - x
走訪時，查詢 target - x 是否已存在於雜湊表中。
fun twoSum(nums: IntArray, target: Int): IntArray {
val seen = HashMap<Int, Int>() // value -> index
for (i in nums.indices) {
val complement = target - nums[i]
if (complement in seen) {
return intArrayOf(seen[complement]!!, i)
}
seen[nums[i]] = i
}
return intArrayOf()
}- 時間複雜度：
O(n) - 空間複雜度：
O(n)
為何用 Map 而非 Set？
題目要求返回下標，Set 只能判斷存在性，無法記錄下標。
三數之和 Three Sum ↗#
題目#
找出陣列中所有和為 0 的不重複三元組。
輸入：nums = [-1, 0, 1, 2, -1, -4]
輸出：[[-1, -1, 2], [-1, 0, 1]]暴力法#
三層迴圈，時間複雜度 O(n³)。
雜湊表#
固定 a、b，查找 -(a+b) 是否存在。
- 時間複雜度：
O(n²) - 空間複雜度：
O(n)
排序 + 雙指標（推薦）#
- 先排序
- 固定第一個數 a
- 用雙指標在剩餘區間找 b + c = -a
雙指標解法程式碼
fun threeSum(nums: IntArray): List<List<Int>> {
nums.sort()
val result = mutableListOf<List<Int>>()
val n = nums.size
for (i in 0 until n - 2) {
// 剪枝：最小值 > 0，不可能有解
if (nums[i] > 0) break
// 去重：跳過重複的 a
if (i > 0 && nums[i] == nums[i - 1]) continue
var left = i + 1
var right = n - 1
while (left < right) {
val total = nums[i] + nums[left] + nums[right]
when {
total < 0 -> left++
total > 0 -> right--
else -> {
result.add(listOf(nums[i], nums[left], nums[right]))
// 去重：跳過重複的 b 和 c
while (left < right && nums[left] == nums[left + 1]) left++
while (left < right && nums[right] == nums[right - 1]) right--
left++
right--
}
}
}
}
return result
}- 時間複雜度：
O(n²) - 空間複雜度：
O(1)（不計輸出）
去重是關鍵！
- 外層去重：
nums[i] == nums[i-1]時跳過- 內層去重：找到解後，跳過重複的 left 和 right
解題模式總結#
| 題型 | 關鍵技巧 | 時間複雜度 |
|---|---|---|
| 計數/頻率 | 雜湊表計數 | O(n) |
| 兩數之和 | 雜湊表查找補數 | O(n) |
| 三數之和 | 排序 + 雙指標 | O(n²) |
| 四數之和 | 固定兩數 + 雙指標 | O(n³) |
通用最佳化思路：
- 暴力
O(nᵏ)➡️ 雜湊表最佳化為O(nᵏ⁻¹)- 有序資料 ➡️ 雙指標替代內層迴圈
倒排索引 (Inverted Index)：搜尋引擎的核心#
雜湊表不只用在小題目，它也是整個搜尋引擎的地基。
一般人的直覺是「文件 ➡️ 它含哪些詞」，例如「第 3 篇文章包含 java、hash、index」。但要支援「使用者輸入一個詞，秒回所有相關文章」，這個方向完全幫不上忙——你得把每篇文章都掃一遍。
倒排索引把這個關係反轉過來：記錄「詞 ➡️ 含這個詞的文件清單」。這份文件清單通常稱為 posting list。本質上，它就是一個 Map<詞, List<文件>>。
| 方向 | 結構 | 查詢「哪些文件含 java」 |
|---|---|---|
| 正向 | 文件 ➡️ 詞 | 掃過每篇文章，O(文件總長) |
| 倒排 | 詞 ➡️ 文件 | 雜湊表直接取出 posting list，O(1) |
查詢時，直接用詞當 key 取出候選文件清單，完全不必掃描每一篇文章。
多關鍵字查詢就是「取交集」。
查「java AND hash」時，分別取出
java與hash兩條 posting list，對它們求交集，剩下的文件就是同時含兩個詞的結果。
建索引 + 查詢範例#
class InvertedIndex {
// 詞 -> 含這個詞的文件 id 集合
private val index = HashMap<String, MutableSet<Int>>()
// 把一篇文件加入索引
fun add(docId: Int, content: String) {
for (word in content.split(Regex("\\s+"))) {
index.getOrPut(word) { mutableSetOf() }.add(docId)
}
}
// 單一關鍵字查詢：O(1) 取出 posting list
fun search(word: String): Set<Int> = index[word] ?: emptySet()
// 多關鍵字 (AND) 查詢：對多條 posting list 取交集
fun searchAll(vararg words: String): Set<Int> {
var result: MutableSet<Int>? = null
for (word in words) {
val postings = search(word)
if (result == null) {
result = postings.toMutableSet()
} else {
result.retainAll(postings) // 交集
}
}
return result ?: emptySet()
}
}進階：在 posting list 裡再存「位置」
實務上的 posting list 不只記錄「哪些文件含這個詞」，還會記錄「這個詞在文件中出現的每一個位置」，例如 java -> {doc3: [5, 18, 42]}。
有了位置資訊，就能直接靠比對位置完成更難的查詢，而不必回去重讀原文：
- 片語查詢（要求「machine learning」相鄰）：檢查兩個詞的位置是否相差 1。
- 鄰近查詢（NEAR，要求兩詞距離在 k 以內）：檢查位置差是否 ≤ k。
這是「用空間換查詢能力」的經典範例——多存一份位置資料，換來原本要掃全文才能做到的查詢。
相似度與 SimHash：從「完全相同」到「幾乎相同」#
一般的雜湊函式有個刻意設計的特性：輸入只要差一個字元，輸出指紋就天差地別。這讓它非常適合判斷「是否完全相同」，卻完全無法回答「這兩篇文章有多像」。
SimHash 是一種「局部敏感雜湊 (Locality-Sensitive Hashing)」：內容相近的文件，算出來的 SimHash 值也會相近，往往只差一兩個位元。
| 特性 | 一般雜湊 | SimHash |
|---|---|---|
| 設計目標 | 差一點就完全不同 | 差一點就只差一點 |
| 能回答 | 是否完全相同 | 有多相似 |
| 衡量方式 | 相等／不相等 | 漢明距離 |
判斷兩篇文件相似度，只要算它們 SimHash 的漢明距離（不同位元的數量）：距離越小越相似。
典型應用：
- 網頁去重——爬蟲抓回海量網頁，用 SimHash 快速濾掉內容幾乎一樣的重複頁。
- 抄襲／相似內容偵測——找出「換了幾個字但骨架相同」的文章。
漢明距離的計算正是位元運算的拿手好戲：把兩個值 XOR 之後，數結果裡有幾個 1，就是漢明距離。
// 兩個 SimHash 指紋的漢明距離 = XOR 後 1 的個數（用 64-bit Long 存指紋）
fun hammingDistance(a: Long, b: Long): Int =
java.lang.Long.bitCount(a xor b)詳見 位元運算。
齊普夫定律 (Zipf’s Law)：為什麼很多統計分佈極度傾斜#
在自然語言裡有個反覆出現的現象：少數高頻詞（的、是、in、the）佔據了絕大多數的出現次數，而絕大多數的詞只出現一兩次。把詞按出現頻率排序，頻率大致與排名成反比——這就是齊普夫定律。
這種「少數項極大、大量項極小」的長尾分佈，並不只出現在語言：城市人口、網站流量、商品銷量都有類似的傾斜形狀。
對資料結構選型的啟示。
像「詞與詞的同現次數」這種統計，理論上是一張 N×N 的大表，但因為長尾分佈，絕大多數格子都是 0。
- 硬用二維大陣列存：空間幾乎全浪費在零上。
- 改用雜湊表只記非零項（key 是「詞對」，value 是次數）：空間只跟真正出現過的組合成正比。
- 若連雜湊表都裝不下，再考慮分治，把資料切塊分別統計後合併。
看清資料的分佈形狀，往往比硬背資料結構更能選對工具。