[Tutor] Hash map and dictionaries

[Steven D'Aprano]

On Sun, Dec 01, 2013 at 09:10:42PM +0530, Reuben wrote:
> Hi
> 
> Question 1:
> -----------------
> I would like to know the concept of hash map. Additionally,  I got to know
> that hash maps are equivalent to dictionaries in python.
> 
> I would like to understand the relationship between dictionaries and hash
> map better.

Pythin dictionaries are hash maps. A hash map is another name for a hash 
table.

I already answered your earlier question about dictionaries with a 
description of hash tables:

https://mail.python.org/pipermail/tutor/2013-November/098436.html

If anything is unclear, please ask.



> Question 2:
> ------------------
> It is also said that in a list of may be 10,000 elements(specifically
> integers), hash maps would be a better option to find the occurrence of
> repetitive integers
> 
> How can this be implemented using dictionaries for a list of 10,000 integer
> elements?

You don't use dicts as lists. If you want a list, use a list:

# list of five integers
[2, 7, 19, 25, 3]

Where hash tables are good is when you want to map a "key" to a "value", 
or another way to say the same thing, to *associate* a key to a value. 
Think of a paper dictionary, where every word is followed by a 
definition -- the key is the word itself, the value is the definition.

There are many names for the same thing:

dict
hash table
hash map
associative array
symbol table
mapping

For example, if you want to associate (map) a person's name to their 
birthday:

{"Susan": "1985-12-03",
 "Fred": "1960-03-15",
 "George": "1973-10-27",
 }


So if you want to map a number to some other piece of data, a dict is 
must better than a list. Searching a list normally depends on how many 
items are in the list -- if there are 10,000 items in the list, you will 
need to inspect 5000 items on average. Searching a dict normally takes 
exactly the same amount of time whether there is one item or 10000 
items.

e.g.:

{2: "two",
 7: "seven",
 19: "nineteen",
 25: "twenty-five",
 3: "three",
 # and ten thousand more
 }


versus:

[(2, "two"), 
 (7, "seven"), 
 (19, "nineteen"), 
 (25: "twenty-five"),
 (3, "three"),
 # and ten thousand more
 ]

the dict will be thousands of times faster, on average.


-- 
Steven