```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 ``` ```#!/usr/bin/env python import itertools from math import log def erat2(): D = {} yield 2 for q in itertools.islice(itertools.count(3), 0, None, 2): p = D.pop(q, None) if p is None: D[q * q] = q yield q else: x = p + q while x in D or not (x & 1): x += p D[x] = p # Inefficient, but not the point of the exercise def next_prime(p): e = erat2() x = e.next() while x <= p: x = e.next() return x def ilog2(x): return int(log(x, 2)) def string_hash(s, x): return reduce(lambda h, c: h * x + ord(c), s, 0) class CuckooTable(dict): def __init__(self, max_size=25, x1=31, x2=37): self.max_probes = max(2 * ilog2(max_size), 20) self.table_size = next_prime(2 * max_size) self.x1 = x1 self.x2 = x2 return None def __repr__(self): r = "Cuckoo Table:\nx1 = %d\nx2 = %d\n" % (self.x1, self.x2) r += dict.__repr__(self) return r def resetMultipliers(self): self.x1 = next_prime(self.x1) self.x2 = next_prime(self.x2) return None def keyHash(self, key, x): return string_hash(key, x) % self.table_size def lookup(self, key): for x in (self.x1, self.x2): h = self.keyHash(key, x) if self.get(h) and self[h][0] == key: return self[h] return None def insert(self, key, value): if self.lookup(key): h1, h2 = self.keyHash(key, self.x1), self.keyHash(key, self.x2) if self.get(h1) and self[h1][0] == key: self[h1] = (key, value) else: self[h2] = (key, value) else: k, v, c = key, value, self.max_probes while c > 0: h1, h2 = self.keyHash(k, self.x1), self.keyHash(k, self.x2) if not self.get(h1): self[h1] = (k, v) break elif not self.get(h2): self[h2] = (k, v) break else: t = self[h1] self[h1] = (k, v) k, v, c = t[0], t[1], c - 1 if c == 0: self.rehash() self.insert(k, v) return None def rehash(self): self.resetMultipliers() _newTable = self.copy() self.clear() for item in _newTable.itervalues(): self.insert(item[0], item[1]) return None def delete(self, key): for x in (self.x1, self.x2): h = self.keyHash(key, x) if self.get(h) and self[h][0] == key: self.pop(h) return None def enlist(self): return sorted(self.items()) # Do we even require sorted order? words = ["alpha", "bravo", "charlie", "delta", "echo", "foxtrot", "golf", "hotel", "india", "juliet", "kilo", "lima", "mike", "november", "oscar", "papa", "quebec", "romeo", "sierra", "tango", "uniform", "victor", "whiskey", "xray", "yankee", "zulu"] def cuckoo_test(): t = CuckooTable() print t.lookup("praxis") is None for val in xrange(len(words)): t.insert(words[val], val + 1) print t.lookup("praxis") is None print t.lookup("papa") t.delete("papa") print t.lookup("papa") is None return None if __name__ == "__main__": cuckoo_test() ```
 ```1 2 3 4 ``` ```True True ('papa', 16) True ```