"""
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 '<MyHashTable n_items=%i id=0x%x>' % (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 <module>
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
"""
syntax highlighted by Code2HTML, v. 0.93pm6