High Performance Python, 3rd Edition

Chapter 4. Dictionaries and Sets

Questions You’ll Be Able to Answer After This Chapter

• What are dictionaries and sets good for?

• How are dictionaries and sets the same?

• What is the overhead when using a dictionary?

• How can I optimize the performance of a dictionary?

• How does Python use dictionaries to keep track of namespaces?

Sets and dictionaries are ideal data structures to be used when your data has no intrinsic order (except for insertion order) but does have a unique object that can be used to reference it (the reference object is normally a string, but it can be any hashable type). This reference object is called the key, while the data is the value. Dictionaries and sets are almost identical, except that sets do not actually contain values: a set is simply a collection of unique keys. As the name implies, sets are very useful for doing set operations (such as union, intersection and difference).

Note

A hashable type is one that implements both the __hash__ magic function and either __eq__ or __cmp__. All native types in Python already implement these, and any user classes have default values. See “Hash Functions and Entropy” for more details.

We saw in the previous chapter that for lists with no intrinsic order we are limited to O(n) lookup time. Dictionaries and sets give us O(1) lookups based on the arbitrary index. In addition, like lists/tuples, dictionaries and sets have O(1) insertion time.¹ As we will see in “How Do Dictionaries and Sets Work?”, this speed is accomplished through the use of an open address hash table as the underlying data structure.

However, there is a cost to using dictionaries and sets. First, they generally take up a larger footprint in memory. Also, although the complexity for insertions/lookups is O(1), the actual speed depends greatly on the hashing function that is in use. If the hash function is slow to evaluate, any operations on dictionaries or sets will be similarly slow.

Let’s look at an example. Say we want to store contact information for everyone in the phone book. We would like to store this in a form that will make it simple to answer the question “What is Ada Lovelace’s phone number?” in the future. With lists, we would store the phone numbers and names sequentially and scan through the entire list to find the phone number we required, as shown in Example 4-1.

Example 4-1. Phone book lookup with a list

def find_phonenumber(phonebook, name):
    for n, p in phonebook:
        if n == name:
            return p
    return None

phonebook = [
    ("Ada Lovelace", "555-555-5555"),
    ("Sophie Wilson", "212-555-5555"),
]

ada = find_phonenumber(phonebook, 'Ada Lovelace')
print(f"Ada Lovelace's phone number is {ada}")

Note

We could also do this by sorting the list (at a O(n log n) penalty) and using the bisect module (from Example 3-4) in order to get O(log n) performance on subsequent lookups.

With a dictionary, however, we can simply have the “index” be the names and the “values” be the phone numbers, as shown in Example 4-2. This allows us to simply look up the value we need and get a direct reference to it, instead of having to read every value in our dataset.

Example 4-2. Phone book lookup with a dictionary

phonebook = {
    "Ada Lovelace": "555-555-5555",
    "Sophie Wilson" : "212-555-5555",
}
print(f"Ada Lovelace's phone number is {phonebook['Ada Lovelace']}")

For large phone books, the difference between the O(1) lookup of the dictionary and the O(n) time for linear search over the list (or, at best, the O(log n) complexity with the bisect module) is quite substantial.

Tip

Create a script that times the performance of the list-bisect method versus a dictionary for finding a number in a phone book. How does the timing scale as the size of the phone book grows?

If, on the other hand, we wanted to answer the question “How many unique first names are there in my phone book?” we could use the power of sets. Recall that a set is simply a collection of unique keys—this is the exact property we would like to enforce in our data. This is in stark contrast to a list-based approach, where that property needs to be enforced separately from the data structure by comparing all names with all other names. Example 4-3 illustrates.

Example 4-3. Finding unique names with lists and sets

def list_unique_first_names(phonebook):
    unique_first_names = []
    for name, phonenumber in phonebook: 
        first_name, last_name = name.split(" ", 1)
        for unique in unique_first_names: 
            if unique == first_name:
                break
        else:
            unique_first_names.append(first_name)
    return len(unique_first_names)

def set_unique_first_names(phonebook):
    unique_first_names = set()
    for name, phonenumber in phonebook: 
        first_name, last_name = name.split(" ", 1)
        unique_first_names.add(first_name) 
    return len(unique_first_names)

phonebook = [
    ("Ada Lovelace", "555-555-5555"),
    ("Sophie Wilson", "212-555-5555"),
    ("Grace Hopper", "647-555-5555"),
    ("Emmy Noether", "202-555-5555"),
    ("Guido van Rossum", "301-555-5555"),
]

