![]() Thus, in Python, they provide a valid _hash_ method and are thus usable as dictionary keys. Note that since tuples are immutable, they do not run into the troubles of lists - they can be hashed by their contents without worries about modification. The built-in list type should not be used as a dictionary key. Having found that both ways of hashing lists have some undesirable side-effects, it should be more obvious why Python takes the stance that: Since the dictionary doesn't know when a key object is modified, such errors could only be produced at key lookup time, not at object modification time, which could make such errors quite hard to debug. Where the value 42 is no longer available because the list that hashes to the same value,, is not equivalent to the modified list, and the value that is equivalent to the modified list, does not hash to the same value. append( 3) 5 > d 6 Traceback ( most recent call last): 7 File " ", line 1, in ? 8 KeyError: 9 > d] 10 Traceback ( most recent call last): 11 File " ", line 1, in ? 12 KeyError: This could end up with unexpected errors like:ġ > l = 2 > d = 3 > d = 42 4 > l. But what should happen when a list, being used as a dictionary key, is modified? If the modification changed the hash value of the list (because it changed the contents of the list), then the list would be in the wrong "bucket" of the dictionary. So, again, the problem is not in the definition of the hash function. If lists were hashed by their contents (as tuples are), this, too, would be a valid hash function - lists with different hash values would have different contents. Using a list literal in a dictionary lookup would be pointless - it would always produce a KeyError. Looking up different lists with the same contents would produce different results, even though comparing lists with the same contents would indicate them as equivalent. 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 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |