网站做小学一年二班作业怎么做,高端专区,学校网站开发方案模板,淄博网站建设推广乐达1. Hash Map简介 Hash Map是一种基于键值对的数据结构#xff0c;通过散列函数将键映射到存储位置#xff0c;实现快速的数据查找和存储。它可以在常数时间内完成查找、插入和删除操作#xff0c;因此在需要频繁进行这些操作时非常高效。 2. Hash Map的定义 散列表#xff…1. Hash Map简介 Hash Map是一种基于键值对的数据结构通过散列函数将键映射到存储位置实现快速的数据查找和存储。它可以在常数时间内完成查找、插入和删除操作因此在需要频繁进行这些操作时非常高效。 2. Hash Map的定义 散列表Hash table也叫哈希表是一种根据键Key直接访问内存存储位置的数据结构。通过计算一个键值的函数将数据映射到表中的一个位置以加快查找速度。这个映射函数称为散列函数存放记录的数组称为散列表。 3. 为什么要使用Hash Map 理想的搜索方法是不经过任何比较一次直接从表中得到要搜索的元素即查找的时间复杂度为 O(1)。哈希表通过哈希函数将元素的存储位置与其关键码之间建立一种映射关系从而实现快速查找。 4. 键值对 键值对是一种常见的数据结构用于表示两个相关联的数据项一个是“键”Key另一个是“值”Value。键用于标识和查找与之关联的值。键值对在许多编程语言中都有特定的表示方法例如C的std::pair和Python的字典dictionary。 python
dictionary {name: Alice, age: 30} 在C中
std::pairstd::string, int person(Alice, 30); 5. Hash Map的基本实现 通过一个简单的数学公式实现Hash Map 假设有数据集合 {1, 7, 6, 4, 5, 9}哈希函数为hash(key) key % capacity其中capacity为10。存储位置如下 - 1 - 1 - 7 - 7 - 6 - 6 - 4 - 4 - 5 - 5 - 9 - 9 6. 哈希冲突 如果插入元素66会与元素6冲突因为它们的哈希地址相同都是6。哈希冲突是指不同关键字通过相同哈希函数计算出相同哈希地址的现象。为了避免冲突需要设计合理的哈希函数。 7. 改进哈希函数 哈希函数设计原则包括 哈希函数的定义域必须包括需要存储的全部关键码。 哈希函数计算出来的地址能均匀分布在整个空间中。 哈希函数应该比较简单。 常用哈希函数设计方法 1. 直接定址法Hash(Key) A * Key B 2. 除留余数法Hash(key) key % p (p m) 3. 平方取中法假设关键字为1234对其平方得到1522756取中间的3位227作为哈希地址。 4. 折叠法将关键字分割成几部分将这些部分叠加求和取后几位作为哈希地址。 5. 随机数法选择一个随机函数取关键字的随机函数值为其哈希地址。 8. 解决哈希冲突的方法 解决哈希冲突的两种常见方法是闭散列和开散列。
8.1 闭散列开放定址法 当发生哈希冲突时将元素存放到冲突位置的下一个空位置中。 线性探测从冲突位置开始依次向后探测直到找到下一个空位置。 查找公式hashi hash(key) % N ii 0, 1, 2, 3, ... 二次探测为了避免线性探测中的堆积问题使用平方探测法。找下一个空位置的方法为hashi hash(key) % N i^2i 1, 2, 3, 4 ...
8.2 开散列链地址法 将具有相同地址的元素归于同一桶桶中的元素通过单链表链接起来。哈希桶的极端情况是所有元素都产生冲突最终都放入一个桶中此时效率退化为 O(N)。 可以将桶中的链表结构改为红黑树结构以提高效率。在JDK1.7中HashMap由数组和链表组成在JDK1.8中引入了红黑树当链表超过8且数组长度超过64时链表会转换为红黑树以提高性能。 9. 闭散列实现 以下是闭散列法的具体实现代码 在python中
class ClosedHashMap:def __init__(self, capacity):self.capacity capacityself.table [None] * capacitydef hash_function(self, key):return key % self.capacitydef insert(self, key, value):index self.hash_function(key)while self.table[index] is not None:index (index 1) % self.capacityself.table[index] (key, value)def search(self, key):index self.hash_function(key)while self.table[index] is not None:if self.table[index][0] key:return self.table[index][1]index (index 1) % self.capacityreturn Nonedef delete(self, key):index self.hash_function(key)while self.table[index] is not None:if self.table[index][0] key:self.table[index] Nonereturn Trueindex (index 1) % self.capacityreturn False 10. 开散列实现 以下是开散列法的具体实现代码 在python中
class Node:def __init__(self, key, value):self.key keyself.value valueself.next Noneclass OpenHashMap:def __init__(self, capacity):self.capacity capacityself.table [None] * capacitydef hash_function(self, key):return key % self.capacitydef insert(self, key, value):index self.hash_function(key)if self.table[index] is None:self.table[index] Node(key, value)else:current self.table[index]while current.next is not None:current current.nextcurrent.next Node(key, value)def search(self, key):index self.hash_function(key)current self.table[index]while current is not None:if current.key key:return current.valuecurrent current.nextreturn Nonedef delete(self, key):index self.hash_function(key)current self.table[index]prev Nonewhile current is not None:if current.key key:if prev is None:self.table[index] current.nextelse:prev.next current.nextreturn Trueprev currentcurrent current.nextreturn False 这些实现展示了如何通过不同的方法来解决哈希冲突确保Hash Map能够高效地插入和查找元素。
