酒店网站建设工作,wordpress 侧边栏位置,昆明铁路局建设工程网站,wordpress 文章主题哈希表#xff08;Hash table#xff0c;也叫散列表#xff09;#xff0c;是根据键#xff08;Key#xff09;而直接访问数据在内存中的储存位置#xff08;又叫做存储桶#xff0c;Buckets#xff09;的数据结构。也就是说#xff0c;它通过计算一个关于键值的函数…哈希表Hash table也叫散列表是根据键Key而直接访问数据在内存中的储存位置又叫做存储桶Buckets的数据结构。也就是说它通过计算一个关于键值的函数哈希函数Hash function也叫散列函数将所需查询的数据映射到表中一个位置来访问记录这加快了查找速度存放记录的数组就叫做哈希表。最直观的例子我们的手机通讯录中如果王某某的电话号码是12345678910我们只需要记个王某某12345678910以后直接找王某某就可以找到他的电话号码了。哈希表可以在O(1)时间内进行读写操作插入与搜索就是最大的优势。leetcode对应章节
哈希表的关键思想是使用哈希函数将键映射到存储桶。
1.当我们插入一个新的键时哈希函数将决定该键应该分配到哪个桶中并将该键存储在相应的桶中 2.当我们搜索一个键时哈希表将使用相同的哈希函数来查找对应的桶并只在特定的桶中进行搜索。
如果两个不同的键经过哈希函数映射之后得到的值相同这叫做哈希冲突或者碰撞collision解决方法后面再讲。
如何设计一个哈希表呢最重要的肯定是哈希函数完美的哈希函数是键与桶一 一对应没有任何冲突或者空间浪费的然而实际基本不可能达到。哈希表又分为两种哈希集合和哈希映射所以设计题就分为设计哈希集合和设计哈希映射。
705. 设计哈希集合
集合是用来存储非重复值的数据结构操作就三种插入、查找是否存在、删除。做设计题必须留意键key的取值范围此处为0到10的六次方因此会有对于桶数数组的长度与桶大小数组中一个格子的大小的权衡。
最极端的开辟一个超大数组桶数为10的六次方、桶大小为1方案如下
class MyHashSet:def __init__(self):Initialize your data structure here.self.HashSet [False] * 1000001def add(self, key: int) - None:self.HashSet[key] Truedef remove(self, key: int) - None:self.HashSet[key] Falsedef contains(self, key: int) - bool:Returns true if this set contains the specified elementreturn self.HashSet[key]初始化数组每一格都是False插入就是对应格变为True查找就是对应格的值True or False删除就是对应格变为False。
如果希望平衡桶数与桶大小相同可以得到以下方案
class MyHashSet:def __init__(self):self.table [[0] * 1000 for _ in range(1001)] # 注意是1001def hash(self, key):return key // 1000, key % 1000 # 获取key在数组中的位置索引def add(self, key):hashkey, hashpos self.hash(key) # 获取key在数组中的位置索引self.table[hashkey][hashpos] 1def remove(self, key):hashkey, hashpos self.hash(key)self.table[hashkey][hashpos] 0def contains(self, key):hashkey, hashpos self.hash(key)return (self.table[hashkey] ! []) and (self.table[hashkey][hashpos] 1)显然这里我们开辟了一个长度 length 为1000的数组哈希函数为取整除冲突的解决方法是让一个格子不止存放一个 key而是用数组把所有可能冲突的 key 都存放进来只需要桶数1000 * 桶大小1001的结果大于10的六次方即可。
hashkey是key经过哈希函数取整除映射后的值可能会重复冲突用于确定key存放在哪个桶
hashpos是key经过取余数后的值可知不同的key得到相同的整除值后它的余数一定是不同的所以可以确定key存放在某一个桶中的哪个位置。
706. 设计哈希映射
映射是用来存储 (key, value) 键值对的数据结构设计思路与集合类似如下
class MyHashMap(object):def __init__(self):self.map [[-1] * 1000 for _ in range(1001)] # 注意是1001def hash(self, key):return key // 1000, key % 1000 # 获取key在数组中的位置索引def put(self, key, value):hashkey, hashpos self.hash(key)self.map[hashkey][hashpos] valuedef get(self, key):hashkey, hashpos self.hash(key)return self.map[hashkey][hashpos]def remove(self, key):hashkey, hashpos self.hash(key)self.map[hashkey][hashpos] -1这里我使用的哈希函数还是取整除桶数还是1001桶大小还是1000。
注意之所以是 range(1001) 而不是 1000 的原因是10的六次方除以 1000 会得到 1000而 range(1000) 最大是999导致 1000 溢出。
下面是更好的方法
705. 设计哈希集合
class MyHashSet:def __init__(self):self.buckets 1001self.table [[] for _ in range(self.buckets)]def hash(self, key):return key % self.bucketsdef add(self, key: int) - None:hash_key self.hash(key)if key in self.table[hash_key]:returnself.table[hash_key].append(key)def remove(self, key: int) - None:hash_key self.hash(key)if key not in self.table[hash_key]:returnself.table[hash_key].remove(key)def contains(self, key: int) - bool:hash_key self.hash(key)return key in self.table[hash_key]只需要设计哈希函数找到桶的位置即可让桶作为一个空的列表里面的元素动态增加。
706. 设计哈希映射
class MyHashMap:def __init__(self):self.buckets 1001self.table [[] for _ in range(self.buckets)]def hash(self, key):return key % self.bucketsdef put(self, key: int, value: int) - None:hash_key self.hash(key)for item in self.table[hash_key]:if key item[0]:item[1] valuereturnself.table[hash_key].append([key, value])def get(self, key: int) - int:hash_key self.hash(key)for item in self.table[hash_key]:if key item[0]:return item[1]return -1def remove(self, key: int) - None:hash_key self.hash(key)for i, item in enumerate(self.table[hash_key]):if key item[0]:self.table[hash_key].pop(i)return同理
