Re: probably weird or stupid newbie dictionary question
Diez B. Roggisch <[EMAIL PROTECTED]> wrote: > But what happens in case of a hash code clash? Then a list of (key, values) > is stored, and for a passed key, each key in that list is additionally > compared for being equal to the passed one. So another requirement of > hashable objecst is the comparability. In java, this is done using the > equals method. > > So in the end, the actual mapping of key, value looks like this: > > hash(key) -> [(key, value), ] Thats called hashing with chaining. See Knuth: Sorting and Searching if you want to know more! -- Nick Craig-Wood <[EMAIL PROTECTED]> -- http://www.craig-wood.com/nick -- http://mail.python.org/mailman/listinfo/python-list
Re: probably weird or stupid newbie dictionary question
Very. Thanks much. :-) h -- http://mail.python.org/mailman/listinfo/python-list
Re: probably weird or stupid newbie dictionary question
That makes sense. Thanks. :-) h -- http://mail.python.org/mailman/listinfo/python-list
Re: probably weird or stupid newbie dictionary question
hawkmoon269 schrieb:
some other languages' hash table (Perl's, for instance). But FMU a
dictionary's keys are *themselves* hashed so that a hash table exists
that maps hashed key values to keys in the dictionary.
I guess you're mixing up the terms "hashing" and "storing in a hash-table".
When we hash a dictionary key
>>> a = hash(key)
then we retrieve a value that is used to refer to the value that we want
to store. Ok? :)
1>>> mydict = {}
2>>> mydict['mykey'] = 'somevalue'
3>>> mydict['mykey']
'somevalue'
What happened, was:
1) mydict becomes a dictionary
2a) mydict hashed the key 'mykey' and got an integer value. Strings know
how to calculate a hash value for themselves, that value is retrieved via
a call to hash('mykey')
2b) mydict then stored the value 'myvalue' at a location that the hashed
key refers to (don't care how that is done)
3) mydict hashes the key 'mykey' and retrieves an integer. It looks at the
location that that int refers to and finds the value 'somevalue' that was
previously stored there. It returns that value.
A bit clearer now?
Stefan
--
http://mail.python.org/mailman/listinfo/python-list
Re: probably weird or stupid newbie dictionary question
hawkmoon269 wrote: > I've read in several places that a Python dictionary is analagous to > some other languages' hash table (Perl's, for instance). But FMU a > dictionary's keys are *themselves* hashed so that a hash table exists > that maps hashed key values to keys in the dictionary. ISTM, then, > that the analogy is at least somewhat faulty...except for the fact that > a dictionary's keys could themselves be hashed redundantly...i.e., the > values to be used as keys could be hashed, inserted into the dictionary > (and mapped to their values, of course), and they would then be hashed > (again) behind the scenes...IOW, ISTM that a dictionary is correctly > understood generally as a mapping (as documentation indicates) and > *could* be understood as a special case hash table itself...Is that > accurate? You're having a point that dicts are mappings. But you're somewhat lost on your understanding of what gets hashed why and when. Hashing is _one_ way of accomplishing a mapping - and usually the easiest, as it has the minimum of requirements for the supported key objects. Other techniques rely on a total order of keys - which can sometimes not be reached. So it is used in most mapping implementations, and for some languages like perl, the method of mapping became the synonym or name for the mapping itself - thus the name "hash". Take for example java: There one usually takes HashMap as the implementation for the Map interface - TreeMap forces the objects to be either Comparable or having an explicit comparison function be passed. OTH every Object in java has a hashCode method that will allow its usage in a HashMap But what happens in case of a hash code clash? Then a list of (key, values) is stored, and for a passed key, each key in that list is additionally compared for being equal to the passed one. So another requirement of hashable objecst is the comparability. In java, this is done using the equals method. So in the end, the actual mapping of key, value looks like this: hash(key) -> [(key, value), ] HTH. -- Regards, Diez B. Roggisch -- http://mail.python.org/mailman/listinfo/python-list
probably weird or stupid newbie dictionary question
I've read in several places that a Python dictionary is analagous to some other languages' hash table (Perl's, for instance). But FMU a dictionary's keys are *themselves* hashed so that a hash table exists that maps hashed key values to keys in the dictionary. ISTM, then, that the analogy is at least somewhat faulty...except for the fact that a dictionary's keys could themselves be hashed redundantly...i.e., the values to be used as keys could be hashed, inserted into the dictionary (and mapped to their values, of course), and they would then be hashed (again) behind the scenes...IOW, ISTM that a dictionary is correctly understood generally as a mapping (as documentation indicates) and *could* be understood as a special case hash table itself...Is that accurate? h -- http://mail.python.org/mailman/listinfo/python-list
