Hash Table Implementation in C++
- 对于字符串,所用的hash函数为:
size_t _Hash_bytes(const void* ptr, size_t len, size_t seed) {
static const size_t mul = (((size_t) 0xc6a4a793UL) << 32UL)
+ (size_t) 0x5bd1e995UL;
const char* const buf = static_cast<const char*>(ptr);
// Remove the bytes not divisible by the sizeof(size_t). This
// allows the main loop to process the data as 64-bit integers.
const int len_aligned = len & ~0x7;
const char* const end = buf + len_aligned;
size_t hash = seed ^ (len * mul);
for (const char* p = buf; p != end; p += 8)
{
const size_t data = shift_mix(unaligned_load(p) * mul) * mul;
hash ^= data;
hash *= mul;
}
if ((len & 0x7) != 0)
{
const size_t data = load_bytes(end, len & 0x7);
hash ^= data;
hash *= mul;
}
hash = shift_mix(hash) * mul;
hash = shift_mix(hash);
return hash;
}
其中ptr="VOA",len=3,seed=3339675911,返回的hash值为5877402447214576471,模11后,得到bucket位置为6。
- 默认的hash表桶数为11。
- unordered_set的实现,在insert调用栈中,会最终调用到:
__node_type* __n = _M_find_node(__bkt, __k, __code),如果__k是首次插入,__n会等于nullptr,此时会转入__n = __node_gen(std::forward<_Arg>(__v)),即生成新的_Hash_node。如果__n不为nullptr,说明之前已有同样元素存在。
- 如果hash表元素是int,那么会生成一个为其特化的hashtable,其hash值不需要计算,而是直接用value % 11得到其__bkt值,进而插入hash表。
最新文章
- .NET string字符串的截取、移除、替换、插入
- Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined)D Dense Subsequence
- a different object with the same identifier value was already associated with the session:错误;
- 【CodeVS 5032】【省队集训2016 Day5 T1】Play with array
- [论文笔记] Legacy Application Migration to the Cloud: Practicability and Methodology (SERVICES, 2012)
- Linux基础学习系列(一)
- navtab方法参数以及事件
- LCA(RMQ)
- c/c++常用代码 -- 共享内存
- YII2 RBAC Admin User权限相关
- SimpleAliasRegistry implements AliasRegistry
- IOS常用开源库
- QT_编程基础
- .net core 11
- C# 6 与 .NET Core 1.0 高级编程 - 41 ASP.NET MVC(上)
- pom.xml配置,针对mvn clean install -P参数(环境参数)打包
- centos7与centos6命令区别
- Angular + Websocket
- [转]python中pandas库中DataFrame对行和列的操作使用方法
- linux系统自签发免费ssl证书,为nginx生成自签名ssl证书