python数据结构教程 Day11

2020-08-04 本文已影响0人 XaviSong

本章内容

映射抽象数据类型

ADT map

散列算法分析

一、映射抽象数据类型

通俗名称为：字典。

字典是一种可以保存key-data键值对的数据类型。其中关键码key可用于查询关联的数据值data，这种键值关联的方法称为“映射Map” 。ADT Map的结构是键-值关联的无序集合，关键码具有唯一性，通过关键码可以唯一确定一个数据值。

二、ADT map

1、定义其操作

Map()：创建一个空映射，返回空映射对象；
put(key, val)：将key-val关联对加入映射中，如果key已存在，将val替换旧关联值；
get(key)：给定key，返回关联的数据值，如不存在，则返回None；
del：通过del map[key]的语句形式删除key-val关联；
len()：返回映射中key-val关联的数目；
in：通过key in map的语句形式，返回key是否存在于关联中，布尔值

2、实现其操作

为了达到快速查找的目标，需要一个支持高效查找的ADT实现。最合适的是使用前述的散列表来实现，这样查找可以达到最快O(1)的性能。

使用一个HashTable类来实现ADT Map，该类包含了两个列表作为成员其中一个slot列表用于保存key，另一个平行的data列表用于保存数据项。在slot列表查找到一个key的位置以后，在data列表对应相同位置的数据项即为关联数据。保存key的列表就作为散列表（大小为素数）来处理，这样可以迅速查找到指定的key。

class HashTable:
    def __init__(self):
        self.size = 11
        self.slots = [None] * self.size
        self.data = [None] * self.size

    def put(self, key, data):
        '''
        插入键值对代码
        '''
        hashvalue = self.hashfunction(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 = self.rehash(hashvalue)
                while self.slots[nextslot] != None and self.slots[nextslot] != key:
                    nextslot = self.rehash(nextslot)                
                if self.slots[nextslot] == None:
                    self.slots[nextslot] = key
                    self.data[nextslot] = data
                else:
                    self.data[nextslot] = data
    
    def hashfunction(self, key):
        return key % self.size

    def rehash(self, oldhash):
        '''
        线性探测，加一再散列
        '''
        return (oldhash + 1) % self.size

    def get(self, key):
        startslot = self.hashfunction(key)
        data = None
        stop = False
        found = False
        position = startslot
        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 __getitem__(self,key):
        return self.get(key)

    def __setitem__(self,key,data):
        return self.put(key, data)

三、散列算法分析

散列在最好的情况下，可以提供O(1)常数级，时间复杂度的查找性能，由于散列冲突的存在，查找比较次数就没有这么简单。

评估散列冲突的最重要信息就是负载因子λ，一般来说：如果λ较小，散列冲突的几率就小，数据项通常会保存在其所属的散列槽中。如果λ较大，意味着散列表填充较满，冲突会越来越多，冲突解决也越复杂，也就需要更多的比较来找到空槽；如果采用数据链的话，意味着每条链上的数据项增多

如果采用线性探测的开放定址法来解决冲突（λ在0~1之间）

成功的查找，平均需要比对次数为：
$1/2(1+1/(1-λ))$
不成功的查找，平均比对次数为：
$1/2(1+1/(1-λ)^2)$
如果采用数据链来解决冲突（λ可大于1）

成功的查找，平均需要比对次数为：
$1+λ/2$
不成功的查找，平均比对次数为：
$λ$