[Tutor] Hash map and dictionaries

[Devin Jeanpierre]

On Sun, Dec 1, 2013 at 7:40 AM, Reuben <reuben.dlink at gmail.com> 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.

Hash maps are a class of data structures which associate values with
keys. They exhibit constant time average case behavior if every
possible key is equally likely. They usually have O(n) worst case
behavior. Python dictionaries are an implementation of hash maps using
a particular choice of algorithms.

>
> 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 would use sets, not dictionaries.

x = set(range(HUGE_NUM)) # "1 in x" is as fast as "-1 in x"
x = list(range(HUGE_NUM)) # "1 in x" is much faster than "-1 in x"

Sets use hash tables internally too, but they don't associate a value
with the keys. They just mark whether or not the key is present.

-- Devin