dict(字典)的一种实现

下面是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.