Introduction

In python dictionaries and sets are used to save unique, unordered(ordered from 3.7 python version explained below), mutable (also immutable - frozen sets) and quick retrieval elements. In any python program there are number of dicts used even when the program is not using it explicitly such as CPython uses dictionary lookup for any attribute or class or global variable and more. As this plays an important role it has been highly optimized by the python core developers, especially for search, add and delete operations. Hash tables are the key element behind the implementation of dicts and sets, making these data structures performance efficient. Hash tables are powerful and are also used in solving real life problems such indexing of database tables, caching, name lookups and so on.

Dictionary

A dictionary is composed of a series of key-value mapping elements. The keys and values can be of mixed types like string, integer

Create

Below are few methods to create a dict

a = dict(one=1, two=2, three=3)
b = {'one': 1, 'two': 2, 'three': 3}
c = dict(zip(['one', 'two', 'three'], [1, 2, 3]))
d = dict([('one', 1), ('two', 2), ('three', 3)])
e = dict({'one': 1, 'two': 2, 'three': 3})

Possible key types, are all the immutable types such as str, bytes, numeric types

Update

The update() method inserts the specified items to the dictionary. The specified items can be a dictionary, or an iterable object with key value pairs.
Eg:
car = {
"brand": "Ford",
"model": "Mustang",
"year": 1964
}

car.update({"color": "White"})

print(car)

Output:
{'brand': 'Ford', 'model': 'Mustang', 'year': 1964, 'color': 'White'}

The pop() method removes the specified item from the dictionary and the value of the removed item is the return value of the pop() method.
Eg:
car = {
"brand": "Ford",
"model": "Mustang",
"year": 1964
}

print("Pre Removed dict:", car)

x = car.pop("model")

print("Removed value:", x)
print("Post Removed dict:", car)

Output:
Pre Removed dict: {'brand': 'Ford', 'model': 'Mustang', 'year': 1964}
Removed value: Mustang
Post Removed dict: {'brand': 'Ford', 'year': 1964}

Return the default value or None if the key does not existing, rather handling KeyError.
__missing__

The __missing__ method, is called by __getitem__() dictionary method internally if the keys doesn't exist.
The return value of __missing__() is the value returned when accessing the non existence key.

Eg:
sample_dict = {'name': 'python', 'age': 20}
print(sample_dict['location'])

Traceback (most recent call last):
File "dict_set_sample.py", line 40, in <module>
print(sample_dict['location'])
KeyError: 'location'

sample_dict = {'name': 'python', 'age': 20}
print(sample_dict.get('location'))
print(sample_dict.get('location', 'India'))

Output:
None
India

Items

The items() method returns a view object.
The view object contains the key-value pairs of the dictionary, as tuples in a list.
The view object will reflect any changes done to the dictionary.
Note: returned view object was part of version 3+, and here we have newly introduced __contains__ methods defined in python dict class to identify if the key exists in the dictionary or sets.
Eg
car = {
"brand": "Ford",
"model": "Mustang",
"year": 1964
}

x = car.items()
print(x)

car["model"] = "Figo"
print(x)

Output:
dict_items([('brand', 'Ford'), ('model', 'Mustang'), ('year', 1964)])
dict_items([('brand', 'Ford'), ('model', 'Figo'), ('year', 1964)])

Keys

Method keys() returns a view object of all the available first level keys in the dictionary.
The view object contains the keys of the dictionary, as a list.
The view object will reflect any changes done to the dictionary.
Eg:
car = {
"brand": "Ford",
"model": "Mustang",
"year": 1964,
"details": {
"wheels": 4,
"doors": 2,
}
}

x = car.keys()
print(x)

Output:
dict_keys(['brand', 'model', 'year', 'details'])

Values

values() is an inbuilt method in Python programming language that returns a view object.
The view object contains the values of the dictionary, as a list.
The view object will reflect any changes done to the dictionary.
Eg:
car = {
"brand": "Ford",
"model": "Mustang",
"year": 1964,
"details": {
"wheels": 4,
"doors": 2,
}
}

x = car.values()

print(x)

Output:
dict_values(['Ford', 'Mustang', 1964, {'wheels': 4, 'doors': 2}])

Filters

Here we will just see some sample examples, but very good blog describes much more possibilities

https://learnpython.com/blog/filter-dictionary-in-python/

