在32位系统中，Python的哈希值算法可以用下面的程序表示：
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位乘法：
return eval(hex((long(a) * b) & 0xFFFFFFFFL)[:-1])
或者使用NumPy中的int32整数进行乘法运算：
def c_mul(a, b):
return int(np.int32(a) * np.int32(b))
让我们验证一下str_hash()的结果：
(1540938112, 1540938112)
>>> hash("12345"), str_hash("12345")
(-274697348, -274697348)
可以看到str_hash()的结果和内置的hash()相同。
为了计算哈希值相同的字符串，需要从某个指定的哈希值出发，做hash()的逆运算。逆运算中最困难的是c_mul()。即假设“r = c_mul(1000003, n)”，已知r，求n。换句话说就是找到一个n，使其满足下面的等式，其中k为整数：
显然我们只需要找到r为1时对应的n(1)，就可以通过r*n(1)计算出n(r)了。
用穷举法可以很快找到n(1)：
>>> 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)。
除了使用穷举法，还可以用下面的程序计算：
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()的用法：
2021759595L
为了理解这段迭代法的工作原理，我们用SymPy编写一个迭代程序：
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
程序的输出为：
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。
对于❸，可以列出下面的两个方程：
-251448106*k + 58545*n = 2*a+1
解这个方程组得到：
n = 4294967296*a + 2021759595
但将a=0代入上面的解中即可求出k和n。
让我们再回顾一下前面介绍的哈希值运算函数：
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 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的乘法和异或运算加快计算速度。
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个字符串：
'ofLCCCaa', 'uemC0Daa', 'CbgFKKaa', 'd0XRbNaa', 'hUzU9Saa']