<jupyter_start><jupyter_text>Setup Sample data to store into dictionaries:<jupyter_code>from pprint import pprint


keys = 'guido sarah barry rachel tim'.split()
val1 = 'blue orange green yellow red'.split()
val2 = 'austin dallas tuscon reno portland'.split()
val3 = 'apple banana orange pear peach'.split()
hashes = list(map(abs, map(hash, keys)))
entries = list(zip(hashes, keys, val1))
comb_entries = list(zip(hashes, keys, val1, val2, val3))<jupyter_output><empty_output><jupyter_text>Database Way * The data is dense.* The search is linear.* Once we get to size of list or 2 or more, the database way is worss than modern dictionaries.<jupyter_code>def database_linear_search():
    pprint(list(zip(keys, val1, val2, val3)))
database_linear_search()<jupyter_output>[('guido', 'blue', 'austin', 'apple'),
 ('sarah', 'orange', 'dallas', 'banana'),
 ('barry', 'green', 'tuscon', 'orange'),
 ('rachel', 'yellow', 'reno', 'pear'),
 ('tim', 'red', 'portland', 'peach')]<jupyter_text>LISP * Store lists of pairs<jupyter_code>def association_lists():
    pprint([
        list(zip(keys, val1)),
        list(zip(keys, val2)),
        list(zip(keys, val3)),
    ])
association_lists()<jupyter_output>[[('guido', 'blue'),
  ('sarah', 'orange'),
  ('barry', 'green'),
  ('rachel', 'yellow'),
  ('tim', 'red')],
 [('guido', 'austin'),
  ('sarah', 'dallas'),
  ('barry', 'tuscon'),
  ('rachel', 'reno'),
  ('tim', 'portland')],
 [('guido', 'apple'),
  ('sarah', 'banana'),
  ('barry', 'orange'),
  ('rachel', 'pear'),
  ('tim', 'peach')]]<jupyter_text>Separate Chaining * Use multiple "buckets" to reduce the linear search by a constant factor.* The higher the number of buckets is, the lower look-up time is.* As the size of dictionary gets bigger, the performance decreases.<jupyter_code>def separate_chaining(n):
    buckets = [[] for _ in range(n)]
    for pair in entries:
        hashvalue, key, value = pair
        i = hashvalue % n
        buckets[i].append(pair)
#     pprint(buckets)
    return buckets
separate_chaining(2)
separate_chaining(4)<jupyter_output><empty_output><jupyter_text>Dynamic Resizing * Periodically resize the dictionary so that it will never get more than 2/3 full.* Faster resizing store hash values in the list so that it could avoid calculating them again, which is very expensive.<jupyter_code>def faster_resize(old_buckets, n):
    n *= 2
    new_buckets = [[] for _ in range(n)]
    for old_bucket in old_buckets:
        if not old_bucket:
            continue
        
        for hashvalue, key, val in old_bucket:
            bucket = new_buckets[hashvalue % n].append((hashvalue, key, val))
    pprint(new_buckets)
faster_resize(separate_chaining(4), 4)<jupyter_output>[[(1289971815486709344, 'barry', 'green')],
 [(357032982473426601, 'sarah', 'orange')],
 [(1693333087535225058, 'guido', 'blue')],
 [],
 [(8468031612747961020, 'tim', 'red')],
 [],
 [(3534391722751367630, 'rachel', 'yellow')],
 []]<jupyter_text>Faster Matching When searching a bucket, we need to know whether the target key is found. We could test whether `key == target_key` but that can be slow because any object can define a complex or interesting `__eu__()` method.  The solution is to have two fast early-outs that can bypass equality testing in some circumstances.  * if two variables point to the same object, they are equal. "identiy implies equality"* For hash tables to work at all, they follow the invariant, "if two objects are equal, then their hash values as equal as well." The contra-positive statement is "if two objects have unequal hashes, then the objects must be unequal as well"<jupyter_code>def fast_match(key, target_key):
    if key is target_key:
        return True
    if hash(key) != hash(target_key):
        return False
    return key == target_key<jupyter_output><empty_output><jupyter_text>Open Addressing The problem with separate chaining is that a great deal of space is wasted by having pointers to many separate lists.  The solution is to make the table more dense and to cope with collisions using linear probing.<jupyter_code>def open_addressing_linear(n):
    table = [None] * n
    for hashvalue, key, value in entries:
        i = hashvalue % n
        while table[i] is not None:
            i = (i + 1) % n
        table[i] = (hashvalue, key, value)
    pprint(table)
