请问平衡搜索树，在哈希之外能够存在原因是不是”有序“？

井蛙夏虫

回复 38# yulihua49
不等式，MAX，MIN也都属于序

   

yulihua49

井蛙夏虫 发表于 2014-05-19 14:39
回复 38# yulihua49
不等式，MAX，MIN也都属于序

yes。强调一下。

JohnBull

hash表操作的时间复杂度是

O(1)+反碰撞方案的复杂度 = 反碰撞方案的复杂度
如果用链表反碰撞那就是O(n)。

另外，大O标记本来就是n趋于无穷时的最高次项，没有什么数据量大了是O什么数据量小了又是O什么的说法。

timespace

请问平衡搜索树，在哈希之外能够存在原因是不是”有序“？

“有序”确实是关键，hash map到处都是，C++标准另选了一个反映本质的命名 --- unordered_map。
hash O(1)多么美好，但十分依赖输入/HASH函数/冲突处理，一不小心就变O(n)，tree O(log(n))是天长地久，“有序”是优点也是缺点，有时几次比较代价并不低。在正确场合使用正确数据结构，谁都无法取代谁。

yulihua49

timespace 发表于 2014-05-21 19:25
“有序”确实是关键，hash map到处都是，C++标准另选了一个反映本质的命名 --- unordered_map。
hash O( ...

搞了一个静态hash碰撞算法，冲突率1/3, 在冲突里，二次以上的占1/3,以此类推。。。。。
基本可以避免O(n)。

kmindg

hash有很多不同的变种算法，特点各不相同
如果查找相对插入删除多，可以用(2,4)-cuckoo hash, 最坏情况下O(1)

yulihua49

kmindg 发表于 2014-05-24 13:15
hash有很多不同的变种算法，特点各不相同
如果查找相对插入删除多，可以用(2,4)-cuckoo hash, 最坏情况下O ...

请介绍一下(2,4)-cuckoo hash。

幻の上帝

1.有序。
2.平衡树能实现增删改查都O(log n)。相对来说，hash表查询效率可以比较高（理想情况平摊O(1)，具体得看怎么hash以及具体数据，比较看RP），但频繁插入删除为主时就没有优势。
3.相对通用。不需要纠结对hash进行特定优化。
4.相对稳定。对于各种输入，性能响应相对差异较小，容易预测，不需要指望RP。不会触发rehash等容易造成停顿的操作。
5.数据量较小时典型实现的存储开销比较小。

kmindg

yulihua49 发表于 2014-05-26 10:38
请介绍一下(2,4)-cuckoo hash。

http://en.wikipedia.org/wiki/Cuckoo_hashing

(2,4)-cuckoo hash 是通用cuckoo hash的变种： 2 hash functions，4 keys per bucket

yulihua49

kmindg 发表于 2014-05-26 15:58
http://en.wikipedia.org/wiki/Cuckoo_hashing

(2,4)-cuckoo hash 是通用cuckoo hash的变种： 2 has ...

看了一下，似懂非懂。
怀疑在接近满的时候会倒腾不过来。
这时需要扩充，rehash。。。。。

我的方法是第二张表是一个临时表，冲突项暂存于此。所有元素都插入完毕，在原表找空位，依次填入冲突项，并与原hash位置钩链，全部安置完毕，临时空间删除。
作为静态表，hash桶与数据项等大，没有空间浪费。