Python实现映射抽象数据类型-字典

雨点打透心脏的1/2处 2023-07-19 12:11 13阅读 0赞

> 《Python数据结构与算法分析》（第二版）

字典是最有用的Python集合之一，使用**键-值对**来存储数据，并且字典是无序的，键是不重复的。键用来查找关联的值，这一概念常常称作**映射**。

映射支持以下操作：

*  Map()创建一个空的映射，它返回一个空的映射集合。
 *  put(key, val)往映射中加入一个新的键-值对。如果键已经存在，就用新值替换旧值。
 *  get(key)返回key对应的值。如果可以不存在，则返回None。
 *  del 通过del map\[key\]这样的语句从映射中删除键-值对。
 *  len()返回映射中存储的键-值对的数目。
 *  in通过key in map这样的语句，在键存在时返回True，否则返回False。

> 使用字典的一大优势是，给定一个键，能很快地找到其关联的值。为了提高搜索效率，可以使用**散列搜索算法**，其时间复杂度可以达到O(1)。

1.使用两个列表创建HashTable类来实现映射抽象数据类型。

class HashTable:
        def __init__(self):# HashTable类的构造方法
            self.size = 11# 散列表的初始大小设置为素数，可以尽可能提高冲突处理算法的效率
            self.slots = [None] * self.size# 设置一个名为slots的列表，用来存储键，并初始化为None
            self.data = [None] * self.size# 设置一个名为data的列表，用来存储值，并初始化为None

1.  实现名为hashfunction的散列函数，要存储或查找的键对散列表的大小进行取余运算。处理冲突时，用一个名为rehash的散列函数实现‘加1’再散列函数的线性探测法。

def hashfunction(self, key, size):
            return key % size
    
        def rehash(self, oldhash, size):
            return (oldhash+1) % size# oldhash为hashfunction()返回的值，但由于该位置上已经有了键，所以发生了冲突，需要使用rehash确定下一个位置

1.  实现put函数， 除非键已经在self.slots中，否则总是可以分配一个位置（槽位）。首先使用hashfunction函数计算初始的散列值，如果对应的位置上已有元素，就循环运行rehash函数，直到遇见一个空槽。如果槽中已有这个键，就用新值替换旧值。

def put(self, key, data):
            hashvalue = self.hashfunction(key, len(self.slots))# 计算散列值，即key所对应的槽位
    
            if self.slots[hashvalue] == None:# 如果该槽位为空，则在该位置添加键-值对
                self.slots[hashvalue] = key
                self.data[hashvalue] = data
            else:
                if self.slots[hashvalue] == key:  # 如果键已经存在
                    self.data[hashvalue] = data  # 用新值替换旧值
                else:  # 该槽位被其他键占用了，计算下一个散列值nextslot
                    nextslot = self.rehash(hashvalue, len(self.slots))
                    # 循环运行rehash直到遇见一个空槽，或发现键已经存在
                    while self.slots[nextslot] != None and \
                            self.slots[nextslot] != key:
                        nextslot = self.rehash(nextslot, len(self.slots))
    
                    if self.slots[nextslot] == None:  # 找到一个空槽位
                        self.slots[nextslot] = key
                        self.data[nextslot] = data
                    else:  # 键已经存在
                        self.data[nextslot] = data

1.  实现get函数，先计算初始散列值，如果值不在初始散列值对应的槽中，就是用rehash确定下一个位置。如果遇到初始槽，就说明已经检查完所有可能的槽，并且元素必定不存在。

def get(self, key):
            startslot = self.hashfunction(key, len(self.slots))
    
            data = None
            stop = False# 一旦遇到初始槽，则赋值为True，停止搜索
            found = False
            position = startslot
    
            # 如果一开始初始槽就为空，则说明元素必定不存在
            while self.slots[position] != None and \
                    not found and not stop:
                if self.slots[position] == key:# 如果找到key
                    found = True
                    data = self.data[position]# 取出key所对应的值
                else:# 如果上一个position已经被其他键占用，则计算下一个位置
                    position = self.rehash(position, len(self.slots))
                    if position == startslot:# 如果遇到初始槽，则搜索失败，元素不存在
                        stop = True# 停止搜索
            return data# 返回data，如果搜素失败，则返回None
    
    
        # 重载__getitem__和__setitem__, 以通过[]进行访问
        def __getitem__(self, key):
            return self.get(key)
    
        def __setitem__(self, key, data):
            self.put(key, data)

1.  运行

H = HashTable()
    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.slots)
    print(H.data)
    print(H[20])
    print(H[17])
    H[20] = 'duck'
    print(H.data)
    print(H[99])

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc5MDM2MA_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc5MDM2MA_size_16_color_FFFFFF_t_70]: /images/20230528/fee8d89a7c8646a498f1c8c9ee7876e2.png