Filter dict with only partial matching values from dictionary:
cars = {
"ford_figo": 1990,
"ford_focus": 1991,
"ford_feista": 1992
}

print("Before drop of the column", cars)

filter_str = "ford_feista"
cars = dict(filter(lambda item: filter_str not in item[0], cars.items()))

print("After drop of the column", cars)

Output:
Before drop of the column {'ford_figo': 1990, 'ford_focus': 1991, 'ford_feista': 1992}
After drop of the column {'ford_figo': 1990, 'ford_focus': 1991}
Filter and save empty values in dict
cars = {
"ford_figo": 1990,
"ford_focus": 1991,
"ford_feista": 1992,
"ford_dummy": 0
}

print("Before drop of the column", cars)

cars = dict(filter(lambda item: not item[1], cars.items()))

print("After drop of the column", cars)

Output:
Before drop of the column {'ford_figo': 1990, 'ford_focus': 1991, 'ford_feista': 1992, 'ford_dummy': 0}
After drop of the column {'ford_dummy': 0}

Delete

To delete the keys and delete the dictionary.
Eg:
dict1 = {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5}
print(dict1)
# Delete a single element
del dict1['a']
print("post delete key dict1:", dict1)
# Delete all elements in the dictionary
dict1.clear()
print("post clear dict1: ", dict1)
dict2 = {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5}
# Delete the dictionary
del dict2
print("complete dict delete dict2: ", dict2)