print("Number of unique names from set method:", set_unique_first_names(phonebook))
print("Number of unique names from list method:", list_unique_first_names(phonebook))

,

    We must go over all the items in our phone book, and thus this loop costs O(n).

Here, we must check the current name against all the unique names we have already seen. If it is a new unique name, we add it to our list of unique names. We then continue through the list, performing this step for every item in the phone book.

For the set method, instead of iterating over all unique names we have already seen, we can simply add the current name to our set of unique names. Because sets guarantee the uniqueness of the keys they contain, if you try to add an item that is already in the set, that item simply won’t be added. Furthermore, this operation costs O(1).

The list algorithm’s inner loop iterates over unique_first_names, which starts out as empty and then grows, in the worst case, when all names are unique, to be the size of phonebook. This can be seen as performing a linear search for each name in the phone book over a list that is constantly growing. Thus, the complete algorithm performs as O(n log n).

On the other hand, the set algorithm has no inner loop; the set.add operation is an O(1) process that completes in a fixed number of operations regardless of how large the phone book is (there are some minor caveats to this, which we will cover while discussing the implementation of dictionaries and sets). Thus, the only nonconstant contribution to the complexity of this algorithm is the loop over the phone book, making this algorithm perform in O(n).

When timing these two algorithms using a phonebook with 10,000 entries and all unique first names, we see how drastic the difference between O(n) and O(n log n) can be:

>>> %timeit list_unique_first_names(large_phonebook)
1.3 s ± 8.83 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

>>> %timeit set_unique_first_names(large_phonebook)
2.32 ms ± 55.6 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In other words, the set algorithm gave us a 560x speedup! In addition, as the size of the phonebook grows, the speed gains increase (we get a 4,300x speedup with a phonebook with 100,000 entries).

How Do Dictionaries and Sets Work?

Dictionaries and sets use hash tables to achieve their O(1) lookups and insertions. This efficiency is the result of a very clever usage of a hash function to turn an arbitrary key (i.e., a string or object) into an index for a list. The hash function and list can later be used to determine where any particular piece of data is right away, without a search. By turning the data’s key into something that can be used like a list index, we can get the same performance as with a list. In addition, instead of having to refer to data by a numerical index, which itself implies some ordering to the data, we can refer to it by this arbitrary key.

Warning

In this chapter we will focus on the implementation details of dictionaries, however sets are very similar. Algorithmically they work in the same way, however several small details are different (for example, the exact growth pattern is different, the existence of an ordered list of keys, etc). We will focus on dictionaries and point out differences to set objects when necessary.

Inserting and Retrieving

To create a hash table from scratch, we start with some allocated memory, similar to what we started with for arrays. For an array, if we want to insert data, we simply find the first unused bucket and insert our data there (and resize if necessary). For hash tables, we must first figure out the placement of the data in this contiguous chunk of memory.

The placement of the new data is contingent on two properties of the data we are inserting: the hashed value of the key and how the value compares to other objects. This is because when we insert data, the key is first hashed and masked so that it turns into an effective index in an array.² The mask makes sure that the hash value, which can take the value of any integer, fits within the allocated number of buckets. So if we have allocated 8 blocks of memory and our hash value is 28975, we consider the bucket at index 28975 & 0b111 = 7. If, however, our dictionary has grown to require 512 blocks of memory, the mask becomes 0b111111111 (and in this case, we would consider the bucket at index 28975 & 0b11111111).

Now we must check if this bucket is already in use. If it is empty, we can insert the key and the value into this block of memory. We store the key so that we can make sure we are retrieving the correct value on lookups. If it is in use and the value of the bucket is equal to the value we wish to insert (a comparison done with the cmp built-in), then the key/value pair is already in the hash table and we can return. However, if the values don’t match, we must find a new place to put the data.

Note

As an extra optimization for dictionaries, Python appends the key/value data into a standard array and then stores only the index into this array in the hash table. This allows us to reduce the amount of memory used by 30–95%.³ In addition, this gives us the interesting property that we keep a record of the order which new items were added into the dictionary (which, since Python 3.7, is a guarantee that all dictionaries give).

