哈希表(Hash Table),又称散列表，是一种根据关键码值(Key Value)而直接进行访问的数据结构，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度，这个映射函数叫作哈希函数(Hash Function)。
哈希表的存储结构通常采用数组和链表的形式，在理想情况下，如果哈希函数的设计得当，使得每个元素都尽可能地均匀分布在数组中，那么在平均情况下，查找、插入和删除的时间复杂度都是O(1)，但是在最坏的情况下，如果所有的元素都集中在数组的某一端，那么时间复杂度就会退化到O(n)。
哈希表的主要优点是：
查找效率高：理想情况下，哈希表的查找时间复杂度是O(1)。
插入和删除效率高：哈希表的插入和删除操作，只要哈希函数设计得当，一般都可以在常数时间内完成。
可以动态扩展：如果哈希表的大小不够用，可以通过增加元素个数的方式来动态扩展哈希表。
哈希表也有其局限性：
冲突问题：如果两个不同的元素具有相同的哈希值，那么它们就会发生冲突，解决这个问题的方法有很多种，比如开放寻址法、链地址法等。
哈希函数的设计：哈希函数的设计直接影响到哈希表的性能，一个好的哈希函数应该能够将输入均匀地映射到一个大的范围，并且尽量减少冲突。
下面我们来看一个简单的哈希表实现的例子，使用Python语言： python class HashTable : def __init__ ( self , capacity = 100 ): self.capacity = capacity self.size = 0 self.buckets = [None] * capacity def _hash ( self , key ): return hash ( key ) def put ( self , key , value ): index = self._hash ( key ) if not self.buckets[index]: self.buckets[index] = [ ( key , value ) ] else for pair in self.buckets[index]: if pair[0] == key: pair[1] = value break else: self.buckets[index].append ( ( key , value ) ) self.size += 1 if self.size > self.capacity * 0.75: self._resize() def get ( self , key ): index = self._hash ( key ) if not self.buckets[index]: return None for pair in self.buckets[index]: if pair[0] == key: return pair[1] return None def remove ( self , key ): index = self._hash ( key ) if not self.buckets[index]: return None for i in range ( len ( self.buckets[index] ) ): if self.buckets[index][i][0] == key: del self.buckets[index][i] self.size -= 1 return True else: return False def _resize ( self ): old_capacity = self.capacity self.capacity *= 2 self.buckets = [None] * self.capacity for bucket in old_capacity: if bucket is not None: for pair in bucket: self.put(pair[0], pair[1]) 相关问题与解答
Q1:什么是哈希冲突？如何解决哈希冲突？
A1:哈希冲突是指当两个或多个不同的键经过哈希函数处理后产生相同的索引值的情况，解决哈希冲突的方法有开放寻址法和链地址法，开放寻址法是在哈希表中寻找下一个可用的空槽位；链地址法则是在哈希表的索引位置上维护一个链表，所有映射到同一个索引位置的键值对都存储在这个链表上。
原创文章，作者：K-seo，如若转载，请注明出处：https://www.kdun.cn/ask/204263.html
微信扫一扫 