散列100个不同的值，范围为10亿

3 回答

• 1

  哈希表不保证O（n * k）的理论复杂度 . 但制作这样的东西很容易 .

  首先，我们需要对值概率分布做一些假设 - 让它统一（或者我们需要一些专门的散列函数） .

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

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

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

  回复于 2024-05-14T07:17:27+08:00
• 1

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

  这里's a solution I came up with in Python. I' m使用 mod 100 作为我的哈希函数并使用Separate chaining来处理冲突 .

  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))
  

  EDIT

  稍微解释一下代码：

  我的哈希表是一个100个元素的数组 . 数组中的每个条目都是 (number, count) 条目的列表 . 要散列数字，我将其值取模100来查找数组的索引 . 我扫描那个桶中已有的数字，如果它们中的任何一个与当前数字匹配，我会增加它的计数 . 如果我没有找到该号码，我会在列表中添加一个新条目，其中包含数字和初始计数为1 .

  在视觉上，数组看起来像这样：

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

  注意，在索引n处，存储在桶中的每个值等于n（mod 100） . 平均而言，每个桶只有一个值，因为阵列中最多有100个不同的值和100个元素 .

  要打印出最终计数，所需要的只是遍历阵列和每个桶中的每个条目并将其打印出来 .

  EDIT 2

  这是一个稍微不同的实现，它使用Open addressing代替线性探测 . 我想我其实更喜欢这种方法 .

  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个不同的数字，则此代码将失败 . （它将永远挂起，试图在阵列中找到一个开放点 . ）保持检测到这种情况（例如，一旦你在阵列中走了整整一圈）并引发异常将会很好 .

  回复于 2024-05-14T07:17:27+08:00
• 1

  实际上，你错了，特里会给你复杂性 .

  trie的一次插入/查找/擦除操作需要 O(L) 时间，其中 L 是推入此trie的字符串的长度 . 幸运的是，您只需插入不超过1万亿的数字，这意味着 L 不大于 log(10^12) （对数基数取决于您在此系列中使用的计数系统 . 我个人会选择 256 或 65536 ，具体取决于整个系统的哪个部分这种结构是否有效） .

  总结一下， O() 的定义需要 O(N) * O(log(10^12)) 等于 O(N) .

  回复于 2024-05-14T07:17:27+08:00