To find the new index, we compute it using a simple linear function, a method called probing. Python’s probing mechanism adds a contribution from the higher-order bits of the original hash (recall that for a table of length 8 we considered only the last three bits of the hash for the initial index, through the use of a mask value of mask = 0b111 = bin(8 - 1)). Using these higher-order bits gives each hash a different sequence of next possible hashes, which helps to avoid future collisions.

There is a lot of freedom when picking the algorithm to generate a new index; however, it is quite important that the scheme visits every possible index in order to evenly distribute the data in the table. How well distributed the data is throughout the hash table is called the load factor and is related to the entropy of the hash function. The pseudocode in Example 4-4 illustrates the calculation of hash indices used in CPython 3.7. This also points towards an interesting fact about hash tables: most of the storage space they have is empty!

Example 4-4. Dictionary lookup sequence

def index_sequence(key, mask=0b111, PERTURB_SHIFT=5):
    perturb = hash(key) 
    i = perturb & mask
    yield i
    while True:
        perturb >>= PERTURB_SHIFT
        i = (i * 5 + perturb + 1) & mask
        yield i

hash returns an integer, while the actual C code in CPython uses an unsigned integer. Because of that, this pseudocode doesn’t replicate exactly the behavior in CPython; however, it is a good approximation.

This probing is a modification of the naive method of linear probing. In linear probing, we simply yield the values i = (i * 5 + perturb + 1) & mask, where i is initialized to the hash value of the key.⁴ An important thing to note is that linear probing deals only with the last several bits of the hash and disregards the rest (i.e., for a dictionary with eight elements, we look only at the last three bits since at that point the mask is 0x111). This means that if hashing two items gives the same last three binary digits, we will not only have a collision, but also the sequence of probed indices will be the same. The perturbed scheme that Python uses will start taking into consideration more bits from the items’ hashes to resolve this problem.

A similar procedure is done when we are performing lookups on a specific key: the given key is transformed into an index, and that index is examined. If the key in that index matches (recall that we also store the original key when doing insert operations), then we can return that value. If it doesn’t, we keep creating new indices using the same scheme, until we either find the data or hit an empty bucket. If we hit an empty bucket, we can conclude that the data does not exist in the table.

Figure 4-1 illustrates the process of adding data into a hash table. Here, we chose to create a hash function that simply uses the first letter of the input. We accomplish this by using Python’s ord function on the first letter of the input to get the integer representation of that letter (recall that hash functions must return integers). As we’ll see in “Hash Functions and Entropy”, Python provides hashing functions for most of its types, so typically you won’t have to provide one yourself except in extreme situations.

Figure 4-1. The resulting hash table from inserting with collisions

Insertion of the key Barcelona causes a collision, and a new index is calculated using the scheme in Example 4-4. This dictionary can also be created in Python using the code in Example 4-5.

Example 4-5. Custom hashing function

class City(str):
    def __hash__(self):
        return ord(self[0])

# We create a dictionary where we assign arbitrary values to cities
data =  {
    City("Rome"): 'Italy',
    City("San Francisco"): 'USA',
    City("New York"): 'USA',
    City("Barcelona"): 'Spain',
}

In this case, Barcelona and Rome cause the hash collision (Figure 4-1 shows the outcome of this insertion). We see this because, for a dictionary with four elements, we have a mask value of 0b111. As a result, Barcelona and Rome will try to use the same index:

hash("Barcelona") = ord("B") & 0b111
                  = 66 & 0b111
                  = 0b1000010 & 0b111
                  = 0b010 = 2

hash("Rome") = ord("R") & 0b111
             = 82 & 0b111
             = 0b1010010 & 0b111
             = 0b010 = 2

Exercise

Work through the following problems. A discussion of hash collisions follows:

1. Finding an element—Using the dictionary created in Example 4-5, what would a lookup on the key Johannesburg look like? What indices would be checked?

2. Deleting an element—Using the dictionary created in Example 4-5, how would you handle the deletion of the key Rome? How would subsequent lookups for the keys Rome and Barcelona be handled?

3. Hash collisions—Considering the dictionary created in Example 4-5, how many hash collisions could you expect if 500 cities, with names all starting with an uppercase letter, were added into a hash table? How about 1,000 cities? Can you think of a way of lowering the number of collisions?

