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

kmindg

yulihua49 发表于 2014-05-28 10:35
看了一下，似懂非懂。
怀疑在接近满的时候会倒腾不过来。
这时需要扩充，rehash。。。。。

(2,4)-cuckoo hash  填充率应该能到90%（文献上的数据，实际情况我不清楚）。关键在于即使没有达到90%有时候插入也会找不到空位，就需要用新的hash函数rehash，所以它的插入比较慢（而且需要多组hash函数，也可以用一些变通的方法只用一个hash函数）。由于查找最多需要2×4次，所以保证最坏情况下也是O(1)。

你的方法在最坏情况下避免不了O(n) 吧？ 比如1000项全冲突，仍然需要遍历1000项去找。

yulihua49

kmindg 发表于 2014-05-28 12:32
(2,4)-cuckoo hash  填充率应该能到90%（文献上的数据，实际情况我不清楚）。关键在于即使没有达到90%有 ...

是。发现过因hash错误造成的全链表。
但是，如果选择好hash函数，一般就是前边说的，冲突大约33%。
我的make_hash()会报告冲突率，根据这个冲突率，你可以选择更好的hash方案。

各村有各村的高招，各自有自己的适用范围。多交流，多一种思路。