下面是python中字典的一种实现，用list数据结构实现字典。具体是这样的：[[(key1,value1),(key2,value2),...],[],[],...]
内部每一个hash地址是一个list,存放hash地址相同的(key,value)对。
### dict代码
~~~
def Map(num_buckets=256):
"""Initializes a Map with the given number of buckets."""
aMap = []
for i in range(0, num_buckets):
aMap.append([])
return aMap
def Map_hash(aMap, key):
"""Given a key this will create a number and then convert it to
and index for the aMap's buckets."""
return hash(key) % len(aMap)
def Map_get_bucket(aMap, key):
"""Given a key, find the bucket where it would go."""
bucket_id = Map_hash(aMap, key)
return aMap[bucket_id]
def Map_get_slot(aMap, key, default=None):
"""Returns the index, key, and value of a slot found in a bucket."""
bucket = Map_get_bucket(aMap, key)
for i, kv in enumerate(bucket):#bucket=[[k1,v1],[k2,v2],...]
k, v = kv
if key == k:
return i, k, v#ex1:i=0,k=k1,v=v1
return -1, key, default
def Map_get(aMap, key, default=None):
"""Gets the value in a bucket for the given key, or the default."""
i, k, v = Map_get_slot(aMap, key, default=default)
return v
def Map_set(aMap, key, value):
"""Sets the key to the value, replacing any existing value."""
bucket = Map_get_bucket(aMap, key)
i, k, v = Map_get_slot(aMap, key)
if v:
bucket[i] = (key, value)#key/value pair
else:
bucket.append((key, value))
def Map_delete(aMap, key):
"""Deletes the given key from the Map."""
bucket = Map_get_bucket(aMap, key)
for i in xrange(len(bucket)):
k, v = bucket[i]
if key == k:
del bucket[i]
break
def Map_list(aMap):
"""Prints out what's in the Map."""
for bucket in aMap:
if bucket:
for k, v in bucket:
print k, v
# The tests that it will work.
jazz = Map()
Map_set(jazz, 'Miles Davis', 'Flamenco Sketches')
# confirms set will replace previous one
Map_set(jazz, 'Miles Davis', 'Kind Of Blue')
Map_set(jazz, 'Duke Ellington', 'Beginning To See The Light')
Map_set(jazz, 'Billy Strayhorn', 'Lush Life')
print "---- List Test ----"
Map_list(jazz)
print "---- Get Test ----"
print Map_get(jazz, 'Miles Davis')
print Map_get(jazz, 'Duke Ellington')
print Map_get(jazz, 'Billy Strayhorn')
print "---- Delete Test ----"
print "**Goodbye Miles"
Map_delete(jazz, "Miles Davis")
Map_list(jazz)
print "**Goodby Duke"
Map_delete(jazz, "Duke Ellington")
Map_list(jazz)
print "**Goodbye Billy"
Map_delete(jazz, "Billy Strayhorn")
Map_list(jazz)
print "**Goodbye Pork Pie Hat"
Map_delete(jazz, "Charles Mingus")
~~~
Map_hash()函数的解释如下:
This deceptively simple function is the core of how a dict (Map) works. What it does is uses the built-in Python hash function to convert a string to a number. Python uses this function for its own dict data structure, and I'm just reusing it. You should fire up a Python console to see how it works. Once I have a number for the key, I then use the % (modulus) operator and thelen(aMap) to get a bucket where this key can go. As you should know, the % (modulus) operator will divide any number and give me the remainder. I can also use this as a way of limiting giant numbers to a fixed smaller set of other numbers. If you don't get this then use Python to explore it.
