1、哈希表基礎知識

• 以鍵值對的方式進行數據存儲
• 優點：哈希表數據結構在插入、刪除或查找一個元素時，都只需要O(1)的時間

哈希表設計三要點：

• 為了快速確定一個元素在哈希表中的位置，可以使用一個數組，元素的位置為他的哈希值除于數組長度的余數。
• 由于多個哈希值不同的元素可能會被存入同一數組位置，數組的每個位置對應一個鏈表，因此存入同一位置的多個元素都被添加到同一個鏈表中。
• 為了確保鏈表不會太長，就需要計算哈希表中元素的數目與數組長度的比值。當這個比值超過某個閾值時，就對數組進行擴容處理，并把哈希表中的所有元素重新分配位置。

2、LCR 030. O(1) 時間插入、刪除和獲取隨機元素

題目信息：

• https://leetcode.cn/problems/FortPu/description/

設計一個支持在平均 時間復雜度 O(1) 下，執行以下操作的數據結構：insert(val)：當元素 val 不存在時返回 true ，并向集合中插入該項，否則返回 false 。
remove(val)：當元素 val 存在時返回 true ，并從集合中移除該項，否則返回 false 。
getRandom：隨機返回現有集合中的一項。每個元素應該有 相同的概率 被返回。示例 1：
輸入: inputs = ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
輸出: [null, true, false, true, 2, true, false, 2]
解釋:
RandomizedSet randomSet = new RandomizedSet();  // 初始化一個空的集合
randomSet.insert(1); // 向集合中插入 1 ， 返回 true 表示 1 被成功地插入
randomSet.remove(2); // 返回 false，表示集合中不存在 2
randomSet.insert(2); // 向集合中插入 2 返回 true ，集合現在包含 [1,2]
randomSet.getRandom(); // getRandom 應隨機返回 1 或 2
randomSet.remove(1); // 從集合中移除 1 返回 true 。集合現在包含 [2]
randomSet.insert(2); // 2 已在集合中，所以返回 false
randomSet.getRandom(); // 由于 2 是集合中唯一的數字，getRandom 總是返回 2提示：
-231 <= val <= 231 - 1
最多進行 2 * 105 次 insert ， remove 和 getRandom 方法調用
當調用 getRandom 方法時，集合中至少有一個元素

解題思路：

• 1、審題：實現時間復雜度O(1)的哈希表，包含操作插入，刪除，和隨機獲取內部數據
• 2、解題：該題要實現哈希表的功能，主要要求是時間復雜度為O(1)
• 插入操作：
  • 使用動態數組vector保存插入后的數據，這樣可以隨機訪問數組內的元素
• 刪除操作：
  • 要實現數據的刪除，需要先知道該數值在數組內的下標位置，可以使用map數據結構保存，key為數值，value為該數值在數組中的下標位置
  • 這樣就可以通過數值獲取到對應保存的下標位置，
  • 還有一個問題是數組中元素刪除，需要將后面部分元素進行整體移動，時間復雜度為O(n)
  • 要實現數組元素刪除時間復雜度為O(1),可將當前需要刪除的元素與數組尾部元素進行交換，然后直接刪除數組尾部的元素
• 隨機獲取操作：
  • 使用random隨機獲取數組內的某一個元素

代碼實現：

class RandomizedSet
{
public:RandomizedSet(){}bool insert(int val){if (arrLocationMap.find(val) != arrLocationMap.end()) // 已經包含了{return false;}// 加入到數組和哈希表中arrLocationMap[val] = array.size();array.push_back(val);return true;}bool remove(int val){// 先判斷數組中是否包含該數值if (arrLocationMap.find(val) == arrLocationMap.end()) // 不包含{return false;}// print();// 找到要刪除原始的下標位置int removeIndex = arrLocationMap[val];// 與數組最后元素交換int size = array.size();int removeVal = array[removeIndex];int tailVal = array[size - 1];arrLocationMap[tailVal] = removeIndex;array[removeIndex] = tailVal;array[size - 1] = removeVal;// 刪除數組最后一個元素array.pop_back();arrLocationMap.erase(val);return true;}/** Get a random element from the set. */int getRandom(){// 使用mt引擎std::mt19937 generate(rd());// 創建分布std::uniform_int_distribution<int> dist(0, array.size() - 1);int index = dist(generate);return array[index];}private:std::vector<int> array;std::map<int, int> arrLocationMap; // 保存數組元素，和對應的數組下標std::random_device rd;             // 初始化隨機數生成數
};

3、總結

• 普通的map哈希表結構為數組與鏈表組合，插入與獲取數據操作，需要遍歷鏈表，時間復雜度為O(n)
• 要設計O（1）時間復雜度的哈希表，可使用數組進行插入與獲取數據，時間復雜度為O(1),因為數組可通過下標索引操作
• 而數組的刪除操作，可利用交換處理，轉變為最終刪除數組尾部元素，只是要知道刪元素的位置所在，所以需要一個map值保存每個元素在數組中的下標位置。
• map操作方法，find為查詢元素是否存在，erase為刪除元素操作。