How does python implement mapping?

Dictionary dict is an important data structure in Python. In the dictionary, each key corresponds to a value. The relationship between keys and values ​​is called mapping. It can also be said that each key is mapped to a value. superior.

Map is a more general data type, specifically a dictionary in Python. (Recommended learning: Python video tutorial)

When using a dictionary, we must have a question, how does it map to the value through the key? How does it know who the value of this key is?

So we came up with this idea:

Use a list to store key-value objects one by one. When searching, just traverse the list and find the key you are looking for. key, take out the value value in the object.

This idea is very simple, we can implement it quickly:

Here we first introduce some related abstract base classes, Mapping and MutableMapping, which are in the collections module for us to implement customization map class. Mapping includes all immutable methods in dict, and the MutableMapping extension includes all variable methods, but neither of them includes the five core special methods: getitem, setitem, delitem, len, and iter. In other words, our goal is to implement these five core methods so that the data structure can be used.

from collections import MutableMapping

class MyMap(MutableMapping):

    class item():

        def __init__(self,key,value):
            self.key = key
            self.value = value

        def __eq__(self, other):
            return self.key == other.key

        def __ne__(self, other):
            return self.key != other.key

    def __init__(self):
        self.table = []

    def __getitem__(self, item):
        for i in self.table:
            if i.key == item:
                return i.value
        raise KeyError('Key Error: '+ repr(item))

    def __setitem__(self, key, value):
        for i in self.table:
            if i.key == key:
                i.value = value
                return
        self.table.append(self.item(key,value))

    def __delitem__(self, key):
        for n,i in enumerate(self.table):
            if i.key == key:
                self.pop(n)
                return
        raise KeyError('Key Error: '+ repr(key))

    def __len__(self):
        return len(self.table)

    def __iter__(self):
        for i in self.table:
            yield i.key

The above method is very simple, but it is not very efficient. We need to traverse the list every time to find the index of the key, so the time complexity is O(n).

For more Python related technical articles, please visit the Python Tutorial column to learn!

The above is the detailed content of How does python implement mapping?. For more information, please follow other related articles on the PHP Chinese website!