1

I was wondering how is the python dict (dictionary/hashtable) implemented. Particularly, if I write something like

my_dict = {"key": {"key: {"key": "value"}}}

what possibly does the python interpreter do? I want to know the internal working of it.

Does it treat each dictionary as an object (mostly yes)? If so, is the hashing same for same keys across different dictionaries? For e.g.

dict1 = {"key": "value", "k": "v"}
dict2 = {"key": [1, 2.], "k": "value"}

How different would the look-up for the keys in these 2 distinct dicts be? Also, how does it decide the size of the buckets? Or is similar to the handling of list size? Hope you get my question. Thanks!

EDIT - No, I am not asking how hash-tables work. I know that part.

shad0w_wa1k3r
  • 12,955
  • 8
  • 67
  • 90
  • Are you asking if the hash function that is called for `dict1["key"]` is identical to the hash function that is called for `dict2["key"]`? – Robᵩ Nov 05 '13 at 18:01
  • 1
    See the answer to this question: http://stackoverflow.com/questions/13514716/overriding-pythons-hashing-function-in-dictionary – Robᵩ Nov 05 '13 at 18:04
  • Can I flag my own question as duplicate? Because, I [found an answer](http://stackoverflow.com/a/9022835/2689986) but the question was not that specific. – shad0w_wa1k3r Nov 05 '13 at 18:09
  • All major implementations of python are open source. Feel free to look at the source. – Marcin Nov 05 '13 at 19:23
  • Oops, I went too far in saying 'internal implementations'. I was asking for theoretical/descriptive explanations (not actual code) (got it in the duplicate questions). – shad0w_wa1k3r Nov 05 '13 at 19:25

2 Answers2

5

Python dictionary are basically the implementation of hash tables. Now, the question is what is hash table? From wikipedia, short and sweet answer:

a hash table (also hash map) is a data structure used to implement an associative array, a structure that can map keys to values A hash table uses a hash function to compute an index into an array of buckets or slots, from which the correct value can be found.

These two questions in SO covers some of the things you are interested in:

How are Python's Built In Dictionaries Implemented

How can Python dict have multiple keys with same hash?

I would be repeating the same things if I go any further.

Community
  • 1
  • 1
Jack_of_All_Trades
  • 10,942
  • 18
  • 58
  • 88
0

The specification reads

Another useful data type built into Python is the dictionary (see Mapping Types — dict). Dictionaries are sometimes found in other languages as “associative memories” or “associative arrays”. It is best to think of a dictionary as an unordered set of key: value pairs, with the requirement that the keys are unique (within one dictionary). A pair of braces creates an empty dictionary: {}. Placing a comma-separated list of key:value pairs within the braces adds initial key:value pairs to the dictionary; this is also the way dictionaries are written on output.

And places items in memory in a deterministic fashion through a hash function

megawac
  • 10,953
  • 5
  • 40
  • 61