1 hashtable
输入数据 `足够随机`
RB-tree `对数`平均时间
else
hashtable: `常数`平均时间, 基于 `统计`
16bit排列组合的非负整数序列 0-65535
插 i: a[i]++
/
`常数` 平均时间 - 删 i: a[i]--
| \
| 找 i: if(a[i] == 0)
| 2个代价
|/ 2个问题 |- 32bit => 元素数 2^32 = 4G, 数组太大 <- - - - - - - - -
- -[1] `大数组` 存储 - - - - - |
| | |
| [2] 初始化为 0 |- 元素不是整数, 如 `字符串` -> 索引(index) 如何表示 ? |
| |
| 整数: 整数编码 -> 字符: 字符编码为整数 |
| |
| "jjhou" = 'j'*128^4 + ... + 'u'*128^0 = 大数 - -
|
| 解决
|- - -> hashFunc(哈希函数): 将 `大数(整数/字符串的编码值) 映射为 小数` -> 作大小可接受的数组 `索引(index)`
|
| 问题
|/
哈希冲突: `不同元素映射到相同位置(相同索引)`
|
| 解决
|/
开链法
buckets vector + bucket(桶) list ) list
template<class Value>
struct __hashtable_node
{
__hashtable_node* next;
Value val;
}
template<class Value, class Key, class HashFcn,
class ExtractKey, class EqualKey, calss Alloc>
struct __hashtable_iterator
{
// 2个成员数据
node* cur; // [1] 指向 node
hashtable* ht; // [2] 相应的 ht: 可能要从 curBucket 跳到 nextNotEmptyBucket
iterator
operator++()
{
const node* old = cur;
cur = cur->next;
if( !cur )
{
// [1] 元素值 -> hashFunc -> index
size_type bucketIndex = ht->bkt_num(old->val);
// [2] 逐个bucket 遍历, 直到到达1个 `非空 bucket`
while( !cur && ++bucketIndex < ht->buckets.size() )
cur = ht->buckets[bucketIndex];
}
return *this;
}
}
template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, calss Alloc>
class hashtable
{
// ...
private:
HashFcn hash;
ExtractKey get_key;
EqualKey equals;
vector<node*, Alloc> buckets; // 中控表
size_type num_elements;
public:
hashtable(size_type n, const HashFcn& hash_, const EqualKey& equal_)
: hash(hash_), get_key(ExtractKey() ), equals(equal_), num_elements(0)
{
initialize_buckets(n);
}
};
是 node 中 dateType, 不是 key-value 中的 Value 的类型
|\
| key 即 value
| hash_set: - - - - - - -hash_set::Value
| /
Value
| \
| hash_map: - - - hash_map::pair<const Key, T>
|
|/
ExtractKey
|
| 据 Value(node 的 data) 获取 key: hash_table 内部用, 插入
|/
Key // 第2参数
EqualKey
据 `key 相等函数(对象)` 判2个 key 是否相等, 对 hash_set/map 相等不插入
if(equals(get_key(node->val), get_key(node->val) ) )
HashFcn // 第3参数
据 key 得 bucketIndex
hash(key) % buckets.bucketNum
hash functions
Note: 自定义类型, 用户必须写 hashFunc, 否则 hashtable 无法处理
<stl_hash_fun.h>
// 主模板
template <class Key>
struct hash {};
// 辅助函数
inline size_t
__stl_hash_string(const char* s)
{
unsigned long h = 0;
for(; *s; ++s)
h = 5*h + *s;
}
// 特化
struct hash<char*>
{
size_t operator()(const char* s) const
{
return __stl_hash_string(s);
}
};
//
struct hash<int>
{
size_t operator()(int x) const
{
return x;
}
};
2 hash_set: 模板形参中不必指定 Key, ExtractKey: std::identity
template <class Value,
class HashFcn = std::hash<Value>,
class EqualKey = std::equal_to<Value>,
class Alloc = alloc>
class hash_set
{
private:
typedef hashtable<Value, Value, HashFcn,
std::identity<Value>, EqualKey, Alloc> ht;
ht rep; // 底层以 hash_table 完成
public:
hash_set():
rep(100, hasher(), key_equal() ) {}
}
Note: 新的 std::identity 不再是模板类
3 hash_map: 模板形参中不必指定 ExtractKey: std::select1st<pair<const Key, T> >, pair<const Key, T> 为 hashtable 中的 Value
template <class Key, class T,
class HashFcn = std::hash<Key>,
class EqualKey = std::equal_to<Key>,
class Alloc = alloc>
class hash_map
{
private:
typedef hashtable<std::pair<const Key, T>, T, HashFcn,
std::select1st<std::pair<const Key, T> >, EqualKey, Alloc> ht;
ht rep; // 底层以 hash_table 完成
public:
hash_set():
rep(100, hasher(), key_equal() ) {}
}
Note: 新的 std::select1st 更名为 std::_Select1st
4 hash_multiset
5 hash_multimap
Note1: EqualKey 为什么不直接用 strcmp ?
答: EqualKey 要求的是 ture / false，而 strcmp 返回 -1,0,1, 所以必须加一层 封装
eg1: 想保留50个 节点, 最接近 50 的质数是 53(hashFunc 对 53 取余), 所以保留 53 个 buckets
... ht(50, hash<int>(), std::equal_to<int>() )
#0 #1 #2 #52
—————————————————————————————————
| | | |
—|———————————————|————————————————
| |
_|/_ _|/_ _ _
| —| ->| | —|-->| —|->|
|_ _| |_ _| |_ _|
| | | | | |
| 53| |108| | 2 |
|_ _| |_ _| |_ _|
#include <hash_set> // for hashtable, Note: client 不能直接 include <stl_hashtable.h>
#include <functional> // std::identity
#include <cstring> // strcmp
#include <iostream>
struct EqStr
{
bool
operator()(const char* s1, const char* s2) const
{
return strcmp(s1, s2) == 0;
}
};
int main()
{
__gnu_cxx::hashtable<const char*, const char*, std::hash<const char*>,
std::identity, EqStr>
ht(50, std::hash<const char*>(), EqStr());// 可不带参数, 默认 Ctora: get_key(ExtractKey() )
ht.insert_unique("xianyang");
ht.insert_unique("xian");
ht.insert_unique("beijing");
__gnu_cxx::hashtable<const char*, const char*, std::hash<const char*>,
std::identity, EqStr>::iterator beg, end;
beg = ht.begin();
end = ht.end();
for (; beg != end; ++beg)
std::cout << *beg << " ";
std::cout << std::endl;
}
// output:
xianyang xian beijing
#include <hash_set>
#include <cstring>
#include <iostream>
struct EqStr
{
bool
operator()(const char* s1, const char* s2) const
{
return strcmp(s1, s2) == 0;
}
};
int main()
{
__gnu_cxx::hash_set<const char*, std::hash<const char*>, EqStr>
hSet;
hSet.insert("xianyang");
hSet.insert("xian");
hSet.insert("beijing");
__gnu_cxx::hash_set<const char*, std::hash<const char*>, EqStr>::iterator beg, end;
beg = hSet.begin();
end = hSet.end();
for (; beg != end; ++beg)
std::cout << *beg << " ";
std::cout << std::endl;
}
// output:
xianyang xian beijing
#include <hash_map>
#include <cstring>
#include <iostream>
struct EqStr
{
bool
operator()(const char* s1, const char* s2) const
{
return strcmp(s1, s2) == 0;
}
};
int main()
{
__gnu_cxx::hash_map<const char*, int, std::hash<const char*>, EqStr> hMap;
hMap["xianyang"] = 1;
hMap["xian"] = 2;
hMap["beijing"] = 3;
__gnu_cxx::hash_map<const char*, int, std::hash<const char*>, EqStr>::iterator beg, end;
beg = hMap.begin();
end = hMap.end();
for (; beg != end; ++beg)
std::cout << beg->first << " ";
std::cout << std::endl;
}
// output:
xianyang xian beijing
