数据结构与算法之哈希表

哈希表实际上是从属于 Dictionary 这个抽象数据结构 (ADT) 下的，本文从抽象数据结构 Dictionary 入手，逐步介绍 C++ 中多个从属于 Dictionary 的数据类型。

Dictionary ADT

Dictionary ADT (Abstract Data Type) 是一个使用非常广泛的抽象数据类型；

Dictionary 允许通过 Key 来访问存储的对应的 Value;

Dictionary 主要支持的操作如下：

  • Search(Dict, Key) —— 给定一个 Key，获取对应的 Value。
  • Insert(Dict, Key, Value) —— 给定一个 Value，将该 Value 以 Key 存储。
  • Delete(Dict, Key) —— 给定一个 Key, 删除对应的 Value。

某些 Dictionary 还支持有序遍历、最大最小值、前驱后继等更多操作。

数组

数组可以看做一种 Dictionary 的实现：

使用数组作为 Dictionary 时，

将数组的下标作为 Key，因此 Key 的范围只能是非负整数。

数组的元素不能删除，因此需要从 Value 的值域中选定一个值来表示该 Value 被删除的状态。

  • Search(Dict, Key), O(1)

    时间复杂度：O(1)

int dict[10] = {0};
int n = dict[1]

  • Insert(Dict, Key, Value), O(1)

    时间复杂度：O(1)

dict[1] = 7;

  • Delete(Dict, Key), O(1)

    时间复杂度：O(1)

// 选择 0 表示该 Key 已删除
dict[1] = 0;

std::unordered_map

std::unordered_map 也是一种 Dictionary 的实现，内部采用哈希表。

  • Search(Dict, Key), O(1)

    时间复杂度：Average case: O(1), worst case: O(n)

std::unordered_map<std::string, int> dict;
auto i = dict["Key"];

  • Insert(Dict, Key, Value),

    时间复杂度：Average case: O(1), worst case O(n)

dict["Key"] = 2;
dict.insert({"Key", 2});

  • Delete(Dict, Key) , O(1)

    时间复杂度：Average case: O(1), worst case: O(n)

dict.erase("Key");

std::map

std::unordered_map 也是一种 Dictionary 的实现，内部采用红黑树。

  • Search(Dict, Key), O(1)

    时间复杂度：O(log(n))

std::map<std::string, int> dict;
auto i = dict["Key"];

  • Insert(Dict, Key, Value),

    时间复杂度：O(log(n))

dict["Key"] = 2;
dict.insert({"Key", 2});

  • Delete(Dict, Key) , O(1)

    时间复杂度：Amortized O(1)

dict.erase("Key");

除此之外 std::map 还支持：

  • 有序遍历：

    begin())

    end()

    int main() {
  std::map<int, float> num_map;
  num_map[4] = 4.13;
  num_map[9] = 9.24;
  num_map[1] = 1.09;
  // calls a_map.begin() and a_map.end()
  for (auto it = num_map.begin(); it != num_map.end(); ++it) {
    std::cout << it->first << ", " << it->second << '\n';
  }
}
  
/*
Output:
1, 1.09
4, 4.13
9, 9.24
*/

  • 按值区间查找：

    equal_range()

    lower_bound()

    upper_bound()

Dictionary 数据类型选择策略

从数组、std::unordered_map 到 std::map ，它们支持的操作变多，但时间复杂度依次增加，因此应尽量选择最小满足要求的数据类型；

若需求中 Key 的值的范围为非负整数，则考虑选择数组。

若除了常规 Dictionary 操作外还需要对结果排序，则考虑选择 std::map。

其余情况则考虑选择 std::unordered_map。

题示例

题目

森林中，每个兔子都有颜色。其中一些兔子（可能是全部）告诉你还有多少其他的兔子和自己有相同的颜色。我们将这些回答放在 answers 数组里。

返回森林中兔子的最少数量。

示例:
输入: answers = [1, 1, 2]
输出: 5
解释:
两只回答了 "1" 的兔子可能有相同的颜色，设为红色。
之后回答了 "2" 的兔子不会是红色，否则他们的回答会相互矛盾。
设回答了 "2" 的兔子为蓝色。
此外，森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。
因此森林中兔子的最少数量是 5: 3 只回答的和 2 只没有回答的。

输入: answers = [10, 10, 10]
输出: 11

输入: answers = []
输出: 0

说明:
answers 的长度最大为1000。
answers[i] 是在 [0, 999] 范围内的整数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rabbits-in-forest
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

从兔子回答的 answers 中依次拿出一个数字 n，从 n 可以推导出该颜色的兔子的数量总共有 n + 1 个，因为是求“森林中兔子的最少数量”，所以之后凡是遇到回答中的数字 n，都认定属于同一颜色，在遍历 answers 的过程中，还需要对每个回答 n 的兔子计数，如果超过 n，则要重新认定另一个组数量同样为 n 但颜色不同的兔子。

在上述算法过程中，需要记录每个 n 及其对应的兔子数量计数，即一个 Key Value Pair，因此自然地需要用到 Dictionary 数据类型，并且由于算法中需要存储的 Key 为非负整数，Value 最大值为 999，因此适合使用整型数组。

例如 answers = [1, 1, 1, 2] 的情况，拿到第一个 1 时，说明这个颜色兔子总共有 2 只目前遇到 1 只，记录 dict[2] = 1，遇到第二个 1，dict[2]–, dict[2] == 0, dict.erase[2]，该颜色兔子统计完毕，遇到第三个 1 ，说明还有一组数量同样是 2 但颜色不同的兔子，记录 dict[2] = 1，最后遇到 2，记录 dict[3] = 2，统计建立过的兔子组的数量 2 + 2 + 3 = 7，即总共最少有 7 只兔子。

代码

class Solution {
public:
    int numRabbits(vector<int>& answers) {
        if (answers.empty()) {
            return 0;
        }

        int total_num_of_rabbits = 0;
        int dict[1001] = {0};
        int rabbits_in_this_color = 0;

        for (const auto& answer : answers) {
            if (answer == 0) {
                total_num_of_rabbits++;
                continue;
            }

            rabbits_in_this_color = answer + 1;
            if (dict[rabbits_in_this_color] == 0) {
                dict[rabbits_in_this_color] = rabbits_in_this_color - 1;
                total_num_of_rabbits += rabbits_in_this_color;
                continue;
            }

            dict[rabbits_in_this_color]--;
        }

        return total_num_of_rabbits;
    }
};

// leetcode 执行结果：
// 执行用时：4 ms, 在所有 C++ 提交中击败了 98.68% 的用户
// 内存消耗：8.1 MB, 在所有 C++ 提交中击败了 100.00% 的用户