python链表法的优缺点

Z时代
2024-01-10
分类：综合

美女程序员鼓励师

1、优点，方便删除记录，直接处理数组对应下标的子数组。平均搜索速度快。如果有冲突，只需要查询子数组。

2、缺点，使用指针导致查询速度较慢，内存占用可能较高，不适合序列化。

而开放式寻址法的优缺点与链表法相反。因为Python的一切都是基于Dict的，都需要序列化，所以选择了开放式寻址法。

实例

   # keys函数
#!/usr/bin/env python
# coding=utf-8
 
class Dict:
    def __init__(self, num):
        self.__solts__ = []
        self.num = num
        for _ in range(num):
            self.__solts__.append([])
    def hash_fun(self,key,num):
        hashval = 0
        x = key
        if x < 0:
                print "the key is low"
                return
        while x != 0:
                hashval = (hashval << 3) + x%10
                x /=10
        return hashval % num
    def put(self, key, value):
        i = self.hash_fun(key,self.num) % 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 = self.hash_fun(key,self.num) % self.num
        for k, v in self.__solts__[i]:
            if k == key:
                return v
        raise KeyError(key)
    # keys函数
    def keys(self):
        ret = []
        for solt in self.__solts__:
            for k, _ in solt:
                ret.append(k)
        return ret
    def __getitem__(self,key):
        return self.get(key)
 
    def __setitem__(self,key,data):
        self.put(key,data)
H = Dict(13)
H[54] = "cat"
H[26] = "dog"
H[93] = "lion"
H[17] = "tiger"
H[77] = "bird"
H[31] = "cow"
H[44] = "goat"
H[55] = "pig"
H[20] = "chicken"
print H.get(54)
H.put(13,"duck")
print H.__solts__
print H.keys()