For 500 cities, there would be approximately 474 dictionary elements that collided with a previous value (500 – 26), with each hash having 500 / 26 = 19.2 cities associated with it. For 1,000 cities, 974 elements would collide, and each hash would have 1,000 / 26 = 38.4 cities associated with it. This is because the hash is based simply on the numerical value of the first letter, which can take only a value from A–Z, allowing for only 26 independent hash values. This means that a lookup in this table could require as many as 38 subsequent lookups to find the correct value. To fix this, we must increase the number of possible hash values by considering other aspects of the city in the hash. The default hash function on a string considers every character in order to maximize the number of possible values. See “Hash Functions and Entropy” for more explanation.

Deletion

When a value is deleted from a hash table, we cannot simply write a NULL to that bucket of memory. This is because we have used NULLs as a sentinel value while probing for hash collisions. As a result, we must write a special value that signifies that the bucket is empty, but there still may be values after it to consider when resolving a hash collision. So if “Rome” was deleted from the dictionary, subsequent lookups for “Barcelona” will first see this sentinel value where “Rome” used to be and instead of stopping, continue to check the next indices given by the index_sequence. These empty slots can be written to in the future and are removed when the hash table is resized.

Resizing

As more items are inserted into the hash table, the table itself must be resized to accommodate them. It can be shown that a table that is no more than two-thirds full will have optimal space savings while still having a good bound on the number of collisions to expect. Thus, when a table reaches this critical point, it is grown. To do this, a larger table is allocated (i.e., more buckets in memory are reserved), the mask is adjusted to fit the new table, and all elements of the old table are reinserted into the new one. This requires recomputing indices, since the changed mask will change the resulting index. As a result, resizing large hash tables can be quite expensive! However, since we do this resizing operation only when the table is too small, as opposed to doing it on every insert, the amortized cost of an insert is still O(1).⁵

The general sizing rules for dictionaries (and sets) is that,

1. The dictionary is always less that 2/3rds full (3/5ths full for sets)

2. The size of the dictionary is always a power of 2

By default, the smallest size of a dictionary or set is 8 (that is, if you are storing only three values, Python will still allocate eight buckets), and it will resize by 3x if the dictionary is more than two-thirds full ⁶. So when trying to insert a sixth element, the dictionary will first realize that this will cause it to be overallocated (more than 2/3rds full). To calculate it’s new size, it finds the smallest power of two that will accomodate 3x it’s current size. So in order to hold 15 items we should resize the dictionary to hold 16 items. resized to accommodate 18 elements. At this point, the old data can be copied into the new dictionary and the new element can be added as well.

Figure 4-2. Graph showing how many extra elements are being allocated to accommodate a dictionary of a given size. Dictionaries will always be at least 1/3rd empty but will also have even more space allocated to make sure the total size is a power of 2. The graph looks similar for sets, however the rate of increase changes at the 50,000 element mark.

On the 11th insertion, this process happens again. We try resizing to 32 elements (the smallest power of 2 that holds 3x10 elements). This gives the following possible sizes:

8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072

It is important to note that resizing can happen to make a hash table larger or smaller. That is, if sufficiently many elements of a hash table are deleted, the table can be scaled down in size. However, resizing happens only during an insert. So, counterintuitively, if you have a dictionary that you dict.pop() many items out of, you can trigger a resize (and thus save memory!) by adding a new element to the dictionary.

Hash Functions and Entropy

Objects in Python are generally hashable, since they already have built-in __hash__ and __cmp__ functions associated with them. For numerical types (int and float), the hash is based simply on the bit value of the number they represent. Tuples and strings have a hash value that is based on their contents. Lists, on the other hand, do not support hashing because their values can change. Since a list’s values can change, so could the hash that represents the list, which would change the relative placement of that key in the hash table.⁷

User-defined classes also have default hash and comparison functions. The default __hash__ function simply returns the object’s placement in memory as given by the built-in id function. Similarly, the __cmp__ operator compares the numerical value of the object’s placement in memory.

This is generally acceptable, since two instances of a class are generally different and should not collide in a hash table. However, in some cases we would like to use set or dict objects to disambiguate between items. Take the following class definition:

class Point(object):
    def __init__(self, x, y):
        self.x, self.y = x, y

If we were to instantiate multiple Point objects with the same values for x and y, they would all be independent objects in memory and thus have different placements in memory, which would give them all different hash values. This means that putting them all into a set would result in all of them having individual entries:

>>> p1 = Point(1,1)
>>> p2 = Point(1,1)
>>> set([p1, p2])
set([<__main__.Point at 0x1099bfc90>, <__main__.Point at 0x1099bfbd0>])
>>> Point(1,1) in set([p1, p2])
False

