Question

Explain of how the implementation of a Python dictionary works in 8-10 sentences. In particular, how are keys and values stored? What hash function is used? How are collisions resolved? How is the size/capacity of the dictionary maintained?

Answer 1

Dictionary in Python:

Dictionary in Python is a data structure where values are stored as unordered, key-value pairs, and indexed. They are written using curly brackets.

Storing keys and values:

To store the keys/values in a dictionary, strings, numbers, or tuples are used as keys. Value can be of any type. This is because values can change but keys are not changeable.

For example:

dictExample={"fruit":"apple", "vegetable":"capsicum"}

Hash function used:

In Python hash tables are used for dictionaries. Hash tables store the key-value pairs in unordered fashion. Keys are unique and are used to identify the value.

Resolving collisions:

Since the dictionaries are created and implemented with hash tables, the collisions are handled with probing.

Probing or linear probing avoids collision by looking for the next available slot for the value.

Size/capacity maintenance of dictionary:

While implementing a dictionary, the size of the dictionary is not kept in it. Dictionary only allocates memory when there is a need to grow or add more key-value pairs. Also, the size maintenance is not necessary as the pairs are not kept in the memory but only reference is used for the value when required.