""" hash_table.py Looking at a model of simple hash table. Output is at the end of the file. Jim Mahoney | April 2013 | MIT License """ import random A = 33 # 3 * 11 B = 5381 # prime C = 4294967296 # 2**32; do everything mod this def myhash(key): """ Return integer hash value given a string. """ # This is close djb2 , but I didn't want 'abc' and 'abcd' to be sequential. # see e.g. http://www.cse.yorku.ca/~oz/hash.html # and http://stackoverflow.com/questions/1579721/ result = 0 for char in key: result = (A * result + B + ord(char)) % C return result def moby_words(how_many='all'): """ Return list of words from Moby Dick. Optionally give how_many """ filename = 'moby_dick.txt' file = open(filename, 'r') punc = [',', '.', '"', "'", ';', ':', '!', '(', ')', '*', '$', '?', '--', '&', '[', ']', '_'] result = set() while True: line = file.readline() if not line: result = list(result) if how_many != 'all': result = random.sample(result, how_many) result.sort() return result words = line.split() for word in words: word = word.lower().strip() for p in punc: word = word.replace(p, '') if word != '': result.add(word) class MyHashTable(object): """ A demo implementation of a hash table with strings for keys (Yes, I know that python already has dictionaries - this is just to get an idea of how things like that are implemented.) >>> hash = MyHashTable() # Create a hashtable. >>> 'color' in hash # See if has a given key. False >>> hash['color'] = 'red' # Put (key, value) into hash. >>> 'color' in hash True >>> hash['color'] # Get value for given key. 'red' >>> len(hash) # How many keys are in the hash? 1 >>> hash.collisions # How many collisions have there been? 0 >>> tiny = MyHashTable(7) >>> tiny.buckets [None, None, None, None, None, None, None] >>> tiny['a'] = 1 >>> tiny['b'] = 2 >>> tiny.buckets [None, None, None, None, ('a', 1), ('b', 2), None] >>> tiny['h'] = 3 >>> tiny.collisions 1 """ # self.buckets is [(key,value), (key,value), ...] # where (key,value) is placed at index i with # i = ( myhash(key) + n * myhash(key+'#') ) % self.size # with n=0 on first attempt (no collision), # and n=1,2,3,... until we find an empty slot # The idea is that "clumps" will be avoided since each # key has a different collision offset. # This uses python's special class methods to emulate # a python dictionary; see e.g. # http://docs.python.org/release/2.5.2/ref/sequence-types.html # TODO: (i.e. things not yet implemented ... and likely never will be) # # * Bug : it's possible for the collision avoidance to fail # in this implementation - see the error at the end of the file. # # * Implement __delitem__ to remove items. # (Note that this means previously collided objects may # need to be adjusted.) # # * Dynamically adjust the number of buckets as items grows (shrinks?) # ... and have the indexing scheme adapt accordingly. # def __init__(self, size=127): # Note that default size is prime which hopefully therefore # cycles through all slots when looking for an empty one. self.n_buckets = size # (fixed) number of slots self.buckets = [None] * size self.n_items = 0 # number of (key,value) pairs self.collisions = 0 # number of items in "wrong" spot self.steps = 0 # O() count of steps in _i_ def __str__(self): return '' % (self.n_items, id(self)) def __len__(self): return self.n_items def __getitem__(self, key): """ Return self[key] """ i = self._i_(key) if self.buckets[i] == None: raise Exception("Oops : no key '%s' in %s" % (key, str(self))) return self.buckets[i][1] def __setitem__(self, key, value): """ Set self[key]=value """ i = self._i_(key) if self.buckets[i] == None: # new item? self.n_items += 1 if i != self._i0_(key): # default index? self.collisions += 1 self.buckets[i] = (key, value) def __contains__(self, key): """ Return True if 'key in self' """ return self.buckets[self._i_(key)] != None def _i0_(self, key): """ Return default hash index, without collision avoidance """ return myhash(key) % self.n_buckets def _i_(self, key): """ Return first hash index i such that self.buckets[i]==None or self.buckets[i]=(key,*) """ i = self._i0_(key) counter = 0 collision_offset = myhash(key + '#') self.steps = 1 while self.buckets[i] != None and self.buckets[i][0] != key: self.steps += 1 i = (i + collision_offset) % self.n_buckets counter += 1 if counter > 2 * self.n_buckets: raise Exception('Oops : MyHashTable._i_ error') return i def main(): """ Look at the hash table collsisions and occupancy """ prime = 2999 table = MyHashTable(prime) for nwords in (50, 200, 500, 1500, 2500): words = moby_words(nwords) for w in words: table[w] = True print print "hash table has %i buckets containing %i words " % \ (table.n_buckets, len(words)) steps = 0.0 maxstep = 0 maxword = '' for w in words: table[w] # Side effect : calculate table.steps steps += table.steps if table.steps > maxstep: maxstep = table.steps maxword = w print "collisions = %i ; average access steps = %f " % \ (table.collisions, steps/len(words)) print "max steps = %i for word '%s' " % (maxstep, maxword) column = 0 for i in xrange(prime): column += 1 if table.buckets[i] == None: print '.', else: print '*', if column == 30: print column = 0 print if __name__ == '__main__': import doctest doctest.testmod() main() """ python hash_table.py hash table has 2999 buckets containing 50 words collisions = 0 ; average access steps = 1.000000 max steps = 1 for word 'affect' . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . * * . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . hash table has 2999 buckets containing 200 words collisions = 8 ; average access steps = 1.040000 max steps = 2 for word 'along' * . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . * . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . * . . * . . . . . . . . . . . . . . . . . * * * . . . . . . . . . . . . . . * * . * . . . . . . . . . . . . * . . . . . . . . . . . . . * . * . * * . . . . . . . . . . . . . . . . . . . . . . . . . * * * . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . * . . . . . . . . * . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . * . . . * . . * . . . . . . . . . . . . . * . . . . . . * . . . . . . . . . . . . . . . . . . . . . . * . . . * . . . * . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . * . . * . . * . . . . . . . . . * . . . . . * . . . * . . . . . . . . . * . . . . . * . . . . . . * . . . . . . . . * . * . . * . . . . . . . . . . . . . . . * . . . . . . . . . . * . . * . . * . . . . * . . . * . . . . . . . . * . . . . . . * . . . . . * . . * . * . * . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . * . . . . . * . . . . . * . * * . . . . . . . . . . . . . . . . . . . . . . * . . * . . . * . . . . . . . . . . . . * . . . . . . . . . . . . . * . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . * . . . . . * . . . . * . . . . . . . . * . * . . . . . . . . . . . . . . . . . . . . . . * . . . * . . . * . . . . . . . . * . . . . . . . . . . . . . * . . . . . . . . . . . * . . . . . * . . . * . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . * . . * . . . * . * . . . . . . . . . . . * . . . . . . . . . * . . . . . * . . . . * . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . * . . . * . . . * . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . * . . . . . . . . . . * . . . . . . . . . . . . . * . . . . . * . * . . . . * . . . . . . . . . . . . . * * . . . . . * . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * * . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . * . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . * * . . . . . . . . . * . . . . . . . . . . . * . . . * . . . . . . . . . . . . . . . . . . * . . . . . . * . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . * . . . . . * . . . * . . * * . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . * . . . . . . * * . * . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . * * . . . . * . . . . . . . . . . . . * . . . . . * . . . . * . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . * . . . . * . . . . . . . * . . . . . . . . . . . . . . . . . . . . . * . . . . . * . . * . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . * . . . . . . * . . . . . . . * . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . * . . . . . . * . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . * . . . . * . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . * . * . . . . . . . . . . . * . * . . . . . . . . . . . * . . . . . * . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . * . . . . . . . * . . . . . . . . . . . . . . . . . . . . * * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . * . . * . . . . . . . . . . . . * . . . . . . . . . . . . . * . . . . . . . . . * . . . . . . . . . . . . . . . . . * . * . . . . . . . * . . . . . . . . . . . . . . . . . . . . * . . * . . . . . * . . . . . . . . . . . . . . * . . . . . . . . . . . * . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . * . . . * . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . * . * . . * . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . * . . . . . * . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . * . * . . . . . * . . . . . * . . . . . . * . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . * . . . . . . . . . . . . * . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . * . . . * . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . * . . . * . . . . . * . . . . . . . . . . . . . . . . . . . . . . . * . . . . . * . * . . . . . . * * . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * . . . . . . . . . . . * . . . . . . . . . . . . . * . . . . . . . . . . . . . . * . . . * . . . . . . . * . . . . . . * . . . . . . * . . . . . . . . . . . . . . . . hash table has 2999 buckets containing 500 words collisions = 82 ; average access steps = 1.180000 max steps = 7 for word 'turkish-rugged' * . . * . * * . . . . . . . * * . . . . . . * * . . . * . * . . . . . . * * . . . . . . . . . . * . . * * . * . * . . . . . * . . . . * . . . . * . * . . . . * . . . . . . . . . . . . . * . . . * * . . . . . * . . . . . . . . . . . . * * . * . . . . . . . . . * . . . . * . . . . . . . . . . . . * * . . . . * * . . . . . . . . . . * . * . . . . . . * . * . * . * . . . . . * . . . . . . . . . . . . * * * . . * . . . . * . * * . . . . . . . . . . . . . * . . * * * * . . . * . . . . . . * * . . * * . * * . . . * . * . * . . . * . . . . . . . . * . . * . * . * . * * * . . * * . . * . . * . . . . * . . . * . . . . . * * * . . * . . . * . . . . . . . . . * . . . . * . . * . . . . . . . * . * . * . . * . * . * . * * . . . . . * * . . . . * * * . . . . . * . . . . . . . . . . . . . . . . . . * . . * . . . . . * . . . . . * . . . . * * * . . * . . * . . . . . . * . * . * . . * . . . . . . . . . . . . . * . . . . . . * * . . . . . . . . . . . . . . . . . . . . . * . . * * . . . * . * . . . . * . . . . . . . * . . * . . . . . . . . . . . . . * . * * . . * . . . . * . * . . * . . . . . * . . . * . . . . . . . . * * . . . . . * . . . . . . * * . . . . . . . * * * . . * . . . . . . . . . * * . * * . * . . . . . . . . . . * . . * . * * * . . . * . * . * . . . . * . * . * . . . * . . * * . . . . * . . * * * . * . * . . * . . . . . . . . . * . . . . . * . * . . * . . . . * . . . . * * . . . . . . . . . * . . . * . . . . . . . . * . . . . . . . . . . . . . * * * . . . . * . . * * . * . * * . . * . . . . . . . * * . . . . . * . . . . * . . * . . . * . . . . . * . . . . . * * . . . . . . . . * . . * * * . . * . . . * * * . . . * . * . . . . . . . . . . . . * . . . . * . . . . . . . . . . * . . . . . . . . . . . * . . . . . . . . . . . . . . * . * . . . * * . * * * . . . . . . . . * . * . . . . * . . * . . * . . * . * . . * . . * * . * * * . . . * . . . . . . . . * . * * . . . * . . . . . * * . . . * . * * . . . * * . * . . . * . . . * . . . * * * . . . . . . * . . . . . . . . * . . . . . . * . * . . * . . . * . * * . . * . * . . * . * * * . . * . . . . . * * . . . . * . * . . * . . . . * . . * . . . . . * . * . . . . . . * . . . . . . . * . * . . . . . * . * . . . . * . . . . . . * . . * . . * * . * . * . . . . . . . . . * . * . . . * * . . . . . . . * . . . * . . . * . . * . . . . . . . * . . . . . . . . * . * . . * . * . * . . . . . . . . * * . . . . * * . . . . . . * * . . . . * . * . . . . * * . * . . . . . . * . * . * * . . . . . * . . * . . * * . . . . . . . . . . . * . . . . . . . . . . . . * . . * . . . * * * . . . . . . * . . . * * * * . . * . * . * . . . * . * . . . . . . . . . . . . . . . * . . . . . . . . . * . . . . * * . . * . . . . . . . . . . . . . * . * . . . . . . . . . . . . * . . . . . . . . . . * * . . * . . * . . . * . . . . * * . * * . . * . * * . . * . . . . * * * . . . . . . . . . . . * . . * . . . . . * . . * . . * . * . . . * . * . . . . * * . . . . * . . * . * . . . . * * . . . . . * . . . * . . . . . . . . . . . . . * . * . . * . . . * * . * . . . . . . . . . . . . * . . . * * . . . * . . . . . . . . . . * . * * . . * . * . * . . * * . . . . . . . * . . . . . . . . . . * . . * . . . . * . * * . . * * . . * . . . * . . . * . . . . . * * . . . . . . . . . . . . . . . . * * . . . * * * . * . . . * * . * . * . . * . . * . . . . * . . . . . . . . . . . . . . . . . . * * * . . . * . . . . . . * . . . . . * * * . . * * . . . . * . . . . . . . . . . . . . * . . . * . . . . * * . . . . . * . . . . . . . * . . * . . . . . . . . . . * * . . . . . . . . . . . . . * . . . . * . . . . * . * . . . . . * . . * . . * . . . . * . . . . . * . . . . * . . . * . * . . * . . . * . . . . . * . . . * . * . . . . . . * . . . . . . . . * . . . * . . * . . * * * . . . . . . * . . * . . . . . . . * . . . * . * * . . . * . * . . . . . . * . . . . . . * . . . * . . * * * . . * . * * . * . . * . * . . * * * . . * * * * . . . . . * . . . . * . . . . * . . . . * . . . . . * * . * . . . . . . * . * . * . . . . . . . . . . . . . * . . . * . . . . . . * . . . . * . * * . . . * * . . . . * . . . . . . . . . . * . * . . * . . . * . . . . . * . . . . . * * . . * . . . . . * * * . . . . . * . * * . * . . * * . * * . . . . * . . . * . * . * . . . . . . . . * . . * . . . . * * . . * . . . * . . . . * . . . . . . . . . . . . . . . . . * * . . . . . . . * . . . . * . . . . * . . * . . . . . * . * * . . * . . . * . . . . . . . . . . . * . . . . . . * * . . . . . * * . . . . . . . . . * * . . . . . . . . . . . . . . * . . * . . * . . * . . . . . . * . . . . . . . * . . . * . * . . * . . * . * . * . . * . . . . . . . . * . * . . . * . * . . . . . . . * . . . . . * . * . . . * * . . . . . . . * . . * * . * . . * * . . . * . . . . . . . . . * . . . . . * . . . . . * . . . . * . . . . . . . . . . . . * . . . . . . . . . . . * . . . . . . . . . . . * . . . . . . . . . . . * * . . * . . . * * * . . . . . * . . . * . * . . * . . . . . . . . * . . . . . * * . * . . * . . . * . . . . . . * . . . . . * * * . * . . . . . . . . . . * . . . * * . . * . * . . . . . . . . . . * . * . . . . . . . . . * . . . . . * . . . . . * . . . * . * . . . . . . . . . . . . . * . * . . . . . * . . * . . * . . . . . . * * . . * . . . . . . . * . . . . . * . . . . . . * * . . . . * . . * . * . * . . . . . . . . * . . . * . . . . * * . . . . . . * . * . . . . . * . . . . . . . * . . . . . . . * . * * * . . . . . * . . * . . * . * . . . . . . . . . . * . * * . . . * . * . . . . * . . . . * . . . . * . . . . . . . . * . . . . . * . . . . . * . * . * * . . * * . * * * * . * . * . . . . . . . . . . . . . . * . * . . * * . . . . * . * * . * . . . * * . * . . . . . * . . * . . * . . . * . . . . . * . * . . . * . . . . * * . . . . . . . . . * . * . * . . . . . . * . . . . . . . . * . . * * . . * . . . * * . . . . * * . * * . . . * . . * . . . . * . . . . * . . . . . . . . . . . . . . . . * . * . * . . * . * * . * . . . * . * . * . . . . . . * . . * . * . . * . . . . . . . . . * . . . * . . * . . * * * . . . . . . * . . . . . . * . . . . * . . . . . * . . * . . hash table has 2999 buckets containing 1500 words collisions = 804 ; average access steps = 2.124667 max steps = 23 for word 'worse' * * * * . * * * . . * . * . * * * * . * . . * * . * * * . * * . * * . * * * * * * * * . . * * * * . * * * * * * * * . * * * * . * * * * * . . . * * * * * . * * * * * . * * * * * * * * * * . * . * * * . * * * * * . * * . * * . . * * * * * * * * * * . * * * * * * * . . * * * * * * . * * . . * * * * * * * * * * * . * . . * . * . * . * * * . * . . * . * . * * * . * * . . . * * * . * * * * * . * * . . * * * * . * . * * * * . * * . * . * * . . . * . . * * * * * * * * * * . . * . . . . * . * * * . * * . * * * * * * * * . * * * * * * * . * * * * . * . * * . * * * * * * * . * * * * . * . * * . . . * * * * * * . * * . * * * * * * * * * * * . * . . * * . * . * . * * . * * . * . * * * * . . * . * * * * * * . * * * . * * . * * * . * * . * * * * * * * * . * . * * * . * * * * * * * * * * * * . * * * * . * . * . . * * * . * . . * * . . * * * * . . * . . * * . . * * . * * * * * * * * * * . * * * * . * * . . * * . . * * . * * * * * * * * . . . * * * * . * . * . * . * . * * . * * * * * * . * . * * * * . * . . . * * * . . * * * * * . * . * . * * * * * . * * . * * . . * * * * * . . * * * . * * * . * . * . * * * * . * * * * * . * * * * . * * * * . * * * * * * * * . * * * . * * * * . * * * . * . * * * * * * * * . . * * * * . * . * * * * * * * * * . * * . * . * * * * . * * * * * * . * * * * * * . . . * * * * * * * * * * * * . * * * . . . . * * . * * . * * * * * * * * * . * . . * . * * . * * . . * * * . * * * * . . . * * * * . * * * * * * * * * . * * . . * * . . * * * . * . . * . * * * * * . * * * . * . * * * * * . * * * . * * * * * . * * * . * * . * * * * . * . * * * * * * * * * * . . * . * * * * * * * * * * . * . * * * * * * * * * * * * * * . . * * . . * . . * * * . * * * . * * * * * * * . * . . . * . . * . . * . * . * . * * . . * * * . * . . * * * . . . * * . * * * * . * * * . * * * * * * * . . * * * * * * * * . * . * * . * * * * * * * * * * * * * * * * * * . * * * * * * * . . * . * * . * * * . . . * * * * * * * * * * * . . * * . * * * * * * * * * . . * * * * * * * * * * * . * * * . * * . . * * * * . * . * * * . * * * * * * * * . * * * * * * * * * . . . * * * * * * * * . * * . * * * * * * . . * * * . * . * * * * * . . . * * * . . * * . * * * * * . * . . * . * * * * * * * * * . * . * . . * * * * * * * * * . * * . . . * . . * * * . . * * * . * . . * * . * * . . * * * * * . . * * . . * * * * * * * * * * . * . * . * * . * * * . * * . . * * * . * * * * * * * * * . . . * . * * * . * . . * * * * * . * * * * * * * . . * * * * * . * * * * * * . * . . * * . * * . * * . * . . * . * * * . * * . * . * * * . * . * * * * . . * * * * * * * * * * * * . * * * * * * * * * * * * * * * * * * * * . * * * * * . . . * . . * * * . * * . * . . * * * . * * * * * * * * * * . . . . . * * * . . * . * * * * * * * . * * * * . * * . . * * . * . * * * * . * * * * * * * * * . . * . * * * * * * * * . * * . * * * . * * * * * * . * . . * . * * . . * * * * . . * * * * * * * * * * * * * . . * . * * * * * * * . * . * * * . * * * * * . * * * * * * . . * * * * * * * * * . . * * * * * . . * . * * . * * . * * * . * . * * * . * . * . . . * * * * . * * * . . * . . * * * * * . * * * . * * * * * * * . * * . * * * * . * * * . * * . . * * * * * . . * * . * * * . * * * * * * * * * . . * * * . * * . * * . . . * * * * . . . * * * . * . . * . . * * * * * . * . * * * . * * * . * * . * . * . . * * . * * * * * * * * . * * * . . . * * * * . . . * . * * * . . * * . * * . . * * * . * * . * * * * * * * . * . * * * * . . * . * * . . * * . * * * * * * * * * * * * * . * * * * * . * . . * * * * * * . * . . * * . . * * * . . * * . * . * . * . . * * * . . * * * * * . * . * * * * * * * * * * * * * . * . . * . * . . . * * . * * * . * * * * * * * * * * . * . * . * * * . * * * * * * * . * . * * * . . * * * * * * * . * * * . * * * * * * * * * * . * * . . * * . * . . * * * * . * * * * * * * . * * * . * * * . . * . * * . * . * * * * * * * * * * . * * . * * . * * * * . * * * * * * * * * * * * . * * . . * * . * * * . * * * * * . * . * . * * . * * * . * . * . * . . * * * . * . . * . * * . * * . * * * * * * * * * . * . * * * * * . * * . * * * * . * * * * * . * . . * * * * * * . . * * * * . * * . . * * . * * * * * . * . . * * * * * . * . * * * * * * * . * . * * * * * * * . * * * * * . * * * * * * * * * * . * * . * * . . * * * * . * . * * * * * . . * * . * * * . * * * * * * . * . * * . * * . * * . * . * * . * * * * * . * * . * * * * . * * * . * * * . * * * * * * * . * * * . . * * * . * * . * * . * * * * . * * * * * * . . . * * * * . . * . . . * . * * * . * * * * . * . * * * . * . * . * * * * * * * * * * . * * * * * * * . * * . * . * * * * * . . * * . * * * * * * * * * . . * * * * * * . * . * * * * * * * * * * * * * * * . . . * * * * * * * * * . * * * * . * * * * * * * * * * * . * * * . * * . * * * * . * * * * * . * * * * * * * * * . . * * * * * * * * * * . * * * . . . . . * * . * . . * * * . * . . * * . . * * * * * * * * . * * * * * * * . * . * . * * * . * * * * * * * * * * * * * * . * * * . . * . * . * * * * * * . * * * * * . * * . . . * . * * * * . * . * * * * * * * * * * . * * * * * * . . * * * * * * * . . * . * . * . * * * * * * . * * . * . . * * * * * * . * * * * * * * . * * * . * * * . * * * * * * * . * * * * * * . * . * * . * * . * * . * * * * * * * * . * * * * * * * . * . . . . . * . . . . * * * * . * . * * . . * . * * * * . . . * * . . * * * * * * . . * * * * * * * * . * * * * * * . . * * * . * * * * * * . . . * * * * * * * * * * . . . * . * * * . * * * . . * . . * * . * * * . * * * * * * * * * . * . * . * . * * * . * * * * . * * * * * . * * * * * * * . * . * . * . * * * * . * * * . * * * * . * * * . * . . * * * * . * * * . * * * * * * * * * * * * * . * * . * * * * * * * * . * * * * * . * * * * * * . * * * * * * * * . * * * * * . * * * * * * . * . . * * * . * * * * * * * * * * . * * * . * . . * * * * * * * . * * * * * * * * * . . * * . * * * . . * . * * * * * . * . * . . * . * * * . * * . * * * . . . * . * * * . * * * * . * * * * * . . * * * * * * * . * * * * * * * * * * * * * . . * . . * . * * . * . * * . * * * * * * * * * . * . * * * . * * . * . * * * * * * . * * * . . * * * Traceback (most recent call last): File "hash_table.py", line 194, in main() File "hash_table.py", line 162, in main table[w] = True File "hash_table.py", line 125, in __setitem__ i = self._i_(key) File "hash_table.py", line 152, in _i_ raise Exception('Oops : MyHashTable._i_ error') Exception: Oops : MyHashTable._i_ error """