We can remedy this by forming a custom hash function that is based on the actual contents of the object as opposed to the object’s placement in memory. The hash function can be any function as long as it consistently gives the same result for the same object (there are also considerations regarding the entropy of the hashing function, which we will discuss later.) The following redefinition of the Point class will yield the results we expect:

class Point(object):
    def __init__(self, x, y):
        self.x, self.y = x, y

    def __hash__(self):
        return hash((self.x, self.y))

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

This allows us to create entries in a set or dictionary indexed by the properties of the Point object rather than the memory address of the instantiated object:

Example 4-6. Point object with a custom hash function

>>> p1 = Point(1,1)
>>> p2 = Point(1,1)
>>> set([p1, p2]) 
set([<__main__.Point at 0x109b95910>])
>>> Point(1, 1) in set([p1, p2])
True

Note that specifically only the first element, p1, gets inserted into the set object. So, if you are using this set object to keep track of existing point objects, p2 will get lost.

As alluded to when we discussed hash collisions, a custom-selected hash function should be careful to evenly distribute hash values in order to avoid collisions. Having many collisions will degrade the performance of a hash table: if most keys have collisions, we need to constantly “probe” the other values, effectively walking a potentially large portion of the dictionary to find the key in question. In the worst case, when all keys in a dictionary collide, the performance of lookups in the dictionary is O(n) and thus the same as if we were searching through a list.

If we know that we are storing 5,000 values with a custom hash function in a dictionary and we need to create a hashing function for the object we wish to use as a key, we must be aware that the dictionary will be stored in a hash table of size 16,384⁸ and thus only the last 14 bits of our hash are being used to create an index (for a hash table of this size, the mask is bin(16_384 - 1) = 0b11111111111111).

This idea of “how well distributed my hash function is” is called the entropy of the hash function. Entropy is defined as

$$S=–\sum _{i}p\left(i\right)·log\left(p\left(i\right)\right)$$

where p(i) is the probability that the hash function gives hash i. It is maximized when every hash value has equal probability of being chosen. A hash function that maximizes entropy is called an ideal hash function since it guarantees the minimal number of collisions.

Note

For the most part, creating your own custom hash function is unnecessary. Generally, you can use the python hash function but indicating specifically which parts of the object needs to be hashed (like what we did in Example 4-6). If more complex hashing is needed, there are many pre-built algorithms that provide different guarantees depending on their inputs. The hash function specifically uses the Siphash 1-3 algorithm for hashing things other than integers. ⁹

For an infinitely large dictionary, the hash function used for integers is ideal. This is because the hash value for an integer is simply the integer itself! For an infinitely large dictionary, the mask value is infinite, and thus we consider all bits in the hash value. Therefore, given any two numbers, we can guarantee that their hash values will not be the same.

However, if we made this dictionary finite, we could no longer have this guarantee. For example, for a dictionary with four elements, the mask we use is 0b111. Thus the hash value for the number 5 is 5 & 0b111 = 5, and the hash value for 501 is 501 & 0b111 = 5, and so their entries will collide.

Note

To find the mask for a dictionary with an arbitrary number of elements, N, we first find the minimum number of buckets that dictionary must have to still be two-thirds full (N * (2 / 3 + 1)). Then we find the smallest dictionary size that will hold this number of elements (8; 32; 128; 512; 2,048; etc.) and find the number of bits necessary to hold this number. For example, if N=1039, then we must have at least 1,731 buckets, which means we need a dictionary with 2,048 buckets. Thus the mask is bin(2048 - 1) = 0b11111111111.

There is no single best hash function to use when using a finite dictionary. However, knowing up front what range of values will be used and how large the dictionary will be helps in making a good selection. For example, if we are storing all 676 combinations of two lowercase letters as keys in a dictionary (aa, ab, ac, etc.), a good hashing function for this specific case would be the one shown in Example 4-7.

Example 4-7. Optimal two-letter hashing function

def twoletter_hash(key):
    offset = ord('a')
    k1, k2 = key
    return (ord(k2) - offset) + 26 * (ord(k1) - offset)

This gives no hash collisions for any combination of two lowercase letters, considering a mask of 0b1111111111 (a dictionary of 676 values will be held in a hash table of length 2,048, which has a mask of bin(2048 - 1) = 0b11111111111).

