hash函数的程序实现

// 说明：Hash函数（即散列函数）在程序设计中的应用目标 ------ 把一个对象通过某种转换机制对应到一个

//size_t类型（即unsigned long）的整型值。

// 而应用Hash函数的领域主要是 hash表（应用非常广）、密码等领域。

// 实现说明：

// ⑴、这里使用了函数对象以及泛型技术，使得对所有类型的对象（关键字）都适用。

// ⑵、常用类型有对应的偏特化，比如string、char*、各种整形等。

// ⑶、版本可扩展，如果你对某种类型有特殊的需要，可以在后面实现专门化。

// ⑷、以下实现一般放在头文件中，任何包含它的都可使用hash函数对象。

//------------------------------------实现------------------------------------------------

#include <string>

using std::string

inlinesize_thash_str(const char* s)

{

unsigned long res = 0

for (*s++s)

res = 5 * res + *s

returnsize_t(res)

}

template <class Key>

struct hash

{

size_toperator () (const Key&k) const

}

// 一般的对象，比如：vector<queue<string>>；的对象，需要强制转化

template <class Key >

size_thash<Key>::operator () (const Key&k) const

{

size_tres = 0

size_tlen = sizeof(Key)

const char* p = reinterpret_cast<const char*>(&k)

while (len--)

{

res = (res<<1）^*p++

}

return res

}

// 偏特化

template<>

size_thash<string >::operator () (const string&str) const

{

return hash_str(str.c_str())

}

typedef char* PChar

template<>

size_thash<PChar>::operator () (const PChar&s) const

{

return hash_str(s)

}

typedef const char* PCChar

template<>

size_thash<PCChar>::operator () (const PCChar&s) const

{

return hash_str(s)

}

template<>size_t hash<char>::operator () (const char&x) const { return x}

template<>size_t hash<unsigned char>::operator () (const unsigned char&x) const { return x}

template<>size_t hash<signed char>::operator () (const signed char&x) const { return x}

template<>size_t hash<short>::operator () (const short&x) const { return x}

template<>size_t hash<unsigned short>::operator () (const unsigned short&x) const { return x}

template<>size_t hash<int>::operator () (const int&x) const { return x}

template<>size_t hash<unsigned int>::operator () (const unsigned int&x) const { return x}

template<>size_t hash<long>::operator () (const long&x) const { return x}

template<>size_t hash<unsigned long>::operator () (const unsigned long&x) const { return x}

// 使用说明：

//

// ⑴、使用时首先由于是泛型，所以要加上关键字类型。

//

// ⑵、其次要有一个函数对象，可以临时、局部、全局的，只要在作用域就可以。

//

// ⑶、应用函数对象作用于对应类型的对象。

//----------------------- hash函数使用举例 -------------------------

#include <iostream>

#include <vector>

#include <string>

using namespace std

int main()

{

vector<string>vstr⑵；

vstr[0] = "sjw"

vstr[1] = "suninf"

hash<string>strhash// 局部函数对象

cout <<" Hash value: " <<strhash(vstr[0]) <<endl

cout <<" Hash value: " <<strhash(vstr[1]) <<endl

cout <<" Hash value: " <<hash<vector<string>>() (vstr) <<endl

cout <<" Hash value: " <<hash<int>() （100） <<endl// hash<int>() 临时函数对象

return 0

}

以下是我用C++编的一个程序，仅供参考！

#include<iostream>

#include<string>

using namespace std

#define M 47 //随机数

#define n 50 //哈希表长

#define q 30 //人数

struct name{

char *py

int k

}

name NameList[n]

struct hash{

char *py

int k

int si

}

hash hashlist[n]

void listname()

{

char *f

int s0,r,i

NameList[0].py="baojie"

NameList[1].py="chengaoyang"

NameList[2].py="chenguangzhong"

NameList[3].py="chenliangliang"

NameList[4].py="chenyongzhou"

NameList[5].py="fengchao"

NameList[6].py="gexiangfeng"

NameList[7].py="huting"

NameList[8].py="huangpinjin"

NameList[9].py="jiangxiaojia"

NameList[10].py="laidongjie"

NameList[11].py="liyexiao"

NameList[12].py="lidaohui"

NameList[13].py="lijue"

NameList[14].py="lizhuoqun"

NameList[15].py="linfujun"

NameList[16].py="luobin"

NameList[17].py="luokeqing"

NameList[18].py="nichao"

NameList[19].py="panhuafeng"

NameList[20].py="sijun"

NameList[21].py="songzhanhui"

NameList[22].py="sunzhengqing"

NameList[23].py="wanghaofeng"

NameList[24].py="wangjunshuai"

NameList[25].py="wangqinde"

NameList[26].py="wangzejun"

NameList[27].py="wangkeke"

NameList[28].py="weixing"

NameList[29].py="wurenke"

for(i=0i<qi++)

{

s0=0

f=NameList[i].py

for(r=0*(f+r)!='\0'r++)

s0+=*(f+r)

NameList[i].k=s0

}

}

void creathash()

{

int i

for(i=0i<ni++)

{

hashlist[i].py=""

hashlist[i].k=0

hashlist[i].si=0

}

for(i=0i<Mi++)

{

int sum=0

int adr=(NameList[i].k)%M

int d=adr

if(hashlist[adr].si==0)

{

hashlist[adr].k=NameList[i].k

hashlist[adr].py=NameList[i].py

hashlist[adr].si=1

}

else

{

while(hashlist[d].k!=0)

{

d=(d+NameList[i].k%10+1)%M

sum=sum+1

}

hashlist[d].k=NameList[i].k

hashlist[d].py=NameList[i].py

hashlist[d].si=sum+1

}

}

}

void findlist()

{

string nam

int s0=0,r,sum=1

cout<<"请输入姓名的拼音："<<endl

cin>>nam

for(r=0r<20r++)

s0+=nam[r]

int adr=s0%M

int d=adr

if(hashlist[adr].k==s0)

cout<<"姓名："<<hashlist[adr].py<<" "<<"关键字："<<s0<<" "<<"查找长度为：1"<<endl

else if(hashlist[adr].k==0)

cout<<"无此记录！"<<endl

else

{

int g=0

while(g==0)

{

d=(d+s0%10+1)%M

sum=sum+1

if(hashlist[d].k==0)

{cout<<"无此记录！"<<endl

g=1

}

if(hashlist[d].k==s0)

{

cout<<"姓名："<<hashlist[adr].py<<" "<<"关键字："<<s0<<" "<<"查找长度为：1"<<endl

g=1

}

}

}

}

void display()

{

int i

for(i=0i<30i++)

cout<<NameList[i].py<<" "<<NameList[i].k<<endl

}

int main()

{

char x

listname()

creathash()

cout<<"d. 显示哈希表 f.查找 任意键退出 请选择"<<endl

while(cin>>x)

{

if(x=='d'){display()cout<<endl}

else if(x=='f'){findlist()cout<<endl}

else break

}

return 0

}

这个涉及到perl包了吧

只能写代码给你看了，细节可能需要自己去查资料。

1、建立一个文件，用于存储你的哈希表，名为MyHashTb.pm，里面的代码为：

#!usr/bin/perl -w

use strict

package MyHashTb

sub new

{

my $class = shift @_

my $ref = {}

bless $ref,$class

return

}

sub set

{

my $class = shift @_

$class ->{"key1"} = "value1"

$class ->{"key2"} = "value2"

...

$class ->{"keyN"} = "valueN"

}

sub get

{

my ($class,$key) = @_

return $class ->{$key}

}

1

#以package开头必须以1结尾

2、将MyHashTb.pm这个文件放到perl存放模块的目录下，之后其他.pl的perl程序可以通过以下代码调用它：

#!usr/bin/perl -w

use strict

use MyHashTb

my $key1 = "key1"

my $key2 = "key2"

my $hash_tb = MyHashTb ->new()

$hash_tb ->set()

my $value1 = $hash_tb ->get($key1)

my $value2 = $hash_tb ->get($key2)

---