So hashing lists by their id instead would produce unexpected behavior such as: But lists are containers, and most other operations on them deal with them as such. If lists were hashed by id, this would certainly be valid given Python's definition of a hash function - lists with different hash values would have different ids. Of course, the obvious question is, "Why not?"Ĭonsider what kinds of hash functions could be provided for lists. That said, the simple answer to why lists cannot be used as dictionary keys is that lists do not provide a valid _hash_ method. through _eq_ or _cmp_), and must satisfy the correctness condition above. through _hash_), equality comparison (e.g. To be used as a dictionary key, an object must support the hash function (e.g. The discussion above should explain why Python requires that: Hash functions that can approximate this property well will distribute (key, value) pairs evenly across the buckets, and keep lookup time down. Thus a (very) desirable property of a hash function is that if two keys produce the same hash values, then the key objects are equivalent, that is, for all i1, i2, if hash(i1) = hash(i2), then i1 = i2 (This is trivially true because no keys have different hash values - they all have the value 1.) But this is a bad hash function because it means that all (key, value) pairs will be placed in a single list, and so each lookup will require searching this entire list.
Note that this function meets the requirements of a hash function - every time two keys have different hash values, they represent different objects. Consider what would happen with the following hash function: Otherwise, checking the hash value of a key object might make us look in the wrong bucket and thus never find the associated value.įor such a lookup algorithm to work efficiently, most buckets should have only a small number of items (preferably only one). " % keyįor such a lookup algorithm to work correctly, the hash functions provided must guarantee that if two keys produce different hash values then the two key objects are not equivalent, that is, for all i1, i2, if hash(i1) != hash(i2), then i1 != i2 data # step 2 15 for pair in cl: # step 3 16 if key = pair: 17 return pair 18 else: 19 raise KeyError, " Key %s not found. The 11 return value of the lookup is then pair. The collision list addressed by the hash value is searched 10 sequentially until a pair is found with pair = key. The hash value addresses a location in d.data which is 6 supposed to be an array of "buckets" or "collision lists" 7 which contain the (key,value) pairs.
A hash value of the key is computed using a hash function. 1 def lookup( d, key): 2 '''dictionary lookup is done in three steps: 3 1.
0 kommentar(er)
