哈希表

哈希表

定义

哈希表（又称散列表）， 是一种线性表的存储结构。哈希表由一个直接寻址表和一个哈希函数组成。哈希函数h(k)将元素关键字K作为自变量，返回元素的存储下标。

哈希函数

例：假设由一个长度为7 的哈希表，哈希函数h(k)=k%7。元素集合{14，22，3，5}的存储方式如下表

value	14	22		3		5
i(k%7)	0	1	2	3	4	5	6

直接寻址表

缺点

当域U很大时，需要消耗大量内存,不实用

如果域U很大，但实际出现的key很少，则大量空间被浪费

无法处理关键字不是数字的情况

改进

构建大小为m的寻址表T

key为k的元素放在h(k)位置上

h(k)时一个函数，其将域U映射道表T[0,1,2,……,m-1]

存在问题

当哈希函数返回的位置已经有值时，就会出现哈希冲突

解决方法

开放寻址法 ： 如果哈希函数返回的位置已经有值，则可以向后探查新的位置来存储这个值

线性探查 ： 如果位置 i 被占用 ， 则探查 i+1, i+2 ,……..

二次探查 ： 如果位置 i 被占用 ，则探查i+1^2^ , i-1^2^, i +2^2^ ,i-2^2^

二度哈希 ： 有n个哈希函数，当使用第1个哈希函数h1法生冲突时，则尝试使用h2,h3

链表法 ： 哈希表每个位置都链接一个链表，当冲突发生时，冲突的元素将被加到该位置链表的最后。

0	496	896
1	1	337	356
2
3	367
4
5
6
7
8	184
9
10	26	126

常用哈希函数

除法哈希表：

h(k) = k %m

乘法哈希表：

h(k) = floor(m * (A * key%1))

全域哈希表：

Ha,b(k) = ((a*key + b ) mod p) mod m a,b =1,2,…..,p-1

哈希表代码实现

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

insert(key,value): 插入键值(key,value)

get(key): 如果存在键为key的键值对则返回其value,否则返回空值

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

class Linklist:
    class Node:
        def __init__(self,item=None):
            self.item = item
            self.next = None
    class LinklistIterator: #迭代器类  for循环依赖于迭代器,不写迭代器的话,链表不能for循环
        def __init__(self,node):
            self.node = node
        def __next__(self):
            if self.node:
                cur_node = self.node
                self.node = cur_node.next
                return cur_node.item
            else:
                raise StopIteration
        '''
        代器规定必要有这个函数 目的是为了 iterator本身必须是iterable
        因此定义__iter__ 函数当对iterator求自身iterator时调用自己
    
       '''
        def __iter__(self):  #迭
            return self
    def __init__(self,iterable = None):
        self.head = None
        self.tail = None
        if iterable:
            self.extend(iterable)
    def append(self,obj):
        s = Linklist.Node(obj)
        if not self.head:
            self.head = s
            self.tail = s
        else:
            self.tail.next = s
            self.tail = s
    def extend(self,iterable):
        for obj in iterable:
            self.append(obj)
    def find(self,obj):
        for n in self:
            if n == obj:
                return True
        else:
            return False
    def __iter__(self): 
        return self.LinklistIterator(self.head)
    def __repr__(self): #转化为字符串
        return "<<"+",".join(map(str,self))+'>>'
    '''map是python内置函数，会根据提供的函数对指定的序列做映射。
    map()函数的格式是：map(function,iterable,...) 
    参数:
    function是一个函数名称，通过该函数对后续参数iterable进行处理
    iterable是一个可迭代对象，比如：字符串、列表、字典、元组、集合等
    '''

#类似于集合的结构
class HashTable:
    def __init__(self,size=101):#size定义哈希表长度
        self.size = size
        self.T = [Linklist() for i in range(self.size)]
    
    def h(self,k):
        return k % self.size
        
    def insert(self,k):
        i = self.h(k) #k的位置 
        if self.find(k):
            print('重复插入')
        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(101)
a= ht.T[0].head.next.item
print(a)