search in dict as hashing
def lookup(d, key):
'''dictionary lookup is done in three steps:
1. A hash value of the key is computed using a hash function.
2. The hash value addresses a location in d.data which is
supposed to be an array of "buckets" or "collision lists"
which contain the (key,value) pairs.
3. The collision list addressed by the hash value is searched
sequentially until a pair is found with pair[0] == key. The
return value of the lookup is then pair[1].
'''
h = hash(key) # step 1
cl = d.data[h] # step 2
for pair in cl: # step 3
if key == pair[0]:
return pair[1]
else:
raise KeyError, "Key %s not found." % key