Python dictionary is the most flexible built-in data structure type in Python besides list. A list is an ordered combination of objects, and a dictionary is an unordered collection of objects. The difference between the two is that the elements in the dictionary are accessed by keys, not by offsets.

Using subscript index in the list can quickly get the corresponding value, so we need to do two things:

• How to calculate a unique value for a key
• How to distribute this unique value uniformly and uniquely in a fixed length list

How to calculate a unique value for a key

Because the key of the dictionary is immutable and can be hashed, we can use the hash function to calculate the unique hash value corresponding to the key.

How to distribute this unique value uniformly and uniquely in a fixed length list

Hash hash is an algorithm that can map large data sets to fixed length data sets, so we can hash the hash values calculated above. Obviously, there will be hash conflicts after hashing. Therefore, we need to deal with this conflict, and the unique value can be uniformly and uniquely distributed. At this time, there are two methods to deal with hash conflict: zipper method and open address method

<!--more-->

Zipper method

Put K and V pairs with the same hash address in the same single linked list. The following two functions are implemented

• Put function: put(slots, key, value), which is used to insert data into the dictionary
• Get function: get(slots, key), which is used to read data from the dictionary.

You can also implement more functions, such as dict.keys()

#!/usr/bin/env python
# coding=utf-8

slots = []
slotsNum = 32
for _ in range(32):
    slots.append([])

def put(slots, key, value):
    i = hash(key) % slotsNum
    pos = -1
    for pos, (k, v) in enumerate(slots[i]):
        if key == k:
            break
    else:
        slots[i].append((key, value))
    if pos >= 0 and pos < len(slots[i]):
        slots[i][pos] = (key, value)

def get(slots, key):
    i = hash(key) % slotsNum
    for k, v in slots[i]:
        if key == k:
            return v
    else:
        raise KeyError(key)        # Throw an exception when it does not exist

put(slots, 'a', 1)
print(get(slots, 'a'))
put(slots, 'b' ,2)
print(get(slots, 'b'))
put(slots, 'a', 3)
print(get(slots, 'a'))

These two functions are encapsulated into classes

class Dict:
    def __init__(self, num):
        self.__solts__ = []
        self.num = num
        for _ in range(num):
            self.__solts__.append([])

    def put(self, key, value):
        i = hash(key) % self.num
        for p, (k, v) in enumerate(self.__solts__[i]):
            if k == key:
                break
        else:
            self.__solts__[i].append((key, value))
            return
        self.__solts__[i][p] = (key, value)

    def get(self, key):
        i = hash(key) % self.num
        for k, v in self.__solts__[i]:
            if k == key:
                return v
        raise KeyError(key)

    # keys function
    def keys(self):
        ret = []
        for solt in self.__solts__:
            for k, _ in solt:
                ret.append(k)
        return ret

After being encapsulated into a class, the usage method is similar to the dict provided by Python

Open address method

When the Python dictionary is implemented internally, the method to deal with hash conflicts is the open address method, which will be supplemented later

• Notes on Python source code analysis - Chapter 5 dict objects in Python
• Python dictionary implementation

Remember to give me some praise!

Carefully sorted out the video courses and e-books in all directions of the computer, including introduction, advanced and actual combat. According to the reasonable classification of the catalogue, you can always find the learning materials you need. What are you waiting for? Pay attention to the download!!!

Never forget, there must be an echo. My friends, please give me a compliment. Thank you very much.

I am a bright brother in the workplace, YY Senior Software Engineer, four years of working experience, and a slash programmer who refuses to be a leader.

Listen to me, more progress, program life is a shuttle

If you are lucky enough to help you, please give me a "like" and give me attention. If you can comment and encourage me, I will be very grateful.

List of articles in the workplace: More articles

All my articles and answers are in cooperation with the copyright protection platform. The copyright belongs to brother Liang in the workplace. Unauthorized reprinting must be investigated!