資料結構 | Chris's Website

哈希表（Hash Table）：高效能的鍵值對數據結構

哈希表（Hash Table）哈希表是一種高效率的數據結構，能夠以接近 O(1) 的時間複雜度進行數據查找、插入和刪除操作。它廣泛應用於數據庫索引、快取系統、符號表等場景，是現代編程中最重要的數據結構之一。基本原理哈希表基於「鍵值對」（key-value pair）的概念，它使用一個特殊的函數（哈希函數）將鍵轉換為數組索引，然後將值存儲在該索引位置。核心組件哈希函數：將鍵轉換為數組索引的函數數組：存儲數據的物理結構衝突解決策略：處理不同鍵產生相同索引的情況哈希函數好的哈希函數應當滿足以下特性：計算速度快分布均勻，最小化衝突確定性，相同輸入產生相同輸出一個簡單的哈希函數示例（針對字符串）： int hash(char* key, int table_size) { unsigned int hash_value = 0; while (*key) { hash_value = (hash_value * 31) + *key++; } return hash_value % table_size; } 衝突解決當兩個不同的鍵產生相同的哈希值（稱為「衝突」）時，我們需要有策略來解決這個問題： 1. 鏈接法（Chaining）每個數組位置存儲一個鏈表，所有哈希到同一位置的元素都放入這個鏈表中。 [0] -> (key1, value1) -> (key4, value4) [1] -> (key2, value2) [2] -> (key3, value3) -> (key5, value5) -> (key6, value6) 2. 開放尋址法（Open Addressing）當發生衝突時，查找數組中的另一個位置來存儲元素。常見的方法有：線性探測：檢查下一個位置，再下一個，依此類推二次探測：使用二次函數計算探測序列雙重哈希：使用第二個哈希函數計算步長哈希表操作的時間複雜度操作平均情況最壞情況查找 O(1) O(n) 插入 O(1) O(n) 刪除 O(1) O(n) 最壞情況發生在所有鍵都哈希到同一位置時。 ...

雜湊表進階應用 - 解決複雜 LeetCode 問題

雜湊表進階應用在上一篇文章中，我們介紹了雜湊表的基本原理和常見應用。本文將進一步探討雜湊表的進階應用，幫助您解決更複雜的 LeetCode 問題。與其他資料結構結合使用雜湊表往往不是單獨使用，而是與其他資料結構結合，發揮更強大的功能。雜湊表 + 堆（Heap） LeetCode 347. Top K Frequent Elements 找出數組中出現頻率最高的 k 個元素。 def topKFrequent(nums, k): # 使用雜湊表計算頻率 counter = {} for num in nums: counter[num] = counter.get(num, 0) + 1 # 使用堆找出頻率最高的 k 個元素 import heapq return heapq.nlargest(k, counter.keys(), key=lambda x: counter[x]) 雜湊表 + 鏈結串列 LeetCode 146. LRU Cache 實現一個 LRU (Least Recently Used) 快取機制。 class DLinkedNode: def __init__(self, key=0, value=0): self.key = key self.value = value self.prev = None self.next = None class LRUCache: def __init__(self, capacity: int): self.cache = {} # 雜湊表：快速查找節點 self.size = 0 self.capacity = capacity self.head, self.tail = DLinkedNode(), DLinkedNode() # 虛擬頭尾節點 self.head.next = self.tail self.tail.prev = self.head def get(self, key: int) -> int: if key not in self.cache: return -1 node = self.cache[key] self._move_to_head(node) return node.value def put(self, key: int, value: int) -> None: if key not in self.cache: node = DLinkedNode(key, value) self.cache[key] = node self._add_to_head(node) self.size += 1 if self.size > self.capacity: removed = self._remove_tail() del self.cache[removed.key] self.size -= 1 else: node = self.cache[key] node.value = value self._move_to_head(node) def _add_to_head(self, node): node.prev = self.head node.next = self.head.next self.head.next.prev = node self.head.next = node def _remove_node(self, node): node.prev.next = node.next node.next.prev = node.prev def _move_to_head(self, node): self._remove_node(node) self._add_to_head(node) def _remove_tail(self): node = self.tail.prev self._remove_node(node) return node 多重雜湊表技巧巢狀雜湊表 LeetCode 49. Group Anagrams ...

鏈表（Linked List）：動態數據結構的基石