求一个hash函数:输入n个非负整数k_1、k_2、...、k_n,随机输出集合{0、1、2、...、m}中的一个非负整数。要求n可配置、m可配置,随机性尽量高、复杂度尽量低
时间: 2023-07-10 21:11:31 浏览: 118
一个简单的hash函数实现是取各个输入数的模,然后将它们相加取模得到结果。具体实现如下:
```python
def hash_func(nums, m):
result = 0
for num in nums:
result = (result + num) % m
return result
```
其中,`nums`是输入的非负整数数组,`m`是输出的集合大小。这个hash函数的复杂度为O(n),随机性较高,可以满足要求。
如果要进一步提高随机性,可以使用哈希表来实现,具体实现如下:
```python
import random
class HashTable:
def __init__(self, m):
self.m = m
self.table = [[] for _ in range(m)]
def hash_func(self, key):
return sum(key) % self.m
def insert(self, key):
idx = self.hash_func(key)
self.table[idx].append(key)
def search(self, key):
idx = self.hash_func(key)
return key in self.table[idx]
def random_hash(nums, m):
table = HashTable(m)
for num in nums:
table.insert([num, random.random()])
return table.hash_func(nums)
```
这个hash函数在插入时随机生成一个小数并与`num`一起插入哈希表中,查询时只需要判断是否存在即可。这个hash函数的随机性更高,但复杂度相对较高,为O(n)。
阅读全文