3

If we create an empty dictionary, like: idict = {}, how many spaces are assigned for this dictionary ? I know for the list, if we initialize a list like ilist = [], it will always over-allocate the size, first is 4 space, then 8.
What about a dictionary ?

Kshitij Saraogi
  • 6,821
  • 8
  • 41
  • 71
umassjin
  • 83
  • 3
  • http://stackoverflow.com/questions/327311/how-are-pythons-built-in-dictionaries-implemented – kgwong Jul 10 '15 at 06:10
  • If we want to check the duplicate of the ASCII characters, allocate list with 256 size is cheaper or allocate a dictionary is cheaper ? – umassjin Jul 10 '15 at 06:13
  • To check duplicates a set seems more appropriate since checking membership is a typical basic operation for a set. – Jacques de Hooge Jul 10 '15 at 06:16

2 Answers2

2

Well, dictionaries don't store the actual string inside them, it works a bit like C/C++ pointers, so you only get a constant overhead in the dictionary for every element.

Testing against 

import sys
x = {}
sys.getsizeof(x)

The dictionary itself consists of a number of buckets, each containing:

  • the hash code of the object currently stored (that is not predictable from the position of the bucket due to the collision resolution strategy used)

  • a pointer to the key object a pointer to the value

  • object in total at least 12 bytes on 32bit and 24 bytes on 64bit.

The dictionary starts out with 8 empty buckets and is resized by doubling the number of entries whenever its capacity is reached (currently (2n+1)/3).

Navneet
  • 4,543
  • 1
  • 19
  • 29
  • 2
    *"The dictionary starts out with 8 empty buckets and is resized by doubling the number of entries whenever its capacity is reached."* Sort of. In fact they grow by a calculated amount when they are about 2/3 full. Here you can see the full explanation https://hg.python.org/cpython/file/tip/Objects/dictobject.c#l258 – Sam Jul 10 '15 at 07:12
0

To be honest it actually works like associative map in C++..If you have ever used C++ then..If you see the source code of Python Interpreter, you will see that it uses your heap memory section to store data to two type & use pointers to point one data to other exactly like map works in C++. In my system it is 280.. Now as @Navneet said you can use sys.getsizeof to calculate the size. But remember that it is system specific & hence your system might not give you 280bytes. Understand that if it is 280bytes, it means it uses a delicate thread of several associative pointers to store an point to the data structure

Mayukh Sarkar
  • 2,289
  • 1
  • 14
  • 38