Example 4-8 very explicitly shows the ramifications of having a bad hashing function for a user-defined class—here, the cost of a bad hash function (in fact, it is the worst possible hash function!) is a 54x slowdown of lookups. This case of a bad hash function even makes the dictionary slower than using a list, which is 13% faster in this case.

Example 4-8. Timing differences between good and bad hashing functions

import string
import timeit

class BadHash(str):
    def __hash__(self):
        return 42

class GoodHash(str):
    def __hash__(self):
        """
        This is a slightly optimized version of twoletter_hash
        """
        return ord(self[1]) + 26 * ord(self[0]) - 2619

bad_dict = set()
good_dict = set()
list_control = list()
for i in string.ascii_lowercase:
    for j in string.ascii_lowercase:
        key = i + j
        bad_dict.add(BadHash(key))
        good_dict.add(GoodHash(key))
        list_control.append(key)

bad_time = timeit.repeat(
    "key in bad_dict",
    setup = "from __main__ import bad_dict, BadHash; key = BadHash('zz')",
    repeat = 3,
    number = 1_000_000,
)
good_time = timeit.repeat(
    "key in good_dict",
    setup = "from __main__ import good_dict, GoodHash; key = GoodHash('zz')",
    repeat = 3,
    number = 1_000_000,
)
list_time = timeit.repeat(
    "key in list_control",
    setup = "from __main__ import list_control; key = 'zz'",
    repeat = 3,
    number = 1_000_000,
)

print(f"Min lookup time for bad_dict: {min(bad_time)}")
print(f"Min lookup time for good_dict: {min(good_time)}")
print(f"Min lookup time for list_control: {min(list_time)}")

# Results:
#    Min lookup time for bad_dict: 10.160735580000619
#    Min lookup time for good_dict: 0.18675472999893827
#    Min lookup time for list_control: 8.958332514994254

Exercise

1. Show that for an infinite dictionary (and thus an infinite mask), using an integer’s value as its hash gives no collisions.

2. Show that the hashing function given in Example 4-7 is ideal for a hash table of size 1,024. Why is it not ideal for smaller hash tables?

Note

Readers of previous editions of this book may have realized that the section on scoping in namespaces is suspicciously missing from this version of the book. Recent changes to how cpython does namespace lookups brings the benchmarks so close to one-another that the conclusions simply no longer hold. However, we still feel it is important to point out that this has changed as yet another reminder to always and continually profile your code. If you can, add profiling metrics to your unit tests to encode performance assumptions so as projects live past cpython changes, or library changes, or hardware changes, the performance characteristics you depend on are still valid.

Wrap-Up

Dictionaries and sets provide a fantastic way to store data that can be indexed by a key. The way this key is used, through the hashing function, can greatly affect the resulting performance of the data structure. Furthermore, understanding how dictionaries work gives you a better understanding not only of how to organize your data but also of how to organize your code, since dictionaries are an intrinsic part of Python’s internal functionality.

In the next chapter we will explore generators, which allow us to provide data to code with more control over ordering and without having to store full datasets in memory beforehand. This lets us sidestep many of the possible hurdles that we might encounter when using any of Python’s intrinsic data structures.

¹ As we will discuss in “Hash Functions and Entropy”, dictionaries and sets are very dependent on their hash functions. If the hash function for a particular datatype is not O(1), any dictionary or set containing that type will no longer have its O(1) guarantee.

² A mask is a binary number that truncates the value of a number. So 0b1111101 & 0b111 = 0b101 = 5 represents the operation of 0b111 masking the number 0b1111101. This operation can also be thought of as taking a certain number of the least-significant digits of a number.

³ The discussion that led to this improvement can be found at https://oreil.ly/Pq7Lm.

⁴ The value of 5 comes from the properties of a linear congruential generator (LCG), which is used in generating random numbers.

⁵ Amortized analysis looks at the average complexity of an algorithm. This means that some inserts will be much more expensive, but on average, inserts will be O(1).

⁶ For sets, the limit is 3/5ths full and the resize factor is reduced to 2x once the set has grown to at least 50,000 elements

⁷ More information about this can be found at https://oreil.ly/g4I5-.

⁸ 5,000 values need a dictionary that has at least 8,333 buckets. The first available size that can fit this many elements is 16,384.

⁹ https://en.wikipedia.org/wiki/SipHash