关于红黑树和Hash表

bigbook2000

我比较喜欢红黑树，插入查找都是固定的复杂度O(lgN)。

我觉得对于固定长度的Hash表的效率很不好，因为我们很难找到一个函数将我们所需要的对象一一对应到一个连续低值的序列中，多数情况下都是有碰撞的。这种不可控性不是我的风格，搞不好你每次都碰到怀运气。

不知道大家怎么看

funcman

一个均匀散列的哈希函数求到一个哈希值，把这个值除以你的存储规模求余，得到数字不就放在一个低值的序列范围内了。可能存储规模越大效果越好。

bigbook2000

有没有什么比较好的快速的整型的hash函数？

funcman

1. unsigned long hash(const char *name,size_t len)
   
2. {
   
3.         unsigned long h=(unsigned long)len;
   
4.         size_t step = (len>>5)+1;
   
5.         for (size_t i=len; i>=step; i-=step)
   
6.             h = h ^ ((h<<5)+(h>>2)+(unsigned long)name[i-1]);
   
7.         return h;
   
8. }

复制代码

LUA里的算法，散列得比较均匀，速度和字符串的长度关系不大（云风wiki里介绍的）

ybt631

emplate <class _Init>
        inline size_t _Hash_value(_Init _Begin, _Init _End)
        {        // hash range of elements
        size_t _Val = 2166136261U;
        while(_Begin != _End)
                _Val = 16777619U * _Val ^ (size_t)*_Begin++;
        return (_Val);
        }
vc 2005 sp1的hash算法, 也还可以...

小学生

要看用在什么地方吧，较为固定的数据存储，哈希表更好吧。

tarkey

http://blog.csdn.net/tarkey/archive/2004/11/05/167909.aspx
鹅早年做过关于hash table的一些研究。。。