各种hash函数

2024-08-27 06:38
文章标签 函数 hash

本文主要是介绍各种hash函数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!


常用的字符串Hash函数还有ELFHash,APHash等等,都是十分简单有效的方法。这些函数使用

位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数,

这些函数几乎不可能找到碰撞。

常用字符串哈希函数有BKDRHash,APHash,DJBHash,JSHash,RSHash,SDBMHash,

PJWHash,ELFHash等等。对于以上几种哈希函数,我对其进行了一个小小的评测。

 

Hash函数数据1数据2数据3数据4数据1得分数据2得分数据3得分数据4得分平均分
BKDRHash20477448196.5510090.9582.0592.64
APHash23475449396.5588.4610051.2886.28
DJBHash22497547496.5592.31010083.43
JSHash14476150610084.6296.8317.9581.94
RSHash10486150510010051.5820.5175.96
SDBMHash32484950493.192.3157.0123.0872.41
PJWHash302648785130043.89021.95
ELFHash302648785130043.89021.95

其中数据1为100000个字母和数字组成的随机串哈希冲突个数。数据2为100000个有意义的英文句

子哈希冲突个数。数据3为数据1的哈希值与1000003(大素数)求模后存储到线性表中冲突的个数。

数据4为数据1的哈希值与10000019(更大素数)求模后存储到线性表中冲突的个数。

经过比较,得出以上平均得分。平均数为平方平均数。可以发现,BKDRHash无论是在实际效果还是

编码实现中,效果都是最突出的。APHash也是较为优秀的算法。DJBHash,JSHash,RSHash与

SDBMHash各有千秋。PJWHash与ELFHash效果最差,但得分相似,其算法本质是相似的。

在信息修竞赛中,要本着易于编码调试的原则,个人认为BKDRHash是最适合记忆和使用的。

CmYkRgB123原创,欢迎建议、交流、批评和指正。

 

附:各种哈希函数的C语言程序代码

unsigned int SDBMHash(char *str) {     unsigned int hash = 0;       while (*str)     {         // equivalent to: hash = 65599*hash + (*str++);         hash = (*str+++ (hash << 6+ (hash << 16- hash;     }       return (hash & 0x7FFFFFFF); }   // RS Hash  unsigned int RSHash(char *str) {     unsigned int b = 378551;     unsigned int a = 63689;     unsigned int hash = 0;       while (*str)     {         hash = hash * a + (*str++);         a *= b;     }       return (hash & 0x7FFFFFFF); }   // JS Hash  unsigned int JSHash(char *str) {     unsigned int hash = 1315423911;       while (*str)     {         hash ^= ((hash << 5+ (*str+++ (hash >> 2));     }       return (hash & 0x7FFFFFFF); }   // P. J. Weinberger Hash  unsigned int PJWHash(char *str) {     unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int* 8);     unsigned int ThreeQuarters    = (unsigned int)((BitsInUnignedInt  * 3/ 4);     unsigned int OneEighth = (unsigned int)(BitsInUnignedInt / 8);     unsigned int HighBits = (unsigned int)(0xFFFFFFFF<< (BitsInUnignedInt                                                 - OneEighth);     unsigned int hash    = 0;     unsigned int test    = 0;       while (*str)     {         hash = (hash << OneEighth) + (*str++);         if ((test = hash & HighBits) != 0)         {             hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));         }     }       return (hash & 0x7FFFFFFF); }   // ELF Hash  unsigned int ELFHash(char *str) {     unsigned int hash = 0;     unsigned int x    = 0;       while (*str)     {         hash = (hash << 4+ (*str++);         if ((x = hash & 0xF0000000L!= 0)         {             hash ^= (x >> 24);             hash &= ~x;         }     }       return (hash & 0x7FFFFFFF); }   // BKDR Hash  unsigned int BKDRHash(char *str) {     unsigned int seed = 131// 31 131 1313 13131 131313 etc..     unsigned int hash = 0;       while (*str)     {         hash = hash * seed + (*str++);     }       return (hash & 0x7FFFFFFF); }   // DJB Hash  unsigned int DJBHash(char *str) {     unsigned int hash = 5381;       while (*str)     {         hash += (hash << 5+ (*str++);     }       return (hash & 0x7FFFFFFF); }   // AP Hash  unsigned int APHash(char *str) {     unsigned int hash = 0;     int i;       for (i=0*str; i++)     {         if ((i & 1== 0)         {             hash ^= ((hash << 7^ (*str++^ (hash >> 3));         }         else         {             hash ^= (~((hash << 11^ (*str++^ (hash >> 5)));         }     }       return (hash & 0x7FFFFFFF); }

这篇关于各种hash函数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1110914

相关文章

Python itertools中accumulate函数用法及使用运用详细讲解

《Pythonitertools中accumulate函数用法及使用运用详细讲解》:本文主要介绍Python的itertools库中的accumulate函数,该函数可以计算累积和或通过指定函数... 目录1.1前言:1.2定义:1.3衍生用法:1.3Leetcode的实际运用:总结 1.1前言:本文将详

轻松上手MYSQL之JSON函数实现高效数据查询与操作

《轻松上手MYSQL之JSON函数实现高效数据查询与操作》:本文主要介绍轻松上手MYSQL之JSON函数实现高效数据查询与操作的相关资料,MySQL提供了多个JSON函数,用于处理和查询JSON数... 目录一、jsON_EXTRACT 提取指定数据二、JSON_UNQUOTE 取消双引号三、JSON_KE

MySQL数据库函数之JSON_EXTRACT示例代码

《MySQL数据库函数之JSON_EXTRACT示例代码》:本文主要介绍MySQL数据库函数之JSON_EXTRACT的相关资料,JSON_EXTRACT()函数用于从JSON文档中提取值,支持对... 目录前言基本语法路径表达式示例示例 1: 提取简单值示例 2: 提取嵌套值示例 3: 提取数组中的值注意

Java function函数式接口的使用方法与实例

《Javafunction函数式接口的使用方法与实例》:本文主要介绍Javafunction函数式接口的使用方法与实例,函数式接口如一支未完成的诗篇,用Lambda表达式作韵脚,将代码的机械美感... 目录引言-当代码遇见诗性一、函数式接口的生物学解构1.1 函数式接口的基因密码1.2 六大核心接口的形态学

Oracle的to_date()函数详解

《Oracle的to_date()函数详解》Oracle的to_date()函数用于日期格式转换,需要注意Oracle中不区分大小写的MM和mm格式代码,应使用mi代替分钟,此外,Oracle还支持毫... 目录oracle的to_date()函数一.在使用Oracle的to_date函数来做日期转换二.日

Redis的Hash类型及相关命令小结

《Redis的Hash类型及相关命令小结》edisHash是一种数据结构,用于存储字段和值的映射关系,本文就来介绍一下Redis的Hash类型及相关命令小结,具有一定的参考价值,感兴趣的可以了解一下... 目录HSETHGETHEXISTSHDELHKEYSHVALSHGETALLHMGETHLENHSET

C++11的函数包装器std::function使用示例

《C++11的函数包装器std::function使用示例》C++11引入的std::function是最常用的函数包装器,它可以存储任何可调用对象并提供统一的调用接口,以下是关于函数包装器的详细讲解... 目录一、std::function 的基本用法1. 基本语法二、如何使用 std::function

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第