probably weird or stupid newbie dictionary question

[Diez B. Roggisch]

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