数据结构之拉链法创建哈希表

哈希表是一个通过函数函数来计算数据存储位置的数据结构，通常支持如下操作：

1) insert(key, value)  插入键值对(key, value)

2) get(key)  如果存在键为key的键值对，则返回对应value，否则返回空值

3) delete(key)  删除键为key的键值对

哈希冲突

由于哈希表的大小是有限的，而要存储的值的总数是无限的，因此对任何哈希函数，都会出现两个不同元素映射到同一位置的情况，这种情况叫做哈希冲突。

解决哈希冲突的一个常用方法是拉链法，即在哈希表的每个位置都连接一个链表，当冲突发生时，冲突的元素将被加到该位置链表的最后。

代码示例

以下我们就在前面链表的基础上，实现一个类似集合的hash结构。

class HashTable():
    # 长度为10
    def __init__(self, size=10):
        self.size = 10
        self.T = [LinkList() for _ in range(self.size)]

    def h(self, k):
        return k%(self.size)

    def insert(self, k):
        i = self.h(k)
        if self.find(k):
            print('Duplicated Insert.')
        else:
            self.T[i].append(k)

    def find(self, k):
        i = self.h(k)
        return self.T[i].find(k)

ht = HashTable()
ht.insert(0)
ht.insert(1)
ht.insert(11)

print(ht.T)