Monthly Archives: December 2017

哈希表性能优化的方法有很多，比如： 使用双 hash 检索冲突 使用开放+封闭混合寻址法组织哈希表 使用跳表快速定位冲突 使用 LRU 缓存最近访问过的键值，不管表内数据多大，短时内访问的总是那么几个 使用更好的分配器来管理 key_value_pair 这个节点对象 上面只要随便选两条你都能得到一个比 unordered_map 快不少的哈希表，类似的方法还有很多，比如使用除以质数来归一化哈希值（x86下性能最好，整数除法非常快，但非x86就不行了，arm还没有整数除法指令，要靠软件模拟，代价很大）。 哈希表最大的问题就是过分依赖哈希函数得到一个正态分布的哈希值，特别是开放寻址法（内存更小，速度更快，但是更怕哈希冲突），一旦冲突多了，或者 load factor 上去了，性能就急剧下降。 Python 的哈希表就是开放寻址的，速度是快了，但是面对哈希碰撞攻击时，挂的也是最惨的，早先爆出的哈希碰撞漏洞，攻击者可以通过哈希碰撞来计算成千上万的键值，导致 Python / Php / Java / V8 等一大批语言写成的服务完全瘫痪。 后续 Python 推出了修正版本，解决方案是增加一个哈希种子，用随机数来初始化它，这都不彻底，开放寻址法对hash函数的好坏仍然高度敏感，碰到特殊的数据，性能下降很厉害。 经过最近几年的各种事件，让人们不得不把目光从“如何实现个更快的哈希表”转移到 “如何实现一个最不坏的哈希表”来，以这个新思路重新思考 hash 表的设计。 哈希表定位主要靠下面一个操作： index_pos = hash(key) … Continue reading →

网上对 AVL被批的很惨，认为性能不如 rbtree，这里给 AVL 树平反昭雪。最近优化了一下我之前的 AVL 树，总体跑的和 linux 的 rbtree 一样快了： 他们都比 std::map 快很多（即便使用动态内存分配，为每个新插入节点临时分配个新内存）。 项目代码在：skywind3000/avlmini 其他 AVL/RBTREE 评测也有类似的结论，见：STL AVL Map 谣言1：RBTREE的平均统计性能比 AVL 好 统计下来一千万个节点插入 AVL 共旋转 7053316 次（先左后右算两次），RBTREE共旋转 5887217 次，RBTREE看起来少是吧？应该很快？但是别忘了 RBTREE 再平衡的操作除了旋转外还有再着色，每次再平衡噼里啪啦的改一片颜色，父亲节点，叔叔，祖父，兄弟节点都要访问一圈，这些都是代价，再者平均树高比 AVL 高也成为各项操作的成本。 谣言2：RBTREE 一般情况只比 AVL 高一两层，这个代价忽略不计 纯粹谣言，随便随机一下，一百万个节点的 RBTREE … Continue reading →