字符串hash算法比较

Post author:xfxia
Post published:2023年8月1日
Post category:其他

1 概述

链表

查找

的时间效率为O(N)，二分法为log2N，B+ Tree为log2N，但

Hash

链表

查找

的时间效率为O(1)。

设计高效算法往往需要使用

Hash

链表，常数级的

查找

速度是任何别的算法无法比拟的，

Hash

链表的构造和冲突的不同实现方法对效率当然有一定的影响，然而

Hash

函数是

Hash

链表最核心的部分，本文尝试分析一些经典软件中使用到的字符串

Hash

函数在执行效率、离散性、空间利用率等方面的性能问题。

2 经典字符串

Hash

函数介绍

作者阅读过大量经典软件原代码，下面分别介绍几个经典软件中出现的字符串

Hash

函数。

2.1 PHP中出现的字符串

Hash

函数

static unsigned long

hash

pjw(char *arKey, unsigned int nKeyLength)

{

unsigned long h = 0, g;

char *arEnd=arKey+nKeyLength;

while (arKey < arEnd) {

h = (h << 4) + *arKey++;

if ((g = (h & 0xF0000000))) {

h = h ^ (g >> 24);

h = h ^ g;

}

return h;

}

2.2 OpenSSL中出现的字符串

Hash

函数

unsigned long lh_str

hash

(char *str)

{

int i,l;

unsigned long ret=0;

unsigned short *s;

if (str == NULL) return(0);

l=(strlen(str)+1)/2;

s=(unsigned short *)str;

for (i=0; i

ret^=(s[i]<<(i&0x0f));

return(ret);

} */

/* The following

hash

seems to work very well on normal text strings

* no collisions on /usr/dict/words and it distributes on %2^n quite

* well, not as good as MD5, but still good.

原文链接：https://blog.csdn.net/nhczp/article/details/3040546

你可能也喜欢