我对这些hash的散列质量及效率作了一个简单测试,测试结果如下: 测试1:对100000个由大小写字母与数字随机的ANSI字符串(无重复,每个字符串最大长度不超过64字符)进行散列: 字符串函数 | 冲突数 | 除1000003取余后的冲突数 | BKDRHash | 0 | 4826 | SDBMHash | 2 | 4814 | RSHash | 2 | 4886 | APHash | 0 | 4846 | ELFHash | 1515 | 6120 | JSHash | 779 | 5587 | DEKHash | 863 | 5643 | FNVHash | 2 | 4872 | DJBHash | 832 | 5645 | DJB2Hash | 695 | 5309 | PJWHash | 1515 | 6120 |
测试2:对100000个由任意UNICODE组成随机字符串(无重复,每个字符串最大长度不超过64字符)进行散列: 字符串函数 | 冲突数 | 除1000003取余后的冲突数 | BKDRHash | 3 | 4710 | SDBMHash | 3 | 4904 | RSHash | 3 | 4822 | APHash | 2 | 4891 | ELFHash | 16 | 4869 | JSHash | 3 | 4812 | DEKHash | 1 | 4755 | FNVHash | 1 | 4803 | DJBHash | 1 | 4749 | DJB2Hash | 2 | 4817 | PJWHash | 16 | 4869 |
测试3:对1000000个随机ANSI字符串(无重复,每个字符串最大长度不超过64字符)进行散列: 字符串函数 | 耗时(毫秒) | BKDRHash | 109 | SDBMHash | 109 | RSHash | 124 | APHash | 187 | ELFHash | 249 | JSHash | 172 | DEKHash | 140 | FNVHash | 125 | DJBHash | 125 | DJB2Hash | 125 | PJWHash | 234 |
结论:也许是我的样本存在一些特殊性,在对ASCII码字符串进行散列时,PJW与ELF Hash(它们其实是同一种算法)无论是质量还是效率,都相当糟糕;例如:"b5"与“aE",这两个字符串按照PJW散列出来的hash值就是一样的。另外,其它几种依靠异或来散列的哈希函数,如:JS/DEK/DJB Hash,在对字母与数字组成的字符串的散列效果也不怎么好。相对而言,还是BKDR与SDBM这类简单的Hash效率与效果更好。
|