How is a dictionary structured in Python?

Python's dictionary (dict) is a mutable, unordered collection of items, where each item is a key-value pair. Keys must be immutable (strings, numbers, tuples), unique, and values can be of any type. It is implemented as a hash table for fast access to elements.

Key features:

• Hashing: Keys are hashed for quick lookup. This allows access to a value by key in average O(1) time.
• Unordered: Until Python 3.7, the order of items in a dictionary was not guaranteed. Starting with Python 3.7, dictionaries preserve the insertion order.
• Mutable: You can add, delete, and modify key-value pairs after creating the dictionary.
• Unique keys: Each key in the dictionary can only appear once. When adding an element with an existing key, the old value is overwritten.

Internal structure (in Python 3.7+):

A dictionary stores data in two structures:

1. Array of entries: Contains references to key objects, hashes of keys, and references to value objects. This array is flat and used for quick access.
2. Hash table (index array): Contains indices into the entries array. The size of this table is usually a power of two.

When adding a pair (key, value):

1. The hash of the key is computed.
2. The hash determines the presumed index in the hash table.
3. If the cell is free, the index is stored in the entries array.
4. If the cell is occupied (hash collision), a collision resolution algorithm (e.g., linear probing) is used to find the next free cell.

When searching for a value by key:

1. The hash of the sought key is computed.
2. The initial index in the hash table is determined by the hash.
3. The hash and the key in the record at the found index are compared.
4. If hashes match but keys differ (collision), the search continues using the collision resolution algorithm.
5. When a record with matching key and hash is found, the corresponding value is returned.

Example:

# Creating a dictionary
my_dict = {"apple": 1, "banana": 2, "orange": 3}

# Accessing a value by key
value = my_dict["banana"] # 2

# Adding a new element
my_dict["grape"] = 4

# Modifying an existing key's value
my_dict["apple"] = 10

# Deleting an element
del my_dict["orange"]

# Representation in a simplified form
# Array of entries:
# [(hash("apple"), "apple", 10), (hash("banana"), "banana", 2), (hash("grape"), "grape", 4)]
# Hash table (simplified, indices in the entries array):
# [1 (for banana), None, 0 (for apple), 2 (for grape), None, ...]