这是一个哈希函数吗？Python

Question

我正在尝试在Python中实现一个哈希函数。你认为以下函数是真正的哈希函数吗？我有10个桶和值从1到7。它还会计算碰撞次数 :)

import random

A=[1,2,3,4,5,6,7]
hashed=[]

def func():
     i=0
     count=0
     while len(A)>i:
          m=random.randint(1,10) # 10 buckets
          if m in hashed:
             count+=1
          hashed.append(m)
          print "element:",A[i], "hashed to bucket", m
          i+=1


     print "Amount of collisions:", count  


func()

测试：

element: 1 hashed to bucket 3
element: 2 hashed to bucket 2
element: 3 hashed to bucket 10
element: 4 hashed to bucket 8
element: 5 hashed to bucket 3
element: 6 hashed to bucket 10
element: 7 hashed to bucket 4
Amount of collisions: 2

编辑：

我查看了所有的评论并尝试创建另一个哈希函数。这次我使用随机数来确定要进行哈希的键。这次我只有3个桶。我将尝试使用25个值，这些值介于1和10之间：

import random


count=[]

list1 = []  # bucket 1
list2 = []  # bucket 2
list3 = []   # bucket 3

the_list = []
the_list.append(list1)
the_list.append(list2)
the_list.append(list3) # using lists within a list


def func():
   while True:
       number=random.randint(1,10)
       i=random.randint(0,len(the_list)-1)
       the_list[i].append(number)
       count.append(number)
       if len(count)>25: # testing for 25 values
           break

func()
print "Bucket 1:", the_list[0]
print "Bucket 2:", the_list[1]
print "Bucket 3:", the_list[2]

测试：

Bucket 1: [5, 9, 8, 10, 3, 10]
Bucket 2: [10, 5, 8, 5, 6, 2, 6, 1, 8]
Bucket 3: [9, 4, 7, 2, 1, 6, 7, 10, 9, 1, 5]

- John

---

当需要检索元素时，您如何确定它去了哪里？您引入了随机性，下一次您使用“1”时，它可能会返回“桶10”，但糟糕的是...它实际上在桶3中。 - Marc B

@John：你的测试输出不可能来自你发布的代码。count是func()的局部变量，并且你在运行func之前就打印了碰撞计数。在这里很容易看出可能发生了什么，但通常请确保您发布的示例是自包含的，可以在其自身上运行并生成输出。 - DSM

是的，我忘记为最后一个打印创建空间了，在我的程序中，打印语句在函数内部。不过感谢您提供的信息。 - John

通常情况下，在Python中你不需要实现哈希函数，因为你通常不需要自己做哈希函数的事情。特别是，你不需要创建哈希容器，因为Python内置了两个：dict（关联映射）和set（具有唯一性约束的集合）。 - Karl Knechtel

Answer 1

编号。哈希函数必须是确定性的。它不能依赖于随机性。

哈希过程必须是确定性的，这意味着对于给定的输入值，它必须始终生成相同的哈希值。换句话说，在数学意义上，它必须是散列数据的函数。此要求排除了依赖于外部变量参数（如伪随机数生成器或当天时间）的哈希函数。它还排除了依赖于被哈希对象的内存地址的函数，因为该地址可能会在执行期间更改（在使用某些垃圾收集方法的系统上可能会发生这种情况），尽管有时可以重新计算项目的哈希值。

来源：哈希函数-确定性（维基百科）

- Dennis

---

谢谢。我被误导了，你有关于如何在Python中创建简单哈希函数的建议吗？ - John

这是一个简单的哈希函数，用于将整数进行哈希：f(x)：返回 x % 10 - Chris Lacasse

@John：你修改后的示例随机填充了一些整数数组。没有任何输入可以被散列。你需要哈希函数做什么？ - Dennis

Answer 2

不，这不是一个哈希函数。哈希函数给定一个输入应该会一遍又一遍地给出相同的输出。

与其构建自己的哈希函数，为什么不直接使用Python自带的hash功能呢？Python内置了哈希实现。

>>> hash("xyz")
-5999452984703080694

所以，不要使用 list，而是使用带有 hash 的 dict，其中键是此哈希输出。碰撞可以轻松检测。

- Srikar Appalaraju

Answer 3

一个哈希函数需要为相同的输入提供相同的输出……而你的函数只是给出一个随机数。所以，我不认为它是一个真正的哈希函数。

- Claudiu

Answer 4

不，你根本没有进行哈希操作，只是随机地将值插入到数组中。哈希函数接受一个输入并返回一个确定性的值。这个返回值就是哈希值。

- Peter Rowell

Answer 5

不，这不是一个哈希函数。哈希函数将大数据集中的元素映射到较小的数据集中。这只是将数字随机插入到列表中。

- Chris Lacasse