probably weird or stupid newbie dictionary question

H

hawkmoon269

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
 
D

Diez B. Roggisch

hawkmoon269 said:
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.
 
S

Stefan Behnel

hawkmoon269 said:
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

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
 
N

Nick Craig-Wood

Diez B. Roggisch said:
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!
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,900
Latest member
Nell636132

Latest Threads

Top