算法学习笔记(三)——散列表
2021/9/13 22:08:16
本文主要是介绍算法学习笔记(三)——散列表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1.1 散列表(哈希表)
散列表(哈希表)是根据键值而直接进行访问的数据结构。通过一个散列函数将查找的键转换为表中的一个索引,来加快查找的速度。理想情况下,不同的键值都能转化为不同的索引值,但是在现实中,我们常常要处理多个键值对应同一个索引值。所以,散列查找的算法分为两个部分。第一部分就是关键的散列函数,第二部分就是处理哈希冲突。
1.2 散列函数
散列函数就是通过该函数将元素的键值转换为表的索引。散列函数应该易于计算并且能够均匀分布所有的键,得到的散列值应该是一个非负整数,每个不同的键都有一一对应的散列值。
1.3 哈希冲突的处理
-
拉链法
将表的每一个索引位置都对应一个链表,链表的每个结点都存储了对应的键值。
-
开放地址法
用大小为M的数组保存N个键值对(M>N),通过依靠数组中的空位解决哈希冲突。最简单的开放地址法便是线性探测法,当碰撞发生时,我们直接检查散列表的下一个位置。此时可能有三种结果,命中,未命中或者继续查找。
2.代码实现
-
基于拉链法实现的散列表
template <typename key, typename value> class ChainingListHashTable { private: int N; //键值对数量 int M; //散列表的大小 vector<vector<value>> List; int MyHash(key key) { hash<key> hash_key; return (hash_key(key) & 0x7ffffff % M); } public: ChainingListHashTable(int m) { N = 0; M = m; List.resize(m); } value get(key key) { return List[MyHash(key)][0]; } void put(key key, value value) { List[MyHash(key)].push_back(value); N++; } void erase(key key) { value v = MyHash(key); for(int i = 0; i < List[v].size(); ++i) { if(List[v][i]==key) { List[v].erase(List[v].begin()+i); return; } } cerr<<"No such key in List"<<endl; return; } };
-
基于线性探测法的散列表
template <typename key, typename value> class LinearProbingHashTable { private: int N; static int M = 16; vector<key> keys; vector<value> values; int MyHash(key key) { hash<key> hash_key; return (hash_key(key) & 0x7ffffff % M); } void resize(int cap) { keys.resize(cap); values.resize(cap); } bool contains(key key) { for (int i = MyHash(key); keys[i] != NULL; i = (i + 1) % M) { if (keys[i] == key) eturn true; } return false; } public: LinearProbingHashTable() { keys.resize(M); values.resize(M); } void put(key key, value value) { if (N >= M / 2) resize(2 * M); int i; for (i = MyHash(key); keys[i] != NULL; i = (i + 1) % M) { if (keys[i] == key) { values[i] = value; return; } } keys[i] = key; values[i] = value; N++; } value get(key key) { for (int i = MyHash(key); keys[i] != NULL; i = (i + 1) % M) { if (keys[i] == key) return values[i]; } return NULL; } void erase(key Key) { if (!contains(Key)) return; int i = MyHash(Key); while (keys[i] != Key) i = (i + 1) % M; keys[i] = NULL; values[i] = NULL; i = (i + 1) % M; while (keys[i] != NULL) { key keyToRedo = keys[i]; value valueToRedo = values[i]; keys[i] = NULL; values[i] = NULL; N--; put(keyToRedo, valueToRedo); i = (i + 1) % M; } if (N > 0 && N == M / 8) resize(M / 2); } };
这篇关于算法学习笔记(三)——散列表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-24怎么修改Kafka的JVM参数?-icode9专业技术文章分享
- 2024-12-23线下车企门店如何实现线上线下融合?
- 2024-12-23鸿蒙Next ArkTS编程规范总结
- 2024-12-23物流团队冬至高效运转,哪款办公软件可助力风险评估?
- 2024-12-23优化库存,提升效率:医药企业如何借助看板软件实现仓库智能化
- 2024-12-23项目管理零负担!轻量化看板工具如何助力团队协作
- 2024-12-23电商活动复盘,为何是团队成长的核心环节?
- 2024-12-23鸿蒙Next ArkTS高性能编程实战
- 2024-12-23数据驱动:电商复盘从基础到进阶!
- 2024-12-23从数据到客户:跨境电商如何通过销售跟踪工具提升营销精准度?