Chinaunix首页 | 论坛 | 博客
  • 博客访问: 957945
  • 博文数量: 33
  • 博客积分: 803
  • 博客等级: 军士长
  • 技术积分: 1755
  • 用 户 组: 普通用户
  • 注册时间: 2010-03-05 18:58
个人简介

《Python科学计算》的作者

文章分类

全部博文(33)

文章存档

2016年(1)

2014年(2)

2013年(3)

2012年(27)

分类: Python/Ruby

2012-02-21 19:54:18

Python的哈希值算法

在32位系统中,Python的哈希值算法可以用下面的程序表示:

def str_hash(s):
    if not s:
        return 0 # empty
    value = ord(s[0]) << 7
    for char in s:
        value = c_mul(1000003, value) ^ ord(char)
    value = value ^ len(s)
    if value == -1:
        value = -2
    return value

其中c_mul()是C语言的32位整数乘法,由于Python的整数乘法不会溢出,因此需要用下面的程序模拟C语言的32位乘法:

def c_mul(a, b):
    return eval(hex((long(a) * b) & 0xFFFFFFFFL)[:-1])

或者使用NumPy中的int32整数进行乘法运算:

import numpy as np
def c_mul(a, b):
    return int(np.int32(a) * np.int32(b))

让我们验证一下str_hash()的结果:

>>> hash("abcd"), str_hash("abcd")
(1540938112, 1540938112)
>>> hash("12345"), str_hash("12345")
(-274697348, -274697348)

可以看到str_hash()的结果和内置的hash()相同。

c_mul()的逆运算

为了计算哈希值相同的字符串,需要从某个指定的哈希值出发,做hash()的逆运算。逆运算中最困难的是c_mul()。即假设“r = c_mul(1000003, n)”,已知r,求n。换句话说就是找到一个n,使其满足下面的等式,其中k为整数:

n(r) * 1000003 = k * 0x100000000 + r

显然我们只需要找到r为1时对应的n(1),就可以通过r*n(1)计算出n(r)了。

用穷举法可以很快找到n(1):

>>> k = np.arange(1000003, dtype=np.int64)
>>> k *= 0x100000000
>>> k += 1
>>> k %= 1000003
>>> np.where(k==0)
(array([470729]),)
>>> (470729*0x100000000+1)%1000003
0L
>>> (470729*0x100000000+1)//1000003
2021759595L
>>>

注意需要使用64位整数,防止k*0x100000000运算溢出。找到k*0x100000000+1除以1000003的余数为0的k值。再把这个k值代入公式计算出n(1)为2021759595。即r = c_mul(1000003, n)的逆运算为n = c_mul(2021759595, r)。

除了使用穷举法,还可以用下面的程序计算:

def invert_mult(a, b):
    g1, g2 = 0, 1
    while a!=0:
        d, m = b//a, b%a
        g1 = g1 - d*g2
        a, b = m, a
        g1, g2 = g2, g1
    return g1

下面是invert_mult()的用法:

>>> invert_mult(1000003, 0x100000000)
2021759595L
迭代法的工作原理

为了理解这段迭代法的工作原理,我们用SymPy编写一个迭代程序:

from sympy import *
n, k = symbols("n,k", integer=True)
a = symbols("a", integer=True)
g1 = n
g2 = k

a = S(1000003)
b = S(0x100000000)

while a!=0:
    print "%s*(%s) == %s*(%s) + 1" % (a, g1, b, g2)
    d, m = b//a, b%a
    g1 = g1 - d*g2
    b = m
    a, b = b, a
    g1, g2 = g2, g1

程序的输出为:

1000003*(n) == 4294967296*(k) + 1
954414*(k) == 1000003*(-4294*k + n) + 1
45589*(-4294*k + n) == 954414*(4295*k - n) + 1
42634*(4295*k - n) == 45589*(-90194*k + 21*n) + 1
2955*(-90194*k + 21*n) == 42634*(94489*k - 22*n) + 1
1264*(94489*k - 22*n) == 2955*(-1413040*k + 329*n) + 1
427*(-1413040*k + 329*n) == 1264*(2920569*k - 680*n) + 1
410*(2920569*k - 680*n) == 427*(-7254178*k + 1689*n) + 1
17*(-7254178*k + 1689*n) == 410*(10174747*k - 2369*n) + 1
2*(10174747*k - 2369*n) == 17*(-251448106*k + 58545*n) + 1
1*(-251448106*k + 58545*n) == 2*(2021759595*k - 470729*n) + 1

