一个神奇的数据结构
程序员文章站
2022-03-03 19:49:31
...
Linklist HashTable
https://github.com/ez8-co/linked_hash/blob/master/linked_hash.hpp
今天在群里有一位群友分享了一个数据结构。通常大家都会使用到数据结构链表。但是链表由于不具备常数级的查找复杂度,有时候需要借助hashTable来做索引方便查找。这常用与缓存中。(其实,队列,二叉树这些都可以借助哈希表来提高其常数级的查找。)
但是使用双数据结构会带来拷贝开销更大的问题,以及同步问题。但是哈希表具有常数级别查找和删除的效率。最适合作为辅助索引使用。
这里贴出部分代码分析。
1. 定义链表节点,val存放数值,另外具有next和prev两个指针,非常标准的双向链表节点。
template<class value_type>
struct lh_entry
{
lh_entry(lh_entry* p = NULL, lh_entry* n = NULL) : val(), prev(p), next(n) {}
lh_entry(const value_type& v, lh_entry* p, lh_entry* n) : val(v), prev(p), next(n) {}
value_type val;
lh_entry *prev, *next;
};
2. 定义链表哈希集合,仅贴出数据结构。
template<class _Kty, class HashFcn/* = lh_hash_fcn<_Kty> */>
class linked_hash_set
{
private:
void assign(const linked_hash_set& rhs);
lh_entry<value_type> _head;
_linked_hash_set _lhs;
}; // end class linked_hash_set
_linked_hash_set 是一个STL的标准哈希表集合,每个元素是链表的节点(可是该数据结构实际并不对链表地址做哈希,而是对key做hash操作)
默认的哈希函数对象(如果自行替换哈希函数,可能会导致该数据结构失效)
struct lhs_hasher
{
lhs_hasher() : cmp() {}
#if defined(_MSC_VER) && _MSC_VER < 1500
enum { // parameters for hash table
bucket_size = 4, // 0 < bucket_size
min_buckets = 8
}; // min_buckets = 2 ^^ N, 0 < N
inline bool operator()(const lh_entry<_Kty>* lhs, const lh_entry<_Kty>* rhs) const {
return cmp(lhs->val, rhs->val);
}
#else
inline size_t operator()(const lh_entry<_Kty>* entry) const {
return cmp(entry->val);
}
#endif
private:
HashFcn cmp;
}; // end class lhs_hasher
然后骚操作来了。
iterator find(const key_type& key) {
_lhs_iter it = _lhs.find((lh_entry<value_type>*)&key);
return iterator(it != _lhs.end() ? *it : &_head);
}
可以使用key直接查找到链表的节点,对返回的迭代器解引用即可。
这样解决了多对象之间多次拷贝的问题。
上一篇: Java开发者的十大戒律
下一篇: Python十大装B语法
推荐阅读
-
前段开发-问一个关于php传值问题在线等挺急的
-
一个php文件可以直接import zip包里的php文件吗?怎么用?
-
PS cs6利用抠图方法制作一个背景透明的图片
-
关于jquery ajax 调用带参数的webservice返回XML数据一个小细节_jquery
-
为什么小弟我的顶部有一个空行
-
利用js编写一个简单的html表单验证,验证通过时提交数据(附源码)
-
请教小弟我写的这个php函数体传递变量的时候为什么总是上一个函数体的值
-
一个写得较好的JavaScript日期挑选控件_时间日期
-
如何实现一个支持动态扩容的数组
-
我遇到一个奇怪的问题,php代码里面凡是含有//这样的注释,include 失败