^

Young Anything I do that may help others, I'll post it here.

Hash map

21 Sep 2016

1 简介

字曲是python里最有用的数据集合之一。字典是一对键值-数据的组合，键值是用来查找相应的数据，我们把这种思想称为“映射”。

映射的抽象数据类型定义如下，这是一个无序的键-值对集合，键值总是唯一的以便建立与数据的对应关系。映射的操作方法如下：
***

  • Map()创建一个新的空的映射，返回一个空集合。
  • put(key,val)在映射中增加一对新的键-值对，如果键值已经存在，用新的数据值代替原来的。
  • get(key)根据给定的键值，返回对应的数值，找不到时返回None。
  • Del从映射中删除键-值对，形式del map[key]
  • len()返回映射中键-值对的数量
  • In如果key值在映射中，key in map返回True，否则返回False

字典的好处之一，是给一个键值可以很快返回相关的数据，为了提供这样快速查询的能力，我们需要引入一个高效的查找功能。

可以对列表使用顺序或二分查找，但是最好是用 哈希表，因为它能提供接近O(1)的性能。

2 代码实现

我们用两个列表创建HashTable类来实现映射的抽象数据类型。 一个列表，名为slots来保存键值元素，另一个平行的列表，名为data，保存数据。
当查询键值的时候，data列表相应的位置上就保存有数据。 我们将键值列表处理成哈希表，注意哈希表的初始大小为是11， 虽然这个大小是随意的，但是选择为质数特别重要，因为这样一来后面处理冲突的效率就比较高。

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

    # Hashfunction函数是简单地用了余数法，冲突解决采用了+1线性探测再哈希函数
    # put函数约定：除非self.slots中包括这个键值，否则这个槽位就认为是空的。
    # 它计算出的哈希值如果非空，就迭代rehash函数，直到找到一个空槽位。
    # 如果一个非空的槽位上已经有键值，就用新数据代替原数据。
    def put(self, key, data):
        hashvalue = self.hashfunction(key, self.size)

        if self.slots[hashvalue] == None:
            self.slots[hashvalue] = key
            self.data[hashvalue] = data
        elif self.slots[hashvalue] == key:
            self.data[hashvalue] = data  # 覆盖更新原数据
        else:
            nextslot = self.rehash(hashvalue, self.size)  # 被先来的key占槽了,就向后就后找槽
            while self.slots[nextslot] != None and self.slots[nextslot] != key:
                nextslot = self.rehash(nextslot, self.size)
                if nextslot == hashvalue:  # 若超过(self.size)个数字继续写入,就break,不允许写入
                    print('no available slot')
                    break

            if self.slots[nextslot] == None:  # 只有空槽和原来存入过该数字这两种情况才写入data
                self.slots[nextslot] = key
                self.data[nextslot] = data
            elif self.slots[nextslot] == key:
                self.data[nextslot] = data  # 覆盖更新原数据

    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, self.size)

        data = None
        stop = False
        found = False
        position = startslot
        while self.slots[position] != None and not found and not stop:  # 有空槽位没放这个key,一开始就put过,可以停止get了
            if self.slots[position] == key:
                found = True
                data = self.data[position]
            else:
                position = self.rehash(position, self.size)  # 被其他数字占了槽,就rehash继续找
                if position == startslot:
                    stop = True  # 找了一圈,槽都被其他先来的数字占了,就不找了。也就是说最多存放(self.size)个数字
        return data

    # 我们重载了__getitem__和__setitem__方法来实现“[]”符号的使用。
    # 这也意味着，一旦HashTable对象创建，熟悉的索引方法就可用了。
    def __getitem__(self, key):
        return self.get(key)

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

    def __delitem__(self, key):
        if self.get(key) != None:  # 只有该key存在于slots中时,才会去查找删除,所以下面的查找就简化了
            hashvalue = self.hashfunction(key, self.size)
            while self.slots[hashvalue] != key:
                hashvalue = self.rehash(hashvalue, self.size)
            self.slots[hashvalue] = None
            self.data[hashvalue] = None

    def __len__(self):
        position = 0
        num = 0
        while position < self.size:
            if self.slots[position] != None:
                num += 1
            position += 1
        return num

    def __contains__(self, key):
        position = 0
        found = False
        while position < self.size and not found:
            if self.slots[position] == key:
                found = True
            position += 1
        return found

3 测试

由以上代码可知：

  • 操作符[]由__getitem__ 和__setitem__重载
  • 操作符del由__delitem__重载
  • 操作符len由__len__重载
  • 操作符in由__contains__ 重载

现对简介中需求的功能测试如下：

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)#[77, 44, 55, 20, 26, 93, 17, None, None, 31, 54]
print(H.data)#['bird', 'goat', 'pig', 'chicken', 'dog', 'lion', 'tiger', None, None, 'cow', 'cat']

print(H[20])#chicken
print(H[17])#tiger
print(H[99])#None

H[20] = 'duck'
print(H[20])#duck


del H[77]
print(H.slots)#[None, 44, 55, 20, 26, 93, 17, None, None, 31, 54]
print(H.data)#[None, 'goat', 'pig', 'duck', 'dog', 'lion', 'tiger', None, None, 'cow', 'cat']
#塞满空余的三个槽位：
print(len(H))#8

H[99] = '99'
H[100] = '100'
H[101] = '101'
print(H.slots)#[99, 44, 55, 20, 26, 93, 17, 100, 101, 31, 54]
print(H.data)#['99', 'goat', 'pig', 'duck', 'dog', 'lion', 'tiger', '100', '101', 'cow', 'cat']

H[22] = 'redundant'#no available slot
print(H.slots)#[99, 44, 55, 20, 26, 93, 17, 100, 101, 31, 54]
print(H.data)#['99', 'goat', 'pig', 'duck', 'dog', 'lion', 'tiger', '100', '101', 'cow', 'cat']
print(len(H))

del H[99],H[100],H[101]
print(H.slots)#[None, 44, 55, 20, 26, 93, 17, None, 101, 31, 54]
print((44 in H))#True
print((100 in H))#False

Related Posts