Simon 's Blog
» 做笔记做笔记
Toggle navigation
Simon 's Blog
HOME
总裁介绍
coper
zongcai
what
ARCH
TAGS
navigation
!!! HashTable实现
? hashtable ?
? 数据结构 ?
? STL源码 ?
2019-07-16 19:39:35
387
0
0
simon88
? hashtable ?
? 数据结构 ?
? STL源码 ?
[TOC] # Hash函数设计 ## 整数 ``` hash(126) = (1 * 10^2+2 * 101+6 * 10^0) ``` ## 字符串 公式: ``` hash(code) = (c * B^3 + o * B^2 + d * B^1 + e * B^0) % M hash(code) = ((((c*B)+o)*B+d)*b+e) % M hash(code) = ((((c%M)*B+o)%M*B+d)%M*B+e)%M ``` 伪算法: ``` hash = 0; i = 0; for i < s.len { hash = (hash*B + s[i])%M; i++; } ``` ## STL中hash function设计 ``` template<typename Key> struct hash {}; inline size_t __stl_hash_string(const char* s) { unsigned long h = 0; for (; *s; ++s) h = 5 * h + *s; return size_t(h); } struct hash<const char*> { size_t operator()(const char* s)const { return __stl_hash_string(s); }; }; struct hash<char*> { size_t operator()(char* s)const { return __stl_hash_string(s); }; }; struct hash<char> { size_t operator()(char x)const { return x; }; }; 更多的特别版本略....... ``` # HashTable的种类 ## 平衡树 - 有M个地址 - 总共有N各元素 - 每个地址都是平衡树 - 时间复杂度O(log(N/M)) 代码实现如下: ``` template<typename Key, typename Value> class HashTable { public: HashTable(int M) :_M(M), _size(0) { _hashTable = new RBTree<Key, Value>[M]; for (int i = 0; i < M; i++) { _hashTable[i] = RBTree<Key, Value>(); } } ~HashTable() { delete[]_hashTable; } public: int getSize() { return _size; } void insert(const Key &k, const Value &v) { RBTree<Key, Value> rb = _hashTable[hash(k)]; if (rb->containsKey(k)) { rb->insert(k, v); } else { rb->insert(k, v); _size++; } } Value remove(const Key &k) { Value ret; RBTree<Key, Value> rb = _hashTable[hash(k)]; if (rb->containsKey(k)) { ret = rb.remove(k); _size--; } return ret; } void set(const Key &k, const Value &v) { RBTree<Key, Value> rb = _hashTable[hash(k)]; if (rb->containsKey(k)) { ret = rb->insert(k, v); } else { throw; } } private: int hash(const Key &k) { return k; } private: RBTree<Key, Value>* _hashTable; int _M; int _size; }; ``` ## 链表法 - 有M个地址 - 总共有N各元素 - 每个地址都是链表 - 时间复杂度O(N/M) 结构如下所示: 
上一篇:
C++11/14可变模板参数
下一篇:
红黑树实现
0
赞
387 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
0
条评论
More...
<>