哈希表

習題預習

1. 什么是Hash Table，它是如何工作的？
2. 如何在Hash Table中查找特定值？
3. 如何在Hash Table中插入一项新的键-值对？
4. 如何从Hash Table中删除某个键-值对？
5. 如何解决Hash Table中的哈希冲突（Hash Collision）问题？

說明知識

哈希表（Hash Table）也被稱為哈希映射（Hash Map），是一種用於實現關聯數組或映射的數據結構。哈希表通過將關鍵字映射到表中的位置來加快查詢速度。這個映射函數被稱為哈希函數（Hash Function），它將關鍵字轉換為數組的索引位置。

哈希表的主要優點是其查找、插入和刪除的操作時間複雜度都是常數級別的。但是，哈希表的具體實現方式會影響到其效率和可靠性。例如，哈希函數的選擇、解決哈希碰撞的方法等等都是需要考慮的因素。

示例：

假設現在有一個需要查找學生信息的系統，每個學生有一個唯一的ID。我們需要設計一個數據結構來保存學生信息。

一種設計方案是使用哈希表，將學生ID作為關鍵字，將學生的姓名、出生日期、成績等信息映射到數組中的對應位置。

例如，如果學生ID為1234，根據哈希函數計算出該學生的位置是數組中的第6個元素，我們可以將該學生的姓名、出生日期、成績等信息保存在數組中的第6個位置上。這樣，當我們需要查找某個學生的信息時，只需要根據他的ID計算出他在數組中的位置，就可以快速地找到他的信息。

這個示例展示了哈希表的一個應用，但是實際的哈希表實現還需要考慮更多的因素，例如如何處理哈希碰撞、如何選擇適合的哈希函數等等。

彙總重點

1. Hash Table是一种数据结构，用于快速查找和访问数据。
2. Hash Table的基本原理是将数据存储在数组中，通过哈希函数将数据的键映射为数组索引。
3. 哈希函数需要满足两个特点：唯一性和均匀性，保证索引的分布均匀而且不发生冲突。
4. 在Hash Table中，对于每一个键值对，通过哈希函数得到的索引值即为该键值对在数组中的存储位置。
5. Hash Table的查找性能很高，可以实现常数级别的查找时间复杂度，但在处理大量冲突时性能会有所下降。
6. 冲突处理方法包括链式法和开放地址法，前者是将冲突的元素存储在同一索引下的链表中，而后者是通过探测找到其他索引来存储冲突元素。
7. Hash Table除了查找功能，还可以实现插入、删除等操作，因此被广泛用于算法设计和软件开发中。

知識測驗

1. 題目：找到重複的數字
   有一個整數陣列，其中包含n個整數。所有的整數都是介於1和n之間（包括1和n）。 現在有些數字出現了兩次，有些數字出現了一次。 找出所有重複出現的數字。 最好時間效率為O（n），空間效率為O（1）。
   答案： https://www.geeksforgeeks.org/find-duplicates-in-on-time-and-constant-extra-space/

2. 題目：聚集相同字母的單詞
   給定一個包含n個單詞的字符串陣列，將所有包含相同字母的單詞分組。
   答案： https://www.geeksforgeeks.org/given-a-sequence-of-words-print-all-anagrams-together/

3. 題目：使用哈希表找到兩個數
   給定一個整數陣列和一個目標數字，判斷數組是否包含兩個數字（不一定相鄰），這兩個數字的和為目標數字。 如果有至少一組這樣的數對，則返回true；否則返回false。
   答案： https://www.geeksforgeeks.org/given-an-array-a-and-a-number-x-check-for-pair-in-a-with-sum-as-x/

4. 題目：計算總和相等的子陣列
   給定一個整數陣列，找到該陣列中所有總和相等的子陣列。
   答案： https://www.geeksforgeeks.org/find-if-there-is-a-subarray-with-0-sum/

5. 題目：聚集相同字母的字符串
   給定一個包含n個字符串的陣列，將它們分組並聚集所有包含相同字母的字符串。
   答案： https://www.geeksforgeeks.org/given-a-sequence-of-words-print-all-anagrams-together/