其中为原始的公式(4294967296就是0x100000000),从可以推出,这是把4294967296分解为:d*1000003+m(其中d=4294,m=954414)的形式,然后整理得到的。接下来的算式都是将较大的乘数用“d*较小乘数+m”的形式表示,直到较小的乘数变为1。

对于,可以列出下面的两个方程:

a = 2021759595*k - 470729*n
-251448106*k + 58545*n = 2*a+1

解这个方程组得到:

k = 1000003*a + 470729
n = 4294967296*a + 2021759595

但将a=0代入上面的解中即可求出k和n。

搜索

让我们再回顾一下前面介绍的哈希值运算函数:

def str_hash(s):
    if not s:
        return 0 # empty
    value = ord(s[0]) << 7
    for char in s:
        value = c_mul(1000003, value) ^ ord(char)
    value = value ^ len(s)
    if value == -1:
        value = -2
    return value

假设要搜索的字符串由大小写字母和数字(CHARS)构成。我们要找到所有长度为8、哈希值为8的字符串。根据哈希值计算程序可知,如果最终得到的value为0,那么字符串的哈希值就为8。

我们从value=0往前逆推,即在中等号左侧的value为0,求出CHARS中的每一个字符char对应的value值,使得c_mul(1000003, value) ^ ord(char)为0。然后对于每个value值再重复上述操作。

由于每一个字符都有62种选择,因此这样的搜索很快就会产生组合爆炸。为了尽可能加快运算速度,减小搜索的深度,我们使用一个字典缓存所有长度为4的字符串的哈希值。

import string
import itertools

CHARS = string.ascii_letters + string.digits
PREV_N = 4

hash_dict = {}
for c in itertools.product(*(CHARS,)*PREV_N):
    s = "".join(c)
    hash_dict[hash(s)^PREV_N] = s

使用itertools.product()产生有CHARS中所4个字符的组合,调用hash()计算字符串的哈希值,注意需要与字符串的长度进行异或,得到每个字符串对应的value的值。这个字典非常大,大约需要占据1G的内存,如果读者的电脑内存不够用,请将PREV_N改为3,不过这样会极大降低搜索的速度。

下面是搜索的程序,我们用NumPy的乘法和异或运算加快计算速度。

results = []
CHARS_ORD = np.array([ord(c) for c in CHARS], np.int32)
magic_num = np.int32(2021759595)                        

def search_h(h, n, s):
    if n == PREV_N:
        if h in hash_dict:                            
            results.append(hash_dict[h] + s)
            if len(results) % 1000 == 0:
                print len(results)
        return
    h2_array = h ^ CHARS_ORD                            
    np.multiply(h2_array, magic_num, out=h2_array)    
    for i, h2 in enumerate(h2_array):
        search_h(h2, n-1, CHARS[i] + s)                

search_h(np.int32(0), 8, "")
print len(results)
print set(hash(s) for s in results)                    

将字符串中的字符转换成32为整数。是前面介绍的c_mul()逆运算的乘数。在search_h()中,s是当前已经完成逆运算的字符串,h为这个字符串对应的逆推的value值,n为距离目标长度的差。当只剩下PREV_N个字符没有运算时,可以直接从hash_dict中寻找。使用NumPy的异或操作符一次运算所有62字符与h的异或结果。c_mul()的逆运算。最后,对h2_array中的每个值递归调用serach_h(),进行下一次逆推运算。

在我的计算机上,只用了25秒的时间就找到了50972个哈希值为8的字符串,最后通过验证这些字符串的哈希值的确是都为8的。下面是results中的头10个字符串:

['GA8Mfaaa', 'e4R5Blaa', 'Y92RLlaa', 'sCvEytaa', 'ydDspvaa',
'ofLCCCaa', 'uemC0Daa', 'CbgFKKaa', 'd0XRbNaa', 'hUzU9Saa']
请读者使用本程序计算出的10000个字符串作为字典的键值,测试字典的存取速度有何变化。
阅读(7175) | 评论(1) | 转发(2) |
0

上一篇:没有了

下一篇:浮点数的精度

给主人留下些什么吧!~~

重返人生2012-02-24 07:00:24

额(⊙o⊙)…要是有图文配合说明就好了