open_addressing_linear(5)<jupyter_output>[(3534391722751367630, 'rachel', 'yellow'),
 (357032982473426601, 'sarah', 'orange'),
 (8468031612747961020, 'tim', 'red'),
 (1693333087535225058, 'guido', 'blue'),
 (1289971815486709344, 'barry', 'green')]<jupyter_text>Deleted Entries The problem is that removing a key leaves a "hole" so that linear probing isunable to find keys that had collisions.  The solution is to mark the slot with as `DUMMY` entry to serve as a placeholder. During the key-insertion phase, we try to re-use that dummy entry whenever possible.  Thei slookup scheme is known as "Knuth - Algorithm D"<jupyter_code>def lookup(h, key):
    freeslot = None
    i = h % n
    while True:
        entry = table[i]
        if entry == FREE:
            return entry if freeslot is None else table[freeslot]
        elif entry == DUMMY:
            if freeslot is None:
                freeslot = i
        elif fast_match(key, entry.key):
            return entry
        i = (i + 1) % n<jupyter_output><empty_output><jupyter_text>Multiple Hashing The problem with linear porbing is that we can end up with catastrophic linear pile-up.  The solution is "re-hash" to other locations based on both the full values (all 64 bits) and on the number of probes.* To make sure that probe sequence eventurally visite every possible slot, we use a simple linear_congruential random number generator thta provably eventually visits each slot, `i = 5 * i +1`* To make sure we use all the bits of the hash, we gradually shift in 5 bits at a time.<jupyter_code>def open_addressing_multihash(n):
    table = [None] * n
    for hashvalue, key, value in entries:
        perturb = hashvalue
        i = hashvalue % n
        while table[i] is not None:
            print('{} collided with {}'.format(key, table[i][1]))
            i = (5 * i + perturb + 1) % n
            perturb >>= 5
        table[i] = (hashvalue, key, value)
    pprint(table)
open_addressing_multihash(7)<jupyter_output>sarah collided with guido
[None,
 None,
 (357032982473426601, 'sarah', 'orange'),
 (1289971815486709344, 'barry', 'green'),
 (8468031612747961020, 'tim', 'red'),
 (3534391722751367630, 'rachel', 'yellow'),
 (1693333087535225058, 'guido', 'blue')]<jupyter_text>Early-Out For Lookups The problem is that the core of Python relies heavily on dict lookups but many times that same lookup must be repeated because the dictionary has mutated.  The solution was created by <NAME> in "PEP 509 - Add a private version to dict". The idea is to update an interanl dict version number every time a dictionary is updated. The lets us do a fast version check to avoid slower repeated lookups  Compact Dict The problem is that dict tables have a lot of empty space interanlly for every entry which includes a hash, key and value.The solution is to store the hash/key/value table densely and make a separate, tiny spared table of indices to vector into the dense table.<jupyter_code>def compact_and_ordered(n):
    table = [None] * n
    for pos, entry in enumerate(entries):
        h = perturb = entry[0]
        i = h % n
        while table[i] is not None:
            i = (5 * i + perturb + 1) % n
            perturb >>= 5
        table[i] = pos
    pprint(entries)
    pprint(table)
compact_and_ordered(8)<jupyter_output>[(1693333087535225058, 'guido', 'blue'),
 (357032982473426601, 'sarah', 'orange'),
 (1289971815486709344, 'barry', 'green'),
 (3534391722751367630, 'rachel', 'yellow'),
 (8468031612747961020, 'tim', 'red')]
[2, 1, 0, None, 4, None, 3, None]<jupyter_text>Key-Sharing Dict The problem with previous design is if you have several dictionaries with the same keys, then there is unneccessary repetition os the keys, hash values and indices.The solution was proposed by <NAME> in "PEP 412 - Key-Sharing Dictionary"<jupyter_code>def shared_and_compact(n):
    table = [None] * n
    for pos, entry in enumerate(comb_entries):
        h = perturb = entry[0]
        i = h % n
        while table[i] is not None:
            i = (5 * i + perturb + 1) % n
            perturb >>= 5
        table[i] = pos
    pprint(entries)
    pprint(table)
shared_and_compact(8)<jupyter_output>[(1693333087535225058, 'guido', 'blue'),
 (357032982473426601, 'sarah', 'orange'),
 (1289971815486709344, 'barry', 'green'),
 (3534391722751367630, 'rachel', 'yellow'),
 (8468031612747961020, 'tim', 'red')]
[2, 1, 0, None, 4, None, 3, None]
{'fraction_non_alphanumeric': 0.11663611365719523, 'fraction_numerical': 0.06072410632447296, 'mean_word_length': 3.976624857468643, 'pattern_counts': {'":': 0, '<': 40, '<?xml version=': 0, '>': 46, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '11', 'dir': 'jupyter-structured-clean-dedup', 'id': '59993', 'license': 'MIT', 'n_tokens_mistral': 3168, 'n_tokens_neox': 2788, 'n_words': 1001, 'path': 'Modern Python Dictionaries by Raymond Hettinger.ipynb', 'repo_name': 'ujhuyz0110/PyCon2017Notes', 'size': '8742'}