from itertools import count, accumulate, chain, cycle
from random import randrange, sample
empty = ("_empty", "_empty", 0)
deleted = ("_deleted", "_deleted", 0)
def is_prime(x):
for f in accumulate(chain((2, 1, 2, 2), cycle((4, 2, 4, 2, 4, 6, 2, 6)))):
if f * f > x:
return True
if x % f == 0:
return False
def next_prime(x):
return next(p for p in count(x|1, 2) if is_prime(p))
def inc_linprob(hashval, M):
""" increment for linear probing"""
return 1
def inc_double_hashing(hashval, M):
""" increment for double hashing - make sure it is not in range [1, M-1]"""
return hashval % (M-1) + 1
class dictlh(object):
""" Store (key, value, hash(key))
"""
def __init__(self, mode=inc_linprob, load_factor=0.5):
self.M = 997
self.buckets = [empty] * self.M
self.load_factor = load_factor
self.max_load = load_factor * self.M
self.n_elements = 0
self.n_deleted = 0
self._increment = mode
self.searches = 0
def _find_insert_bucket(self, key):
""" result: find the key OR find an empty bucket to insert """
hashval = hash(key)
b, M = self.buckets, self.M
inc = self._increment(hashval, M)
h = hashval % M
bh = b[h]
while bh != empty and bh[0] != key:
h = (h + inc) % M
bh = b[h]
self.searches += 1
return h
def _insert(self, key, value, hashval=None):
if hashval is None:
hashval = hash(key)
bi = self._find_insert_bucket(key)
isempty = self.buckets[bi] == empty
self.buckets[bi] = (key, value)
if isempty:
self.n_elements += 1
if self.n_elements > self.max_load:
self._rehash()
def _find_key(self, key):
bi = self._find_insert_bucket(key)
if self.buckets[bi][0] == key:
return bi
raise KeyError
("key not found")
def _lookup(self, key):
h = self._find_key(key)
return self.buckets[h][1]
def _rehash(self):
load = self.n_elements - self.n_deleted
self.M = next_prime(4 * load)
self.max_load = self.load_factor * self.M
self.n_elements = self.n_deleted = 0
old_buckets = list(self.buckets)
self.buckets = [empty] * self.M
for item in old_buckets:
if item not in (deleted, empty):
self._insert(*item)
def _delete(self, key):
h = self._find_key(key)
self.buckets[h] = deleted
self.n_deleted += 1
def __setitem__(self, key, value):
self._insert(key, value)
def __getitem__(self, key):
return self._lookup(key)
def __delitem__(self, key):
self._delete(key)
def get(self, key, default=None):
try:
return self._lookup(key)
except KeyError:
return default
def __len__(self):
return self.n_elements - self.n_deleted
def __contains__(self, key):
bi = self._find_insert_bucket(key)
return self.buckets[bi][0] == key
def __iter__(self):
yield from (b[0] for b in self.buckets if b not in (empty, deleted))
def keys(self):
"""a copy of all keys"""
return list((b[0] for b in self.buckets if b not in (empty, deleted)))
def values(self):
"""a copy of all values"""
return list((b[1] for b in self.buckets if b not in (empty, deleted)))
if __name__ == '__main__':
from glob import glob
from itertools import starmap, repeat
def repeatfunc(func, times=None, *args):
if times is None:
return starmap(func, repeat(args))
return starmap(func, repeat(args, times))
load_factor = 0.50
# Tests
for mode in (inc_linprob, inc_double_hashing):
D = dictlh(mode=mode, load_factor=load_factor)
PD = {}
for k, v in zip("abcdefghijklmnopqrstuvwxyz", range(26)):
D[k] = v
PD[k] = v
del D["v"]
del PD["v"]
try:
D["v"]
except KeyError:
pass
for key in "abcdefghijklmnopqrstuwxyz":
D["a"] = 99
PD["a"] = 99
def random_ints(N, start, stop):
return list(repeatfunc(randrange, N, *(start, stop)))
N = 1000
rand1, rand2 = random_ints(N, 0, 50), random_ints(N, 0, 1000000)
for key, val in zip(rand1, rand2):
D[key] = val
PD[key] = val
for key in sample(rand1, N // 2):
try:
del D[key]
except KeyError:
pass
try:
del PD[key]
except KeyError:
pass
for key, val in PD.items():
assert D
[key
] == val
, "{} {} {}".
format(key
, val
, D
[key
])
print(D.searches)
print("tests OK")
ZnJvbSBpdGVydG9vbHMgaW1wb3J0IGNvdW50LCBhY2N1bXVsYXRlLCBjaGFpbiwgY3ljbGUKZnJvbSByYW5kb20gaW1wb3J0IHJhbmRyYW5nZSwgc2FtcGxlCgplbXB0eSA9ICgiX2VtcHR5IiwgIl9lbXB0eSIsIDApCmRlbGV0ZWQgPSAoIl9kZWxldGVkIiwgIl9kZWxldGVkIiwgMCkKCmRlZiBpc19wcmltZSh4KToKICAgIGZvciBmIGluIGFjY3VtdWxhdGUoY2hhaW4oKDIsIDEsIDIsIDIpLCBjeWNsZSgoNCwgMiwgNCwgMiwgNCwgNiwgMiwgNikpKSk6CiAgICAgICAgaWYgZiAqIGYgPiB4OgogICAgICAgICAgICByZXR1cm4gVHJ1ZQogICAgICAgIGlmIHggJSBmID09IDA6CiAgICAgICAgICAgIHJldHVybiBGYWxzZQoKZGVmIG5leHRfcHJpbWUoeCk6CiAgICByZXR1cm4gbmV4dChwIGZvciBwIGluIGNvdW50KHh8MSwgMikgaWYgaXNfcHJpbWUocCkpCgpkZWYgaW5jX2xpbnByb2IoaGFzaHZhbCwgTSk6CiAgICAiIiIgaW5jcmVtZW50IGZvciBsaW5lYXIgcHJvYmluZyIiIgogICAgcmV0dXJuIDEKCmRlZiBpbmNfZG91YmxlX2hhc2hpbmcoaGFzaHZhbCwgTSk6CiAgICAiIiIgaW5jcmVtZW50IGZvciBkb3VibGUgaGFzaGluZyAtIG1ha2Ugc3VyZSBpdCBpcyBub3QgaW4gcmFuZ2UgWzEsIE0tMV0iIiIKICAgIHJldHVybiBoYXNodmFsICUgKE0tMSkgKyAxCgpjbGFzcyBkaWN0bGgob2JqZWN0KToKICAgICIiIiBTdG9yZSAoa2V5LCB2YWx1ZSwgaGFzaChrZXkpKQogICAgIiIiCiAgICBkZWYgX19pbml0X18oc2VsZiwgbW9kZT1pbmNfbGlucHJvYiwgbG9hZF9mYWN0b3I9MC41KToKICAgICAgICBzZWxmLk0gPSA5OTcKICAgICAgICBzZWxmLmJ1Y2tldHMgPSBbZW1wdHldICogc2VsZi5NCiAgICAgICAgc2VsZi5sb2FkX2ZhY3RvciA9IGxvYWRfZmFjdG9yCiAgICAgICAgc2VsZi5tYXhfbG9hZCA9IGxvYWRfZmFjdG9yICogc2VsZi5NCiAgICAgICAgc2VsZi5uX2VsZW1lbnRzID0gMAogICAgICAgIHNlbGYubl9kZWxldGVkID0gMAogICAgICAgIHNlbGYuX2luY3JlbWVudCA9IG1vZGUKICAgICAgICBzZWxmLnNlYXJjaGVzID0gMAoKICAgIGRlZiBfZmluZF9pbnNlcnRfYnVja2V0KHNlbGYsIGtleSk6CiAgICAgICAgIiIiIHJlc3VsdDogZmluZCB0aGUga2V5IE9SIGZpbmQgYW4gZW1wdHkgYnVja2V0IHRvIGluc2VydCAiIiIKICAgICAgICBoYXNodmFsID0gaGFzaChrZXkpCiAgICAgICAgYiwgTSA9IHNlbGYuYnVja2V0cywgc2VsZi5NCiAgICAgICAgaW5jID0gc2VsZi5faW5jcmVtZW50KGhhc2h2YWwsIE0pCiAgICAgICAgaCA9IGhhc2h2YWwgJSBNCiAgICAgICAgYmggPSBiW2hdCiAgICAgICAgd2hpbGUgYmggIT0gZW1wdHkgYW5kIGJoWzBdICE9IGtleToKICAgICAgICAgICAgaCA9IChoICsgaW5jKSAlIE0KICAgICAgICAgICAgYmggPSBiW2hdCiAgICAgICAgICAgIHNlbGYuc2VhcmNoZXMgKz0gMQogICAgICAgIHJldHVybiBoCgogICAgZGVmIF9pbnNlcnQoc2VsZiwga2V5LCB2YWx1ZSwgaGFzaHZhbD1Ob25lKToKICAgICAgICBpZiBoYXNodmFsIGlzIE5vbmU6CiAgICAgICAgICAgIGhhc2h2YWwgPSBoYXNoKGtleSkKICAgICAgICBiaSA9IHNlbGYuX2ZpbmRfaW5zZXJ0X2J1Y2tldChrZXkpCiAgICAgICAgaXNlbXB0eSA9IHNlbGYuYnVja2V0c1tiaV0gPT0gZW1wdHkKICAgICAgICBzZWxmLmJ1Y2tldHNbYmldID0gKGtleSwgdmFsdWUpCiAgICAgICAgaWYgaXNlbXB0eToKICAgICAgICAgICAgc2VsZi5uX2VsZW1lbnRzICs9IDEKICAgICAgICAgICAgaWYgc2VsZi5uX2VsZW1lbnRzID4gc2VsZi5tYXhfbG9hZDoKICAgICAgICAgICAgICAgIHNlbGYuX3JlaGFzaCgpCgogICAgZGVmIF9maW5kX2tleShzZWxmLCBrZXkpOgogICAgICAgIGJpID0gc2VsZi5fZmluZF9pbnNlcnRfYnVja2V0KGtleSkKICAgICAgICBpZiBzZWxmLmJ1Y2tldHNbYmldWzBdID09IGtleToKICAgICAgICAgICAgcmV0dXJuIGJpCiAgICAgICAgcmFpc2UgS2V5RXJyb3IoImtleSBub3QgZm91bmQiKQoKICAgIGRlZiBfbG9va3VwKHNlbGYsIGtleSk6CiAgICAgICAgaCA9IHNlbGYuX2ZpbmRfa2V5KGtleSkKICAgICAgICByZXR1cm4gc2VsZi5idWNrZXRzW2hdWzFdCgogICAgZGVmIF9yZWhhc2goc2VsZik6CiAgICAgICAgbG9hZCA9IHNlbGYubl9lbGVtZW50cyAtIHNlbGYubl9kZWxldGVkCiAgICAgICAgc2VsZi5NID0gbmV4dF9wcmltZSg0ICogbG9hZCkKICAgICAgICBzZWxmLm1heF9sb2FkID0gc2VsZi5sb2FkX2ZhY3RvciAqIHNlbGYuTQogICAgICAgIHNlbGYubl9lbGVtZW50cyA9IHNlbGYubl9kZWxldGVkID0gMAogICAgICAgIG9sZF9idWNrZXRzID0gbGlzdChzZWxmLmJ1Y2tldHMpCiAgICAgICAgc2VsZi5idWNrZXRzID0gW2VtcHR5XSAqIHNlbGYuTQogICAgICAgIGZvciBpdGVtIGluIG9sZF9idWNrZXRzOgogICAgICAgICAgICBpZiBpdGVtIG5vdCBpbiAoZGVsZXRlZCwgZW1wdHkpOgogICAgICAgICAgICAgICAgc2VsZi5faW5zZXJ0KCppdGVtKQoKICAgIGRlZiBfZGVsZXRlKHNlbGYsIGtleSk6CiAgICAgICAgaCA9IHNlbGYuX2ZpbmRfa2V5KGtleSkKICAgICAgICBzZWxmLmJ1Y2tldHNbaF0gPSBkZWxldGVkCiAgICAgICAgc2VsZi5uX2RlbGV0ZWQgKz0gMQoKICAgIGRlZiBfX3NldGl0ZW1fXyhzZWxmLCBrZXksIHZhbHVlKToKICAgICAgICBzZWxmLl9pbnNlcnQoa2V5LCB2YWx1ZSkKCiAgICBkZWYgX19nZXRpdGVtX18oc2VsZiwga2V5KToKICAgICAgICByZXR1cm4gc2VsZi5fbG9va3VwKGtleSkKCiAgICBkZWYgX19kZWxpdGVtX18oc2VsZiwga2V5KToKICAgICAgICBzZWxmLl9kZWxldGUoa2V5KQoKICAgIGRlZiBnZXQoc2VsZiwga2V5LCBkZWZhdWx0PU5vbmUpOgogICAgICAgIHRyeToKICAgICAgICAgICAgcmV0dXJuIHNlbGYuX2xvb2t1cChrZXkpCiAgICAgICAgZXhjZXB0IEtleUVycm9yOgogICAgICAgICAgICByZXR1cm4gZGVmYXVsdAoKICAgIGRlZiBfX2xlbl9fKHNlbGYpOgogICAgICAgIHJldHVybiBzZWxmLm5fZWxlbWVudHMgLSBzZWxmLm5fZGVsZXRlZAoKICAgIGRlZiBfX2NvbnRhaW5zX18oc2VsZiwga2V5KToKICAgICAgICBiaSA9IHNlbGYuX2ZpbmRfaW5zZXJ0X2J1Y2tldChrZXkpCiAgICAgICAgcmV0dXJuIHNlbGYuYnVja2V0c1tiaV1bMF0gPT0ga2V5CgogICAgZGVmIF9faXRlcl9fKHNlbGYpOgogICAgICAgIHlpZWxkIGZyb20gKGJbMF0gZm9yIGIgaW4gc2VsZi5idWNrZXRzIGlmIGIgbm90IGluIChlbXB0eSwgZGVsZXRlZCkpCgogICAgZGVmIGtleXMoc2VsZik6CiAgICAgICAgIiIiYSBjb3B5IG9mIGFsbCBrZXlzIiIiCiAgICAgICAgcmV0dXJuIGxpc3QoKGJbMF0gZm9yIGIgaW4gc2VsZi5idWNrZXRzIGlmIGIgbm90IGluIChlbXB0eSwgZGVsZXRlZCkpKQoKICAgIGRlZiB2YWx1ZXMoc2VsZik6CiAgICAgICAgIiIiYSBjb3B5IG9mIGFsbCB2YWx1ZXMiIiIKICAgICAgICByZXR1cm4gbGlzdCgoYlsxXSBmb3IgYiBpbiBzZWxmLmJ1Y2tldHMgaWYgYiBub3QgaW4gKGVtcHR5LCBkZWxldGVkKSkpCgoKaWYgX19uYW1lX18gPT0gJ19fbWFpbl9fJzoKICAgIGZyb20gdGltZSBpbXBvcnQgY2xvY2sKICAgIGZyb20gZ2xvYiBpbXBvcnQgZ2xvYgogICAgZnJvbSBpdGVydG9vbHMgaW1wb3J0IHN0YXJtYXAsIHJlcGVhdAoKICAgIGRlZiByZXBlYXRmdW5jKGZ1bmMsIHRpbWVzPU5vbmUsICphcmdzKToKICAgICAgICBpZiB0aW1lcyBpcyBOb25lOgogICAgICAgICAgICByZXR1cm4gc3Rhcm1hcChmdW5jLCByZXBlYXQoYXJncykpCiAgICAgICAgcmV0dXJuIHN0YXJtYXAoZnVuYywgcmVwZWF0KGFyZ3MsIHRpbWVzKSkKCiAgICBsb2FkX2ZhY3RvciA9IDAuNTAKICAgICMgVGVzdHMKICAgIGZvciBtb2RlIGluIChpbmNfbGlucHJvYiwgaW5jX2RvdWJsZV9oYXNoaW5nKToKICAgICAgICBEID0gZGljdGxoKG1vZGU9bW9kZSwgbG9hZF9mYWN0b3I9bG9hZF9mYWN0b3IpCiAgICAgICAgUEQgPSB7fQogICAgICAgIGZvciBrLCB2IGluIHppcCgiYWJjZGVmZ2hpamtsbW5vcHFyc3R1dnd4eXoiLCByYW5nZSgyNikpOgogICAgICAgICAgICBEW2tdID0gdgogICAgICAgICAgICBQRFtrXSA9IHYKCiAgICAgICAgYXNzZXJ0IERbInYiXSA9PSBQRFsidiJdCgogICAgICAgIGRlbCBEWyJ2Il0KICAgICAgICBkZWwgUERbInYiXQogICAgICAgIHRyeToKICAgICAgICAgICAgRFsidiJdCiAgICAgICAgZXhjZXB0IEtleUVycm9yOgogICAgICAgICAgICBwYXNzCgogICAgICAgIGZvciBrZXkgaW4gImFiY2RlZmdoaWprbG1ub3BxcnN0dXd4eXoiOgogICAgICAgICAgICBhc3NlcnQgRFtrZXldID09IFBEW2tleV0KCiAgICAgICAgRFsiYSJdID0gOTkKICAgICAgICBQRFsiYSJdID0gOTkKICAgICAgICBhc3NlcnQgRFsiYSJdID09IFBEWyJhIl0KCiAgICAgICAgZGVmIHJhbmRvbV9pbnRzKE4sIHN0YXJ0LCBzdG9wKToKICAgICAgICAgICAgcmV0dXJuIGxpc3QocmVwZWF0ZnVuYyhyYW5kcmFuZ2UsIE4sICooc3RhcnQsIHN0b3ApKSkKCiAgICAgICAgTiA9IDEwMDAKICAgICAgICByYW5kMSwgcmFuZDIgPSByYW5kb21faW50cyhOLCAwLCA1MCksIHJhbmRvbV9pbnRzKE4sIDAsIDEwMDAwMDApCiAgICAgICAgZm9yIGtleSwgdmFsIGluIHppcChyYW5kMSwgcmFuZDIpOgogICAgICAgICAgICBEW2tleV0gPSB2YWwKICAgICAgICAgICAgUERba2V5XSA9IHZhbAogICAgICAgICAgICBhc3NlcnQgRFtrZXldID09IFBEW2tleV0KCiAgICAgICAgZm9yIGtleSBpbiBzYW1wbGUocmFuZDEsIE4gLy8gMik6CiAgICAgICAgICAgIHRyeToKICAgICAgICAgICAgICAgIGRlbCBEW2tleV0KICAgICAgICAgICAgZXhjZXB0IEtleUVycm9yOgogICAgICAgICAgICAgICAgcGFzcwogICAgICAgICAgICB0cnk6CiAgICAgICAgICAgICAgICBkZWwgUERba2V5XQogICAgICAgICAgICBleGNlcHQgS2V5RXJyb3I6CiAgICAgICAgICAgICAgICBwYXNzCiAgICAgICAgICAgICAgICAKCiAgICAgICAgZm9yIGtleSwgdmFsIGluIFBELml0ZW1zKCk6CiAgICAgICAgICAgIGFzc2VydCBEW2tleV0gPT0gdmFsLCAie30ge30ge30iLmZvcm1hdChrZXksIHZhbCwgRFtrZXldKQogICAgICAgIAogICAgICAgIHByaW50KEQuc2VhcmNoZXMpCiAgICAgICAgICAgIAogICAgICAgIHByaW50KCJ0ZXN0cyBPSyIpCg==