Output:
{'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5}
post delete key dict1: {'b': 2, 'c': 3, 'd': 4, 'e': 5}
post clear dict1: {}
Traceback (most recent call last):
File "dict_sample.py", line 134, in <module>
print("complete dict delete dict2: ", dict2)
NameError: name 'dict2' is not defined

Fromkeys

The fromkeys() method returns a dictionary with the specified keys and the specified value.
It creates a new dictionary from the given sequence with the specific value else creates with None value assigned.
Eg:
types = ('flower', 'diamond', 'heart')
cards = dict.fromkeys(types)
print("Create a dict with None values:", cards)

qty = [10]
cards = dict.fromkeys(types, qty)
print("Create a dict with default values:", cards)

qty.append(3)
print("View the created dict with updated list values:", cards)

qty.pop(0)
print("View the created dict with updated list values:", cards)

Output:
Create a dict with None values: {'flower': None, 'diamond': None, 'heart': None}
Create a dict with default values: {'flower': [10], 'diamond': [10], 'heart': [10]}
View the created dict with updated list values: {'flower': [10, 3], 'diamond': [10, 3], 'heart': [10, 3]}
View the created dict with updated list values: {'flower': [3], 'diamond': [3], 'heart': [3]}

Setdefault

setdefault() returns the value of a key (if the key is in dictionary).
Else, it inserts a key with the default value to the dictionary.
Provides a significant speedup by avoiding redundant key lookups.
Eg:
d = {'a': 97, 'b': 98, 'c': 99, 'd': 100}
ret_value = d.setdefault('e', 120)
print("New key which does not exists in the dict, value: {}, dict: {}", ret_value, d)
ret_value = d.setdefault('e', 140)
print("New key which exists in the dict, value: {}, dict: {}", ret_value, d)

Output:
New key which does not exists in the dict, value: {}, dict: {} 120 {'a': 97, 'b': 98, 'c': 99, 'd': 100, 'e': 120}
New key which exists in the dict, value: {}, dict: {} 120 {'a': 97, 'b': 98, 'c': 99, 'd': 100, 'e': 120}

Defaultdict

A defaultdict is configured to create items on demand whenever a missing key is searched.
Internally it works by calling the callable provided to produce s default value.
The callable that produces the default values is held in an instance attribute called default_factory.
Eg:

Create a defaultdict with a list constructor as default_factory

index = collections.defaultdict(list)

If the key is not found, an empty list is assigned to the new key.
If no default_factory is provided, the usual KeyError is raised for the missing keys.

Dict Comprehensions

Transforming dictionary from one form to another using dict comprehensions.
Dict comprehensions make the code easier to read, avoid loops and performance benefits.
Explained the performance boost reason with dis output:

https://stackoverflow.com/questions/52542742/why-is-this-loop-faster-than-a-dictionary-comprehension-for-creating-a-dictionar

Eg:
dict1 = {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5}
# Double each value in the dictionary
double_dict1 = {k:v*2 for (k,v) in dict1.items()}
print(double_dict1)

Output:
{'a': 2, 'b': 4, 'c': 6, 'd': 8, 'e': 10}
Very good reference sharing multiple examples:

https://www.datacamp.com/tutorial/python-dictionary-comprehension

Call by Reference

Call by reference means that the argument passed to the function is a reference to a variable that already exists in memory rather than an independent copy of that variable. Hence any changes made to the variable will be impacted even after the function execution completes.
Dictionary passed as argument is call by reference.
Eg:
dict1 = {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5}

def change(dict_val):
print("inside change function before change:", dict_val)
dict_val['new'] = 100
print("inside change function after change:", dict_val)

print("inside main function before change:", dict1)
change(dict1)
print("inside main function after change:", dict1)

Output:
inside main function before change: {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5}
inside change function before change: {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5}
inside change function after change: {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5, 'new': 100}
inside main function after change: {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5, 'new': 100}

Variations

UserDict

User can implement own dictionary by extending UserDict, which works like standard dict.
It is preferred to use subclass from UserDict rather than from dict, as the builtin has some implementation shortcuts that end up forcing to override, which can be easily inherited from UserDict.
Eg:
# Python program to demonstrate Userdict
from collections import UserDict

# Creating a Dictionary where
# deletion is not allowed
class MyDict(UserDict):

# Function to stop deletion
# from dictionary
def __del__(self):
raise RuntimeError("Deletion not allowed")

# Function to stop pop from
# dictionary
def pop(self, s = None):
raise RuntimeError("Deletion not allowed")

# Function to stop popitem
# from Dictionary
def popitem(self, s = None):
raise RuntimeError("Deletion not allowed")

# Driver's code
d = MyDict({'a':1,
'b': 2,
'c': 3})

print("Original Dictionary")
print(d)

d.pop(1)

Output:
Original Dictionary
{'a': 1, 'b': 2, 'c': 3}
Traceback (most recent call last):
File "dict_sample.py", line 154, in <module>
d.pop(1)
File "dict_sample.py.py", line 139, in pop
raise RuntimeError("Deletion not allowed")
RuntimeError: Deletion not allowed
Exception ignored in: <function MyDict.__del__ at 0x10955b8b0>
Traceback (most recent call last):
File "dict_sample.py.py", line 134, in __del__
RuntimeError: Deletion not allowed

OrderedDict

Maintains the order of the insertion.
The popitem method of an OrderedDict pops the first item by default, but if called by popitem(last=True) will return the last item added.
Ordered dictionary is designed to remember the order of items, which is defined by the insertion order of keys.
When the value of a certain key is changed, the position of the key remains unchanged.
Syntax: OrderedDict()
Eg:
from collections import OrderedDict

numbers = OrderedDict()

numbers["one"] = 1
numbers["two"] = 2
numbers["three"] = 3

print(numbers) # OrderedDict([('one', 1), ('two', 2), ('three', 3)])
Memory Allocation:

As like dictionary the memory is allocated which grows linearly based on the number of keys added, but in ordered dictionary to maintain the order nearly 50% more memory is used to preserve the order of the items.
Code:

from collections import OrderedDict
import sys

ordd = OrderedDict()
d = {}

for x in range(15):
ordd[x] = x
d[x] = x
print("ordered dict:", sys.getsizeof(ordd), "\t", "dict:", sys.getsizeof(d))

'''
Output:
-------
ordered dict: 392 dict: 232
ordered dict: 424 dict: 232
ordered dict: 456 dict: 232
ordered dict: 488 dict: 232
ordered dict: 520 dict: 232
ordered dict: 744 dict: 360
ordered dict: 776 dict: 360
ordered dict: 808 dict: 360
ordered dict: 840 dict: 360
ordered dict: 872 dict: 360
ordered dict: 1312 dict: 640
ordered dict: 1344 dict: 640
ordered dict: 1376 dict: 640
ordered dict: 1408 dict: 640
ordered dict: 1440 dict: 640
'''

References:

https://lerner.co.il/2019/05/12/python-dicts-and-memory-usage/

Methods

move_to_end: method is used to move an existing key of the dictionary either to the end or to the beginning. Eg:
from collections import OrderedDict

ord_dict = OrderedDict().fromkeys('GeeksForGeeks')
print("Original Dictionary")
print(ord_dict)

# Move the key to end
ord_dict.move_to_end('G')
print("\nAfter moving key 'G' to end of dictionary :")
print(ord_dict)

# Move the key to beginning
ord_dict.move_to_end('k', last = False)
print("\nAfter moving Key in the Beginning :")
print(ord_dict)

Output:
Original Dictionary
OrderedDict([('G', None), ('e', None), ('k', None), ('s', None), ('F', None), ('o', None), ('r', None)])

After moving key 'G' to end of dictionary :
OrderedDict([('e', None), ('k', None), ('s', None), ('F', None), ('o', None), ('r', None), ('G', None)])

After moving Key in the Beginning :
OrderedDict([('k', None), ('e', None), ('s', None), ('F', None), ('o', None), ('r', None), ('G', None)])
reversed: reverse the order of the dict keys stored. Eg:
from collections import OrderedDict

x = {'d':'four', 'e':'five', 'a':'one'}

sample_reversed_dict = OrderedDict(reversed(list(x.items())))
print("The reversed order dictionary : " + str(sample_reversed_dict))

Output:
The reversed order dictionary : OrderedDict([('a', 'one'), ('e', 'five'), ('d', 'four')])

Counter

Holds the count for each key, adding a new key will create a single count and updating the existing key will increase the count.
Eg:
from collections import Counter

counter_dict_sample = Counter("helloworld")
print(counter_dict_sample)

Output:
Counter({'l': 3, 'o': 2, 'h': 1, 'e': 1, 'w': 1, 'r': 1, 'd': 1})

ChainMap

Holds the list of dictionaries, where for key search will be performed based on the order of the dictionaries stored.
Eg: Interpreters use nested scopes, where each mapping represents a scope context.

pylookup = ChainMap(locals(), globals(), vars(builtins)

MappingProxyType

Builds a read-only dictionary instance.

Performance

Time complexity for querying: O(1)
Time complexity for storing: O(n)

Calculating the count is going to slow down a Dictionary; it will take O(n) time complexity to calculate the counts for all keys (because each key will have to be hit at least once in order to append it's count to the running count stored in the value).

Space complexity for storing: O(n) (During Hash Collision more than O(n))
Let's look into a sample to see the performance list vs dict.
Code:

import timeit

def find_number_in_list(lst, number):
    if number in lst:
        return True
    else:
        return False

short_list = list(range(100))
start = timeit.default_timer()
find_number_in_list(short_list, 1)
stop = timeit.default_timer()
print("--- short_list %s seconds ---" % (stop - start))

long_list = list(range(10000000))
start = timeit.default_timer()
find_number_in_list(long_list, 1)
stop = timeit.default_timer()
print("--- long_list %s seconds ---" % (stop - start))

def find_number_in_dict(dct, number):
    if number in dct.keys():
        return True
    else:
        return False

short_dict = {x:x*5 for x in range(1,100)}
start = timeit.default_timer()
find_number_in_dict(short_dict, 1)
stop = timeit.default_timer()
print("--- short_dict %s seconds ---" % (stop - start))

long_dict = {x:x*5 for x in range(1,10000000)}
find_number_in_dict(long_dict, 1)
stop = timeit.default_timer()
print("--- long_dict %s seconds ---" % (stop - start))

Output

>> python list_vs_dict_time.py
--- short_list 1.0299999999990872e-06 seconds ---
--- long_list 4.7639999999904425e-06 seconds ---
--- short_dict 2.97399999998893e-06 seconds ---
--- long_dict 1.768262919 seconds ---

The fastest way to repeatedly lookup data with millions of entries in Python is using dictionaries. Because dictionaries are the built-in mapping type in Python thereby they are highly optimized. However, we have a typical space-time tradeoff in dictionaries and lists. Dict still use more memory than lists, since you need to use space for the keys and the lookup as well, while lists use space only for the values.
In general O(1) to find the element in the dictionary. Though when this is hash collision we cannot say its always O(1).

Set

Set is a collection of unique objects. Set elements needs to be hashable. Frozen sets are part of sets which are immutable.

Create

Below are few methods to create a set

a = set([1, 2, 3])
b = {1, 2, 3} #Set literal

Author from Fluent Python explains the set create using set literals are faster as calling set constructor requires to build a list and finally call set.
Where as set literal directly calls specialized BUILD_SET bytecode

Set doesn't support index operations as it is not built as list but using hash.

s = {1, 2, 3}
print(s[0])

Traceback (most recent call last): File "dict_set_sample.py", line 44, in <module> print(s[0]) TypeError: 'set' object is not subscriptable

Frozen set

Immutable version of set.
Eg:

cars = set(['ford', 'renault', 'tata'])
print(cars)

cars.add("kia")
print(cars)

frozen_cars = frozenset(['ford', 'renault', 'tata'])
print(frozen_cars)

frozen_cars.add("kia")
print(frozen_cars)

Output:
{'tata', 'renault', 'ford'}
{'tata', 'renault', 'kia', 'ford'}
frozenset({'tata', 'renault', 'ford'})
Traceback (most recent call last):
File "sample.py", line 121, in <module>
frozen_cars.add("kia")
AttributeError: 'frozenset' object has no attribute 'add'

Set comprehensions

Similar to any list/dict comprehensions, we have few different types of sample explained in the below blog - #veryhandy

https://www.pythonforbeginners.com/basics/set-comprehension-in-python

curSet = set([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
newSet = {element*3 for element in curSet}
print("The Current set is:")
print(curSet)
print("The Newly Created set is:")
print(newSet)

Output:
The Current set is:
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
The Newly Created set is:
{3, 6, 9, 12, 15, 18, 21, 24, 27, 30}

Set methods

s.add(e) - Adds element e to s
s.clear() - Remove all the elements of s
s.copy() - Shallow copy of s
s.discard(e) - Remove element e from s if it is present
s.pop() - Remove element and return an element from s, raising KeyError if s is empty. However pop method removes the last element of the set and set itself is not ordered one needs to be cautious using this as any element could be removed.
s.remove(e) - Remove element e from s, raising KeyError if e not in s
s.isdisjoint(z) - Returns True if no elements in common from s and z

Sort

sorted(s) gives the sorts the set values, and returns the ordered output
Eg:

s = {3, 4, 2, 1}
print(sorted(s))

[1, 2, 3, 4]

Set operators

As the name suggests sets are ideally useful for performing set operations.
Set operations as infix operators are useful to make the code easier to read and reason.
Examples:

s & z: s.__and__(z) - Intersection of s and z
s | z: s.__or__(z) - Union of s and z
s - z: s.__sub__(z) - Difference between s and z
s ^ z: s.__xor__(z) - Symmetric difference
e in s: s.__contains__(e) - Element e is present in s
s < z: s.__le__(z) - Validates s is a subset of the z set
s <= z: s.__lt__(z) - Validates s is proper subset of the z set
s > z: s.__ge__(z) - Validates s is a super set of the z set
s >= z: s.__gt__(z) - Validates s is proper super set of the z set
s =& z: Intersection of s and z, s is updated

Performance

Sample performance validation to check the values in
Code:

def return_unique_values_using_list(values):
    unique_value_list = [] 
    for val in values:
       if val not in unique_value_list: 
           unique_value_list.append(val) 
    return unique_value_list

def return_unique_values_using_set(values):
    unique_value_set = set() 
    for val in values:
        unique_value_set.add(val) 
    return unique_value_set

import time
id = [x for x in range(0, 100000)]
start_using_list = time.perf_counter()
return_unique_values_using_list(id)
end_using_list = time.perf_counter()
print("time elapse using list: {}".format(end_using_list - start_using_list))

start_using_set = time.perf_counter()
return_unique_values_using_set(id)
end_using_set = time.perf_counter()
print("time elapse using set: {}".format(end_using_set - start_using_set))


Output:
time elapse using list: 83.99319231199999
time elapse using set: 0.01616014200000393

As we could see the performance between set vs list, set wins with a big impact.
Time complexity for querying: O(1)
Space complexity for storing: O(n)

Hash and Hash Tables

Hash and Hash Tables are two different but inter-related concepts:

Hash - Function to generate unique value for difference set of values
Hash Tables - Is a data structure to implement dictionaries and sets. Basically data structure to save key and values.

Hash

A hash value for the given key to the hash function will always return same hash value.
The efficiency of the hash function is to turn the key into an index of the list, hence the effective hash function and list can determine the particular index of data in the list without search.
Keys must be hashable objects

For user defined dict class if __eq__ method is implemented it requires __hash__ also to be implemented, as it should make a == b to True and hash(a) == hash(b) to True as well.
In Python 3, if you override __eq__, it automatically sets __hash__ to None, making the object unhashable, need to manually override __hash__ to make it hashable again.

In python we have built-in hash function, used to generate unique value for different set of values
Example of getting a same hash key running in same program, even if there is small variation the results completely differs.

print(hash("Lorem"))
print(hash("Lorem"))
print(hash("Loren"))

5675358576591581973
5675358576591581973
1733253194914647111

Each rerun will produce random values and this is expected behaviour, this is used as a countermeasure against Denial-of-Service(DoS) or Hash Flooding making it secure difficult to attack. Hash flooding occurs when the attacker knows for the list of keys the hash function returns the same hash bucket, causing collision in turn this will take long time and freeze.
If the language does not provide a randomized hash function or the application server does not recognize attacks using multi-collisions, an attacker can degenerate the hash table by sending lots of colliding keys. The algorithmic complexity of inserting n elements into the table then goes to O(n**2), making it possible to exhaust hours of CPU time using a single HTTP request. Reference: https://ocert.org/advisories/ocert-2011-003.html

>> /usr/bin/python3 -c 'print(hash("Lorem"))'
3856737851614672944
>> /usr/bin/python3 -c 'print(hash("Lorem"))'
3400600052546168698
>> /usr/bin/python3 -c 'print(hash("Lorem"))'
3757617178999059249

At the time of writing this the below algorithm is used to generate hash by built-in hash. This was designed to prevent DoS attacks against hash tables - hash flooding is a concept (also known as HashDoS) is a denial of service attack that uses hash collisions to exploit the worst-case (linear probe) runtime of hash table lookups.
Along with SipHash, Random Salt is used.

Salt, starting with Python 3.3, a random salt value is included when computing hash codes for str, bytes, and datetime objects, as documented in Issue 13703—Hash collision security issue. The salt value is constant within a Python process but varies between interpreter runs. With PEP-456, Python 3.4 adopted the SipHash cryptographic function to compute hash codes for str and bytes objects. The random salt and SipHash are security measures to prevent DoS attacks.

Python 3.8.9. Reference: https://en.wikipedia.org/wiki/SipHash

import sys
print(sys.hash_info.algorithm)
siphash24

To disable hash randomization by setting a fixed seed value through the PYTHONHASHSEED environment variable.

>> PYTHONHASHSEED=1 /usr/bin/python3 -c 'print(hash("Lorem"))'
440669153173126140
>> PYTHONHASHSEED=1 /usr/bin/python3 -c 'print(hash("Lorem"))'
440669153173126140
>> PYTHONHASHSEED=1 /usr/bin/python3 -c 'print(hash("Lorem"))'
440669153173126140

Instances of built-in mutable types—like lists, sets, and dicts—aren’t hashable. Only immutable objects are hashable (keys alone).

>> /usr/bin/python3 -c 'hash([1, 2, 3])'

Traceback (most recent call last):
File "<string>", line 1, in <module>
TypeError: unhashable type: 'list'

Hash values small integers are equal to themselves, which is an implementation detail that CPython uses for simplicity and efficiency. The hash values don’t matter as long as you can calculate them in a deterministic way.

print(hash(5))
print(hash(500000))
print(hash(50000000000))
print(hash(500000000000000000000))
print(hash(5000000000000000000000000000000))
print(hash(50000000000000000000000000000000000000000))

Output:
5 500000 50000000000 1937910009842106584 20450418580029579 24958392007006097

>>>[hash(i) for i in range(4)]
[0, 1, 2, 3]

Comment: cpython implementation dictobject.c

This isn't necessarily bad!
To the contrary, in a table of size 2**i,
taking the low-order i bits as the initial table index is extremely fast,
and there are no collisions at all for dicts indexed by a contiguous range of ints.
So this gives better-than-random behavior in common cases,
and that's very desirable.

To define a hash function for an object, define the __hash__ method.

class HashToOne(object):
def __hash__(self):
return 1
HTO = HashToOne()
print(hash(HTO))

Output:
1

To set an object as not hashable, set __hash__ to None.

class NotHashable(object):
__hash__ = None

NH = NotHashable()
print(hash(NH))

Output:
Traceback (most recent call last):
File "dict_sample.py", line 94, in <module>
print(hash(NH))
TypeError: unhashable type: 'NotHashable'

Defining own hash needs to be with caution, this could be easily misleading the actual implementation of datatypes and one may encounter subtle issues. Below article very clearly explains how it could break things and tips to resolve.

https://www.asmeurer.com/blog/posts/what-happens-when-you-mess-with-hashing-in-python/

Hash Tables

Hash tables are the engines behind dicts and sets making it faster in order to achieve O(1). Here only the keys must be hashable.
Each position in hash table is called as bucket.
Caution: Please note the below example is one of its kind to handle hash collision but there are several types of it which we will discuss later.

Credits: https://tenthousandmeters.com/blog/python-behind-the-scenes-10-how-python-dictionaries-work/

Once the hash value is generated, its passed through a mathematical process to get the bucket number to be placed. Explained the process below in the Insertion.

Simple version: bucket_index = hash(key) % number_of_buckets
Yet another version: bucket_index = hash(key) % prime_number

Hash table was initially built as sparse array which has empty cells, usually 1/3 or 1/2 would be empty cells.

Sample dict: d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'}
Code Structure:
struct dict {
long num_items;
dict_entry* items; /* pointer to array */
}
struct dict_entry {
long hash;
PyObject* key;
PyObject* value;
}
Stored as :
items = [['--', '--', '--'],
[-8522787127447073495, 'barry', 'green'],
['--', '--', '--'],
['--', '--', '--'],
['--', '--', '--'],
[-9092791511155847987, 'timmy', 'red'],
['--', '--', '--'],
[-6480567542315338377, 'guido', 'blue']]

Later after 3.6 the structure changed to make it compact and memory efficient.

Code Structure:
struct dict {
long num_items;

// new PyPy dictionary is split in two arrays
variable_int *sparse_array;
dict_entry* compact_array;
}

struct dict_entry {
long hash;
PyObject *key;
PyObject *value;
}
Stored as:
sparse_array = [None, 1, None, None, None, 0, None, 2]
compact_array = [[-9092791511155847987, 'timmy', 'red'],
[-8522787127447073495, 'barry', 'green'],
[-6480567542315338377, 'guido', 'blue']]

In the latest code structure change, the compact_array stores all the items in order of insertion the dictionary ordered is maintained, while sparse_array is a 1/2 to 2/3 full array of integers.
From: https://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html.
The integers themselves are of the smallest size necessary for indexing the compact_array. So if compact_array has less than 256 items, then sparse_array will be made of bytes; if less than 2^16, it'll be two-byte integers; and so on. This design saves quite a bit of memory.
For example, on 64bit systems we can, but almost never, use indexing of more than 4 billion elements; and for small dicts, the extra sparse_array takes very little space. For example a 100 element dict, would be on average for the original design on 64bit: 100 * 12/7 * WORD * 3 =~ 4100 bytes, while on new design it's 100 * 12/7 + 3 * WORD * 100 =~ 2600 bytes, quite a significant saving.
After reading the above example reminded me of Aniyan movie, if 1 person steals 5Rs it may not be impacting by if 5Lakhs people each steal 5Rs will be huge impact.
With the reduced memory footprint, we can also expect better cache utilization.
Only the data layout needs to change, rest all the hash table algorithms would stay the same, no change in hash functions or search order or collision statistics.
Coming back here as well, if the hash table is filled it is copied to new location or resized for extra space (same like list once the list grows it will be resized).

Hash Collision

When the hash function gives the same value for different keys is known as hash collision. Below are few methods to address hash collision.
Open Addressing: Spread the collided values in a predictable way that lets you retrieve them later. Sample several algorithms:

Cuckoo hashing
Double hashing
Hopscotch hashing
Linear probing
Quadratic probing
Robin Hood hashing

Closed Addressing: Keep the collided values in a separate data structure to search through. Also known as separate chaining.
Coalesced hashing: Combines the ideas behind both open and closed addressing into one algorithm.

Insertion

In a hash table for each item saved it contains two fields, hash mapping a reference to the key and a reference to the value of the item. For sets it is only the value.
For insert of key into the dict

hash value is calculated using the built-in hash() function
hash value is then performed an "and" operation for creating mask value so that it turns into an effective index to fit in an array (or bucket)
if we have allocated 8 blocks of memory and our hash value is 28975, we consider the bucket at index 28975 & 0b111 = 7, however if the dictionary has grown to require 512 blocks of memory, then the mask becomes 0b111111111 and would consider the bucket at index 28975 & 0b11111111
check if the returned index is already in use, if not insert the key and the value in to the block of memory
if already in use and the key matches the given key update the value
else if there is a collision meaning the hash function generated same hash value for two different keys, in such scenario to compute new index simple linear function is used called probing
hash collision (perturb)

Hash table with collision

Credits: https://www.oreilly.com/library/view/high-performance-python/9781449361747/ch04.html

To find the position where it should be based on the hash value; then, compare the hash value and key of the element in this position to the hash table to see if it is equal to the element that needs to be found.
If they are equal, return directly; if they are not, then continue to search until a slot is found or an exception is thrown.

Deletion

For the delete operation, Python temporarily assigns a special value to the element at this position marking this as deleted. Order is preserved and then deletes from the compact array when the hash table is resized when many eateries needs to be cleared. Also reindexes the sparse array, as the positions changed.
It is not difficult to understand that the occurrence of hash collisions tends to reduce the speed of dictionary and set operations. Therefore, in order to ensure its efficiency, the dictionary and the hash table in the collection are usually guaranteed to have at least 2/3 of the remaining space.
With the continuous insertion of elements, when the remaining space is less than 2/3, Python will regain a larger memory space and expand the hash table.
However, in this case, all element positions in the table will be re-arranged.
Although the hash collision and the adjustment of the size of the hash table will slow down the speed, this happens very rarely. Therefore, on average, this can still ensure that the time complexity of insert, find, and delete is O(1).

Dicts has significant memory overhead

Even empty dictionary occupies more memory than list or tuples.
Sample:

import sys

sample_dict = {}
print(sample_dict, " size of empty dict", sys.getsizeof(sample_dict), type(sample_dict))

sample_list = list()
print(sample_list, " size of empty list", sys.getsizeof(sample_list), type(sample_list))

Output:
{} size of empty dict 64 <class 'dict'>
[] size of empty list 56 <class 'list'>

Though dicts require additional storage it brings in better performance. We can optimize and its the continuous process. One needs to remember optimization is the altar where maintainability is sacrificed.

Modifying the dict while iterating is not a good idea.
Set and frozenset types are also implemented with a hash table, except that each bucket holds only a reference to the element though slight variation in algorithms as dict we need to perform lookups whereas sets are used to save unique objects.

Conclusion

A dictionary is composed of a series of key-value mapping elements.
Compared with lists and tuples, the performance of dictionaries is better, especially for search, add, and delete operations. A dictionary can be completed within a constant time complexity.
A set and a dictionary are basically the same, the only difference is that a set has no key-value pairing and is a series of disordered and unique element combinations.
Source code: dictobject.c

Finally a huge round of applause to python core developers, researchers and several other behind the scene engineers who want to make python better and efficient and secure! Huge Bow!!

References and Credits

https://nolongerset.com/content/images/2020/12/key-5105878_1920.jpg
Fluent Python - Luiano Ramalho
https://github.com/python/cpython/blob/main/Objects/dictobject.c
https://stackoverflow.com/questions/52023758/list-vs-dictionary-vs-set-for-finding-the-number-of-times-a-number-appears
https://towardsdatascience.com/faster-lookups-in-python-1d7503e9cd38
https://dzone.com/articles/python-memo-2-dictionary-vs-set-1
https://www.oreilly.com/library/view/high-performance-python/9781449361747/ch04.html
https://tenthousandmeters.com/blog/python-behind-the-scenes-10-how-python-dictionaries-work/
https://realpython.com/python-hash-table/
https://www.acunetix.com/vulnerabilities/web/php-hash-collision-denial-of-service-vulnerability/
https://www.asmeurer.com/blog/posts/what-happens-when-you-mess-with-hashing-in-python/
https://www.youtube.com/watch?v=npw4s1QTmPg
https://www.geeksforgeeks.org/*/
https://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html
https://mail.python.org/pipermail/python-dev/2012-December/123028.html
https://www.fluentpython.com/extra/internals-of-sets-and-dicts/
https://www.youtube.com/watch?v=66P5FMkWoVU&t=56s

HelloWorldEngineer

Thursday, 23 March 2023

Define Manager - An Attempt

Thursday, 9 March 2023

Dictionary and Set in Python - BTS

Introduction

Dictionary

Set

Hash and Hash Tables

Conclusion

References and Credits

Scarcity Brings Efficiency: Python RAM Optimization