【算法专题训练】19、哈希表

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为删除元素操作。