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

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)

本文为 陈华 原创,欢迎转载,但请注明出处:http://edu.ichenhua.cn/read/327