Trie, Hash, MinADFA
Trie的搜索复杂度是 O(length(strkey))，Hash表，计算Hash的复杂度也是O(length(strkey))，但是，仔细分析一下： 继续阅读
缓存与平行数组在 hash_strmap 和 gold_hash_map 中的应用
2007 年我写过一篇关于平行数组与CPU缓存文章，最近，我在 hash_strmap 和 gold_hash_map 中应用了这种设计思想，有这么几个字段可以使用平行数组： 继续阅读
gold_hash_map vs google sparse map by google’s time_hash_map.cc
这个列表由我写的一个 perl 程序抓取 time_hash_map 的结果生成。time_hash_map 是 google 自己实现的 hash table 中的一个性能测试程序，我在其中加入了针对 gold_hash_map 的测试，没有其它任何改动。实现原理：缓存与平行数组在…… 继续阅读
hash_strmap 最新性能数据
QPS 达到了35,644,397，测试机器就是普通 PC：CPU 3G Hz，内存 2G。
总计500,000 条数据，keylen=32 byte，迭代20次, 总查询次数 10,000,000 次, 耗时 0.280549 秒 继续阅读
gold_hash_map design
前一段时间写了个 hash_strmap, 效果不错，其中的一些设计思想可以扩展。于是，昨天到今天两天写了一个通用的 hash_map, 起了个名字叫gold_hash_map。 继续阅读
gold_hash_map bench mark with google sparse hash
This is the testing result with google sparse hash’s bench mark (time_hash_map.cc in google sparse hash’s tar ball)
The only modify to time_hash_map.cc is added the test for gold_hash_map (see diff below) 继续阅读
hash_strmap 为什么那么快
测试结果(普通PC，CPU 3G HZ，内存 2G)
- 单核达到了每秒 30,000,000 次查询，string 长度是 32 字节，这个速度比 unordered_map 快10 倍，比 std::map 快40 倍。
- iteration 的速度, 比 std::map 快 180 倍以上, 比 unordered_map 快 150 倍。
HashMap<string, …> 能有多快
看到很多使用 map<string, ….> 的代码, 也有一些使用了 unordered_map<string, …> 或者 hash_map<string, …>, 当然, hash_map 不是标准的, unordered_map 也只在 boost, tr1 和 c++0x 中可用. 从代码的简洁性和可移植性上讲, 标准的 std::map 是首选. 继续阅读
popcount & google.sparsegroup
ubuntu+gcc4.3 ，尝试修改 google.sparsetable 中的 sparsegroup，修改完成，不启用 -mpopcnt，sparsetable_unittest 和 hashtable_unittest 都通过了。启用-mpopcnt以后，发现硬件不支持，报非法指令错误，公司的电脑太烂了！ 继续阅读
google.sparsegroup 可以更好
sparsegroup 是 google.sparseXXXX （sparsehashmap）系列中最底层的一个数据结构，sparseXXX 的互相依赖如下: 继续阅读