本文参考了此文章

放代码

# Python3.6以前
class HashDict(object):
    def __init__(self):
        """
        在Python字典3.6以前,字典是无序存储的
        存储原理为使用hash散列法,将key的hash值与字典当前的长度-1取余(_first_index函数),
        得到的值将是该数据在__hash_data中的基础位置,若该位置有数据,则继续寻找下一个位置,一直找到一个空位置
        然后将需要存储的key的hash key value存到该位置处
        当字典长度不足时,则将__hash_data扩容,并对已存储的数据重新排序存储
        由于数据在__hash_data中的位置是通过hash的余数来确定的,和插入顺序无关,故是无序存储的
        """
        self.__hash_data = []  # 用以存储数据[[key的hash值, key, value], [..]]
        self._dict_len = 0
        self._extend(8)

    def _extend(self, k):
        """
        扩展字典容量
        :param k: 新增的长度
        :return:
        """
        hash_data_tem = self.__hash_data  # 缓存以前的数据
        self._dict_len += k  # 新的长度
        self.__hash_data = [None for _ in range(self._dict_len)]
        for item in hash_data_tem:
            if item:
                self._insert(item[1], item[2], item[0])

    def _insert(self, key, value, hash_key=None):
        """
        插入数据
        :param key:
        :param value:
        :param hash_key:key的hash值
        :return:
        """
        k, hash_key = self._first_index(key, hash_key)
        while k < self._dict_len:
            if not self.__hash_data[k] or self.__hash_data[k][0] == hash_key:
                self.__hash_data[k] = [hash_key, key, value]
                break
            else:
                k += 1
        else:
            self._extend(self._dict_len)
            self._insert(key, value, hash_key)

        return True

    def insert(self, key, value):
        return self._insert(key, value)

    def _first_index(self, key, hash_key=None):
        """
        获取key的hash值对应的第一个下标
        :param key:
        :param hash_key:
        :return:
        """
        hash_key = hash_key or hash(key)
        k = hash_key % (self._dict_len - 1)
        return k, hash_key

    def get(self, key):
        k, hash_key = self._first_index(key)
        while k < self._dict_len:
            if self.__hash_data[k]:
                if self.__hash_data[k][0] == hash_key:
                    return self.__hash_data[k][2]

                k += 1
            else:
                return None

# Python3.6+
class NewHashDict(object):

    def __init__(self):
        """
        在Python3.6以后,数据的存储使用两个容器存储,分别是用以存储数据的__hash_data,和用于存储位置的__hash_index,
        当插入数据时,数据依顺序插入到__hash_data数组中,得到其存储的下标,
        然后计算出key在__hash_index的hash散列法得到的第一个非空位置处将下标和hash值存储下来

        这样在遍历的时候,只需直接遍历__hash_data即可,查询时先查询__hash_index得到其在__hash_data中的坐标,然后再获取数据
        """
        self.__hash_data = []  # 用以存储数据[[key, value], [..]]
        self.__hash_index = []  # 用以存储数据在hash_data中的下标和hkey
        self._dict_len = 0
        self._extend(8)

    def _extend(self, k):
        """
        扩展字典容量
        :param k: 新增的长度
        :return:
        """
        self._dict_len += k
        self.__hash_data.extend([None for _ in range(k)])
        tmp_hash_index = self.__hash_index
        self.__hash_index = [None] * self._dict_len
        for index, item in enumerate(tmp_hash_index):
            if item:
                self._insert(index, hkey=item[1])

    def _insert(self, index, key=None, hkey=None):
        assert key or hkey
        k, hash_key = self._first_index(key=key, hash_key=hkey)
        while self.__hash_index[k] is not None:
            k += 1
            if k >= self._dict_len:
                self._extend(8)
                self._insert(index, key=key, hkey=hkey)
                return

        self.__hash_index[k] = [index, hkey]

    def insert(self, key, value):
        hkey = hash(key)
        k = 0
        while self.__hash_data[k] is not None:
            k += 1
            if k >= self._dict_len:
                self._extend(8)
                break

        self.__hash_data[k] = [key, value]
        self._insert(k, hkey=hkey)

    def _first_index(self, key, hash_key=None):
        """
        获取key的hash值对应的第一个下标
        :param key:
        :param hash_key:
        :return:
        """
        hash_key = hash_key or hash(key)
        k = hash_key % (self._dict_len - 1)
        return k, hash_key

    def get(self, key):
        k, hkey = self._first_index(key=key)
        _k = k

        while k < self._dict_len and self.__hash_index[k] and hkey != self.__hash_index[k][1]:
            k += 1

        if k >= self._dict_len or self.__hash_index[k] is None:
            return None
        return self.__hash_data[self.__hash_index[k][0]][1]


if __name__ == "__main__":
    ht = NewHashDict()
    for i in range(10):
        i = str(i)
        ht.insert('p' + i, 'pp' + i)

    for i in range(20, 0, -1):
        i = str(i)
        print('p' + i, ht.get('p' + i))