哈希100个10亿范围内的不同值

Question

我最近在一次采访中被问到这个问题。我有一个由n个元素组成的数组。该数组只有100个不同的值。我需要打印每个数字的出现次数。

 1<=n<=10^6
 1<=A[i]<=10^12

预期的空间复杂度为O（k），其中k是数组中不同值的数目。

例如，1 2 3 2 1 4 3 2 4 2 3 1 2；这里CCD_ 3是CCD_。首先，我建议在stl中使用map，但他希望他实现我自己的数据结构。然后我建议像在二进制搜索树中一样，对每个元素使用排序插入，但这会给出O（nlogn）的时间复杂度。他想要一个O（n）解。我试着想出任何散列函数，但我无法想出任何这样的函数。我也试着考虑trie数据结构，但我必须再次扫描每个数字的每个数字，从而再次给出O（nlogn）复杂性。解决这个问题的可能方法是什么？

Answer 1

哈希表不能保证O（n*k）的理论复杂度。但制作这样一个很容易。

首先，我们需要对值的概率分布做出一些假设——让它是均匀的（否则我们需要一些专门的哈希函数）。

接下来，让我们选择哈希表大小，比如说201个条目（因此它将小于50%满）。

接下来，让hash函数只是hash(A[i]) = A[i] mod 201。

然后使用具有201个条目对的开放寻址哈希表H[]：A[i]或NULL；频率值。

Answer 2

我认为哈希表是一个很好的解决方案，但我想面试官希望你建立自己的哈希表。

以下是我在Python中提出的一个解决方案。我使用mod 100作为哈希函数，并使用分离链接来处理冲突。

import random
N = random.randint(1, 10**6)
K = 100
HASH_TABLE_SIZE = 100
distinct = [random.randint(1, 10**12) for _ in range(K)]
numbers = [random.choice(distinct) for _ in range(N)]
hash_table = [[] for _ in range(HASH_TABLE_SIZE)]
def hash(n):
    hash_key = n % HASH_TABLE_SIZE
    bucket = hash_table[hash_key]
    for value in bucket:
        if value[0] == n:
            value[1] += 1
            return
    bucket.append([n, 1])
for number in numbers:
    hash(number)
for bucket in hash_table:
    for value in bucket:
        print('{}: {}'.format(*value))

编辑

稍微解释一下代码：

我的哈希表是一个100元素的数组。数组中的每个条目都是(number, count)条目的列表。为了散列一个数字，我取它的值取模100，在数组中找到一个索引。我扫描该存储桶中已经存在的数字，如果其中任何数字与当前数字匹配，我会递增其计数。如果我找不到数字，我会在列表中添加一个新条目，其中包含数字和初始计数1。

从视觉上看，数组看起来有点像：

[
  [ [0, 3], [34500, 1] ]
  [ [101, 1] ],
  [],
  [ [1502, 1] ],
  ...
]

请注意，在索引n处，存储在bucket中的每个值都等于n（mod 100）。平均而言，每个bucket只有一个值，因为数组中最多有100个不同的值和100个元素。

要打印出最终计数，只需要遍历数组和每个bucket中的每个条目并打印出来。

编辑2

这里有一个稍微不同的实现，它使用开放寻址和线性探测。我想我其实更喜欢这种方法。

hash_table = [None] * HASH_TABLE_SIZE
def hash(n):
    hash_key = n % HASH_TABLE_SIZE
    while hash_table[hash_key] is not None and hash_table[hash_key][0] != n:
        hash_key = (hash_key + 1) % HASH_TABLE_SIZE
    if hash_table[hash_key] is None:
        hash_table[hash_key] = [n, 1]
    else:
        hash_table[hash_key][1] += 1
for number in numbers:
    hash(number)
for entry in hash_table:
    print('{}: {}'.format(*entry))

注意：如果实际有超过100个不同的数字，则此代码将失败。（试图在数组中找到一个空位会一直挂着。）如果能不断检测到这种情况（例如，一旦你在数组中走了一整圈）并引发异常，那就太好了。

Answer 3

实际上，您错了，trie会给您带来O(N)的复杂性。

trie的一次插入/查找/擦除操作需要O(L)时间，其中L是推入该trie的字符串的长度。幸运的是，你只需插入不大于1万亿的数字，这意味着L不大于log(10^12)（对数基数取决于你在这个trie中使用的计数系统。我个人会根据这个结构在整个系统中的作用选择256或65536）。

综上所述，您将需要O(N) * O(log(10^12))，根据O()的定义，它等于O(N)。