小阮的菜田
一个人一种命,各安天命吧。
C++博客
首页
新随笔
联系
聚合
管理
随笔-141 评论-9 文章-3 trackbacks-0
字符串Hash算法
据说,Hash的优劣顺序为:BKDRHash, APHash, DJBHash, JSHash, RSHash, SDBMHash, PJWHash, ELFHash。
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 Function
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 Function
unsigned
int
JSHash(
char
*
str)
{
unsigned
int
hash
=
1315423911
;
while
(
*
str)
{
hash
^=
((hash
<<
5
)
+
(
*
str
++
)
+
(hash
>>
2
));
}
return
(hash
&
0x7FFFFFFF
);
}
//
P. J. Weinberger Hash Function
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 Function
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 Function
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 Function
unsigned
int
DJBHash(
char
*
str)
{
unsigned
int
hash
=
5381
;
while
(
*
str)
{
hash
+=
(hash
<<
5
)
+
(
*
str
++
);
}
return
(hash
&
0x7FFFFFFF
);
}
//
AP Hash Function
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
);
}
posted on 2011-02-23 22:16
小阮
阅读(389)
评论(0)
编辑
收藏
引用
所属分类:
数据结构和算法
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
相关文章:
[网络流]骑士共存问题
[网络流] 餐巾计划问题
ural 1297 最长回文子串(后缀数组)
SPOJ 694 Distinct Substrings(不同子串个数, 后缀数组)
并查集类
次短路径与次小生成树问题的简单解法
高精计算
pku 1204 Word Puzzles (trie)
pku 1200 Crazy Search (Rabin Karp)
[网络流] 方格取数问题 ( 二分图点权最大独立集, 最小割模型, 最大流)
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
<
2010年12月
>
日
一
二
三
四
五
六
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
7
8
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(1)
给我留言
查看公开留言
查看私人留言
随笔分类
C++程序设计语言(6)
POJ(13)
USACO(97)
计算几何(5)
数据结构和算法(20)
网络编程(1)
随笔档案
2011年10月 (2)
2011年6月 (3)
2011年5月 (2)
2011年4月 (6)
2011年3月 (17)
2011年2月 (25)
2011年1月 (24)
2010年12月 (28)
2010年11月 (34)
文章档案
2011年2月 (3)
搜索
最新评论
1. re: USACO 4.2.3 Job Processing (平均贪心)
如何证明其正确性
--膜
2. re: USACO 5.2.2 Electric Fences (模拟退火算法)[未登录]
666@匿名
--xixi
3. re: USACO 2.3.1 The Longest Prefix [未登录]
发现一个错误,对于测试实例
AE ABC CDEF .
ABCDEFG
错误
正确答案是3
--z
4. re: USACO 4.2.3 Job Processing (平均贪心)
平均的贪心,好像没听说诶。
--怡红公子
5. re: USACO 5.4.2 Canada Tour (DP)
不明白如何去除重复的,就是怎么解决两个人交叉问题?
--zyz913614263
阅读排行榜
1. 计算几何 - 判断线段相交(转)(3722)
2. N个点中求三个点组成的三角形面积最大(2053)
3. [网络流]最小路径覆盖问题 (二分图最大匹配, 最大流)(1739)
4. ural 1297 最长回文子串(后缀数组)(1684)
5. [网络流] 方格取数问题 ( 二分图点权最大独立集, 最小割模型, 最大流)(1371)
评论排行榜
1. USACO 5.2.2 Electric Fences (模拟退火算法)(3)
2. USACO 4.2.3 Job Processing (平均贪心)(2)
3. pku 1948 Triangular Pastures (01背包)(1)
4. USACO 2.3.1 The Longest Prefix (1)
5. pku 1625 Censored! (AC自动机, DP, 高精度加法)(1)