网站开发网站源码,创建wordpress网站,济南网站建设服务商,网站服务器备案查询网站备案一#xff0c;基础概念
散列表#xff0c;英文名是hash table#xff0c;又叫哈希表。
散列表通常使用顺序表来存储集合元素#xff0c;集合元素以一种很分散的分布方式存储在顺序表中。
散列表是一个键值对(key-item)的组合#xff0c;由键(key)和元素值(item)组成。键…一基础概念
散列表英文名是hash table又叫哈希表。
散列表通常使用顺序表来存储集合元素集合元素以一种很分散的分布方式存储在顺序表中。
散列表是一个键值对(key-item)的组合由键(key)和元素值(item)组成。键和它对应的元素值基于散列函数(hash function)进行一对一的映射基于键查找到的元素值也可以称为散列值查找公式item hash(key)。其中item可以是具体的值也可以是具体的值对应的内存地址也可以是链表或者链表的指针。
注意有的教程里面喜欢把键值对称为(key, item)有的教程里面喜欢把键值对称为(index, value)其实是相同的意思。
散列表和数组相似的地方在于都可以基于下标快速的访问数据数组的下标是索引散列表的下标是键。
散列表结构在生活中的抽象模型一个班级所有学生的姓名和对应的学号。 二散列表的图示结构
图一key - hash function - hash tablekey, item 图二哈希函数item key % 10 三关于散列函数
最常见的散列函数
除数留余法item (key 5) % 10
例如key50, item 5。key 44, item 9 好的散列函数具有以下特性
函数的设计不过于复杂。
大部分情况下使用相同的键只会查找到同一个值。
键和元素值要均匀随机分布。
基于键查找每个元素值的时间是近似的而不是查找有的值耗时很长查找有的值耗时很短。
发生散列冲突的概率极低。 四散列冲突处理
所谓散列冲突是指不同的键映射到了相同的散列值。
例如对于”item key % 10“的哈希函数key为12或者22得到的散列值都是2。 方式一链表法
在链表法中散列表中的每个key都映射到一个链表。因此当两个key具有相同的item值时这两个key都被添加到相同的链表中。 方式二线性探测法
线性探测法是开放寻址法中的一种所谓开放寻址是指如果出现了散列冲突在散列表中重新找一块儿没被使用过的内存地址组成新的键值对。 具体操作
基于当前key生成的item值没有被其他键值对占用时。则该item值可以和key组成键值对来放进散列表中。如果该item值对应了已有的其他的key则将该key映射到散列表中还没被使用的下一个位置的item值组成新的键值对来放进散列表中。 对于当前场景具体步骤为
step.01: 采用itemkey%10的方式来获得哈希值。
step.02: 发现采用item key%10的方式获得的哈希值被别的key占用了于是采用item(key1)%10的方式来获得新的哈希值。
step.03: 发现采用item(key1)%10的方式获得的新哈希值没被占用就将此哈希值作为key的item生成键值对放入到散列表。否则继续采用item(key2)%10的方式来获得哈希值以此类推。 例如
根据key70获得的哈希值也是0。但是那个位置已经被(key10, item0)占用了。因此根据线性探测法我们将继续找到下一个位置 1。由于该位置暂时未被占用我们依此生成(key70, item1)的键值对。 两种方式对比 五散列表常见操作
a.插入元素
step1.计算key对应的散列值。
step2.如果散列值不在散列表中则插入生成新的键值对。
step3.如果散列值已经在散列表中则发生了散列冲突return返回或覆盖旧散列值或调用专门处理散列冲突的函数。 b.查找元素
step1.计算key对应的散列值。
step2.如果散列值在散列表中则查找成功否则查找失败。 c.删除元素
对于链接法执行和链表一样的删除操作。
对于开放寻址法将被删除节点置为“已删除”标记查找时跳过此节点插入时重新覆盖该节点。 六代码实现
1.Python实现
class HashTable:def __init__(self, size):self.size sizeself.hash_table self.create_buckets()def create_buckets(self):#存储key用的桶结构return [[] for _ in range(self.size)]def insert_val(self, key, val):hashed_key hash(key) % self.sizebucket self.hash_table[hashed_key]found_key Falsefor index, record in enumerate(bucket):record_key, record_val recordif record_key key:found_key Truebreakif found_key:#遇到散列冲突时直接覆盖了旧的值bucket[index] (key, val)else:bucket.append((key, val))def get_val(self, key):hashed_key hash(key) % self.sizebucket self.hash_table[hashed_key]found_key Falsefor index, record in enumerate(bucket):record_key, record_val recordif record_key key:found_key Truebreakif found_key:return record_valelse:return No record founddef delete_val(self, key):hashed_key hash(key) % self.sizebucket self.hash_table[hashed_key]found_key Falsefor index, record in enumerate(bucket):record_key, record_val recordif record_key key:found_key Truebreakif found_key:bucket.pop(index)return#魔法函数遍历对象中的元素def __str__(self):return .join(str(item) for item in self.hash_table)hash_table HashTable(5)
hash_table.insert_val(key_1, value_1)
hash_table.insert_val(key_2, value_2)
hash_table.insert_val(key_3, value_3)
print(hash_table)print(the value of key_2 is: , hash_table.get_val(key_2))
hash_table.delete_val(key_3)
print(hash_table)
运行结果
[][][(key_3, value_3)][(key_1, value_1), (key_2, value_2)][]
the value of key_2 is: value_2
[][][][(key_1, value_1), (key_2, value_2)][]
2.C实现
#includeiostream
#include list
using namespace std;
class Hash
{int BUCKET;//每个散列值对应的链表listint* table;
public:Hash(int V); //插入元素void insertItem(int x);//删除元素void deleteItem(int key);//散列函数int hashFunction(int x) {return (x % BUCKET);}void displayHash();
};
Hash::Hash(int b)
{this-BUCKET b;table new listint[BUCKET];
}
void Hash::insertItem(int key)
{int value hashFunction(key);table[value].push_back(key);
}
void Hash::deleteItem(int key)
{//找到key对应的散列值int index hashFunction(key);list int ::iterator i;for (i table[index].begin();i ! table[index].end(); i) {if (*i key)break;}//删除key对应的元素if (i ! table[index].end())table[index].erase(i);
}
void Hash::displayHash() {for (int i 0; i BUCKET; i) {cout i;for (auto x : table[i])cout -- x;cout endl;}
}
int main()
{int a[] { 15, 11, 27, 8, 12 };int n sizeof(a) / sizeof(a[0]);Hash h(7); for (int i 0; i n; i)h.insertItem(a[i]);h.deleteItem(12);h.displayHash();return 0;
}
运行结果
0
1 -- 15 -- 8
2
3
4 -- 11
5
6 -- 27
3.内置数据类型实现
C内置数据类型STL标准库中的unordered_map容器
Python内置数据类型Python字典dict
Demo1
#include iostream
#include unordered_map
using namespace std;
int main()
{unordered_mapstring, double umap {{One, 1},{Two, 2},{Three, 3}};//insert valueumap[PI] 3.14;umap[root2] 1.414;umap.insert(make_pair(e, 2.718));string key PI;if (umap.find(key) umap.end())cout key not found\n\n;elsecout Found key \n\n;unordered_mapstring, double::iterator itr;cout \nAll Elements : \n;for (itr umap.begin();itr ! umap.end(); itr){cout itr-first itr-second endl;}
}
运行结果
Found PIAll Elements :
One 1
Two 2
Three 3
PI 3.14
root2 1.414
e 2.718
Demo2
dict_obj {a:1, b:2, c:3, d:4}#打印字典
print(dict_obj[a])#增加键值对
dict_obj[e] 5#修改字典的值
dict_obj[a] 21#删除键值对
del dict_obj[d]
print(dict_obj)#清空字典
dict_obj.clear()
print(dict_obj)
运行结果
1
{a: 21, b: 2, c: 3, e: 5}
{} 七参考阅读
《Problem Solving with Algorithms and Data Structures Using Python, Second Edition》
https://www.softwaretestinghelp.com/hash-table-cpp-programs/
https://www.digitalocean.com/community/tutorials/hash-table-in-c-plus-plus
https://www.geeksforgeeks.org/hash-map-in-python/
https://scanftree.com/programs/cpp/c-program-for-hashing-with-chaining/
