hashConflict.py

import time
# [1, 2, 3, ...N, 1, 2, 3, ...N]というリストを作る
n = 200000
start = time.time()
listSeq = list(range(n//2))
d = dict()
for x in listSeq: d[x] = True
print("listSeq elapsed_time:{0}".format(time.time() - start) + "[sec]") # listSeq elapsed_time:0.0070133209228515625[sec]

# [2^17+1(=1), 6,31, 156]というリストを作る
d = dict()
start = time.time()
listCollision = []
mask = (1<<17) - 1 # 0xffff
listCollision.append(mask+2) # ind = 1
ind = 6 # ind = 6->31->156...
print(listCollision)
for i in range(1,43000): # key=1と衝突するキーで埋める。この値が大きすぎると環境により(pypy?)うまくぶつからない。おそらくdk_sizeが変わってしまうのか？
    listCollision.append(ind)
    ind = (ind * 5 + 1) & mask
print(min(listCollision), max(listCollision)) # -> 5 131073
for i in range(1, n-len(listCollision)): # 1で埋める。(各アクセスは上記で入れたkeyとぶつかる)
    listCollision.append(1)
print("listColision", listCollision[:10]) # listColision [131073, 6, 31, 156, 781, 3906, 19531, 97656, 95065, 82110]
for x in listCollision: d[x] = True
print("listCollision elapsed_time:{0}".format(time.time() - start) + "[sec]") # listCollision elapsed_time:16.341837167739868[sec]