排序与查找-映射抽象数据类型

[TOC]

抽象数据类型“映射”:ADT Map

  • Python最有用的数据类型之一“字典”

  • 字典是一种可以保存key-data键值对的数据类型
    其中关键码key可用于查询关联的数据值data

  • 这种键值关联的方法称为“映射Map”

  • ADT Map的结构是键-值关联的无序集合

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

用一个HashTable类来实现

ADT Map， 该类包含了两个列表作为成员其中一个slot列表用于保存key另一个平行的data列表用于保存数据项

  • 在slot列表查找到一个key的位置以后，在data列表对应相同位置的数据项即为关联数据

  • 保存key的列表就作为散列表来处理， 这样可以迅速查找到指定的key

  • 注意散列表的大小， 虽然可以是任意数，但考虑到要让冲突解决算法能有效工作，应该选择为==素数==。

  • hashfunction方法采用了简单求余方法来实现散列函数， 而冲突解决则采用线性探测“加1”再散列函数。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
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,len(self.slots))

      if self.slots[hashvalue] == None:
        self.slots[hashvalue] = key
        self.data[hashvalue] = data
      else:
        if self.slots[hashvalue] == key:
          self.data[hashvalue] = data  #replace
        else:
          nextslot = self.rehash(hashvalue,len(self.slots))
          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 #replace

    def hashfunction(self,key,size):
         return key%size

    def rehash(self,oldhash,size):
        return (oldhash+1)%size
        
    def get(self,key):
      startslot = self.hashfunction(key,len(self.slots))

      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,len(self.slots))
           if position == startslot:
               stop = True
      return data

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

    def __setitem__(self,key,data):
        self.put(key,data)
        
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[20])
print(H[99])

散列算法分析

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

  • 评估散列冲突的最重要信息就是负载因子λ，一般来说：

    • 如果λ较小，散列冲突的几率就小，数据项通常会保存在其所属的散列槽中

    • 如果λ较大，意味着散列表填充较满，冲突会越来越多，冲突解决也越复杂，也就需要更多的比较来找到空槽；如果采用数据链的话，意味着每条链上的数据项增多

  • 如果采用线性探测的开放定址法来解决冲突（λ在0~1之间）
    成功的查找，平均需要比对次数为：$\frac{1}{2}(1+\frac{1}{1-\lambda})$
    不成功的查找，平均比对次数为：$\frac{1}{2}((1+\frac{1}{1-\lambda})^2)$

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