映射抽象数据类型是散列的应用之一，因为其散列函数与存储空间的关联，使得查找效率大大提高，但随之而来的是空间利用率的下降。准确的说是一种空间换时间。

其实字典也是映射抽象数据类型，因为映射函数的关系，使得存储的数据是无序的。我就简单实现了一下，包括put方法，get方法和dels方法，有了增删改查，其他方法的就简单多了。

因为要存储键和值，而又要用到散列，所以散列肯定是和键key有关，对其计算散列值，并将其存储。那么值value怎么存储呢，因为key和value是有关系的，我们可以用相同的散列值来存储，根据key计算出散列值后，也准备另一个表，在同样的散列值的下标处，存储value。

前面提到，由于表的长度的原因，线性探测再散列解决冲突的时候可能会造成循环检测固定的位置（比如线性加5的时候，而表的长度是10，那么就会一直是两个固定的位置，从而永远也散列不到其他的位置），(尽管我用到的加1的线性探测，但是为了避免循环检测固定的位置)，还是将表的长度设为质数。

# 散列映射数据结构

class HashTable(object):

    # 初始化，两个列表，一个表用于存储key，一个表用于存储实际数据vlaue
    def __init__(self):
        self.size = 11
        self.slots = [None] * self.size
        self.data = [None] * self.size

    # 哈希函数，计算哈希值,利用求余法
    def hash_function(self, key):
        return key % self.size

    # 冲突解决函数，发生冲突后就线性探测再散列，看是否为空，为空则占用。
    # 注意要求余，因为末尾到首部要求余才能回去。
    def rehash(self, oldhash):
        return (oldhash + 1) % self.size

    # 添加函数
    # 两个作用，如果存在这个key，那就是修改data
    # 如果不存在，则是为了存储
    def put(self, key, data):
        hash_value = self.hash_function(key)

        # 看看对应的哈希值的位置是否已经占用，若为空，则将key和value分别存储
        if self.slots[hash_value] == None:
            self.slots[hash_value] = key
            self.data[hash_value] = data

        # 不为空的话，可能就是已经存了这个key（也就是要修改data），也可能是被别的占用了（冲突）
        else:
            # 修改data
            if self.slots[hash_value] == key:
                self.data[hash_value] = data

            # 造成冲突
            else:
                # 持续计算下一个hash值，直到找到。
                next_slot = self.rehash(hash_value)
                while self.slots[next_slot] != None and self.slots[next_slot] != key:
                    next_slot = self.rehash(next_slot)

                # 找到了可以存储的位置
                if self.slots[next_slot] == None:
                    self.slots[next_slot] = key
                    self.data[next_slot] = data

                # 找到了可以替换的位置（修改）
                else:
                    self.data[next_slot] = data


    # 获取data函数
    def get(self, key):
        
        start_slot = self.hash_function(key)

        data = None
        stop = False
        found = False
        position = start_slot

        while self.slots[position] != None and not found and not stop:
            # 找到
            if self.slots[position] == key:
                found = True
                data = self.data[position]
            else:
                # 未找到，再散列
                position = self.rehash(position)

                # 循环一圈还未找到，那就是没有保存这个数据
                if position == startslot:
                    stop = True
        return data

    def dels(self, key):
        start_slot = self.hash_function(key)

        data = None
        stop = False
        found = False
        position = start_slot

        while self.slots[position] != None and not found and not stop:
            # 找到
            if self.slots[position] == key:
                found = True
                self.slots[position] = None
                self.data[position] = None
            else:
                # 未找到，再散列
                position = self.rehash(position)

                # 循环一圈还未找到，那就是没有保存这个数据
                if position == startslot:
                    stop = True
        return found
    

        
    def __get_item__(self, key):
        return self.get(key)

    def __set_item__(self, key, data):
        self.put(key, data)



H = HashTable()

H.put(1, '张三')
H.put(2, '李四')
H.put(3, '王五')

print(H.get(54))
print(H.get(1))

print(H.put(54, '王二麻子'))
print(H.get(54))

H.dels(54)
print(H.get(54))

作者：qq_42907161

链接：https://blog.csdn.net/qq_42907161/article/details/108414937

来源：CSDN
著作权归作者所有，转载请联系作者获得授权，切勿私自转载。