1

我正在尝试实现自定义散列方法（乘法方法）：

def h(k, M):
    y = hash(k)
    T = (math.sqrt(5)-1)/2
    return(int(M*((y*T) - int(y * T))))

它总是返回零。我对其进行了测试并(y*T)-> 返回浮点值（例如10,666666）。int(y * T)-> 返回整数值（例如10）。但如果我这样做(y*T) - int(y * T)，它总是会返回0.0。我的目标是调用类似的东西h('test', 10)并得到一个数字作为返回，但它总是返回0.0。为什么会这样？

4

2 回答 2

4

你是在 64 位系统上运行的吗？如果是这样，y将是一个 64 位整数，T大约为 0.6，因此，例如，

>>> import random
>>> y = random.randrange(2**64) # some 64-bit int
>>> y
17364376918466400468
>>> yt = y * 0.6
>>> yt
1.041862615107984e+19
>>> yt - int(yt)
0.0

浮点数只有 53 位精度，因此在将 64 位 int 转换为浮点数时，“小数点后”没有位的可能性很大。

在 32 位系统上，hash()返回 32 位整数，因此不会出现此问题。

如果这是问题所在，那么您可以尝试各种解决方法，例如添加：

y = abs(y)
y = (y >> 32) ^ (y & 0xffffffff)  # collapse to 32 bits
于 2013-10-29T21:41:35.863 回答
1

这个问题源于浮点数在计算机中的存储方式。

简而言之：它们被存储为有限数量的有效数字、一个基数和一个指数。然后计算机知道将有效数字按以指数为底的基数来缩放以获得该值。数据量是特定于机器的：对于 32 位机器，23 位用于有效数字，8 用于指数，1 用于底数，64 位机器将有 53 位用于 sig figs， 8 为指数，1 为底数。

然后通过添加/减去有效数字和指数之间的差异来完成加法和减法。

您正在生成非常大的整数，hash(k)并试图获取向下舍入int(y*T)和浮点数之间的差异y*T。当 Python 解释器尝试获取 afloat和 an之间的差异int时，它会将inta 转换为浮点数，以y*T存储一定数量的有效数字。当您尝试从两个高数量级数中获得低数量级差异时，就会出现问题，或者通常任何时候差异的数量级与所涉及的数字有很大差异。低位有效数字将在计算中丢失。

这是我为测试您的方法而编辑的版本。添加的参数c是一个常数，我怀疑它有助于规范化您的结果。

import math

def h(k,M,c):
    y = hash(k)
    print "hash = ", y
    T = (math.sqrt(5)-1)/(2*c)
    print "y*T = ", y*T
    print "int(y*T) = ", int(y*T)
    print "(y*T) - int(y * T) = ",(y*T) - int(y * T)
    print "M*((y*T) - int(y * T)) = ", M*((y*T) - int(y * T))
    return(int(M*((y*T) - int(y * T))))

print(h('test',2,c))

随着 c 的增加，实际上这两个数字的差异出现在越来越接近的数量级上，您开始看到 的值(y*T) - int(y * T)远离0。示例输出如下：

>>>h('test',2,10)
hash =  2314058222102390712
y*T =  1.43016663321e+17
int(y*T) =  143016663320543088
(y*T) - int(y * T) =  0.0
M*((y*T) - int(y * T)) =  0.0
h(test,2,10) =  0
>>>h('test',2,1000)
hash =  2314058222102390712
y*T =  1.43016663321e+15
int(y*T) =  1430166633205430
(y*T) - int(y * T) =  0.75
M*((y*T) - int(y * T)) =  1.5
h(test,2,1000) =  1

>>>h('test',2,10000000)
hash =  2314058222102390712
y*T =  1.43016663321e+11
int(y*T) =  143016663320
(y*T) - int(y * T) =  0.543090820312
M*((y*T) - int(y * T)) =  1.08618164062
h(test,2,10000000) =  1

>>>h('test',2,10000000000000)
hash =  2314058222102390712
y*T =  143016.663321
int(y*T) =  143016
(y*T) - int(y * T) =  0.66332054307
M*((y*T) - int(y * T)) =  1.32664108614
h(test,2,10000000000000) =  1

作为我正在谈论的现象的一个附加示例：

y = hash('test')
print y
y = float(y)
print y
y = int(y)
print y

输出：

2314058222102390712
2.3140582221e+18
2314058222102390784

仅仅通过简单地切换到浮点数并返回到整数，最后两位数字不再可靠，因此可以看出低于此值的任何内容也会丢失。

于 2013-10-29T22:04:34.410 回答