C语言实现哈希表的相关运算算法 编写程序实现哈希表的构造过程。

#define MaxSize 100 //定义最大哈希表长度

#define NULLKEY -1 //定义空关键字值

#define DELKEY -2 //定义被删关键字值

typedef int KeyType //关埋孝键字类型

typedef char * InfoType //其他数据类型

typedef struct

{

KeyType key //关键字域

InfoType data //其他数据域

int count //探查次数域

} HashData

typedef HashData HashTable[MaxSize] //哈希表类型

void InsertHT(HashTable ha,int &n,KeyType k,int p) /薯世/将关键字k插入到哈希表中

{

int i,adr

adr=k % p

if (ha[adr].key==NULLKEY || ha[adr].key==DELKEY)//x[j]可以直接放在哈希表中

{

ha[adr].key=k

ha[adr].count=1

}

else//发生冲突时采用线性探弯手稿查法解决冲突

{

i=1 //i记录x[j]发生冲突的次数

do

{

adr=(adr+1) % p

i++

}

while (ha[adr].key!=NULLKEY &&ha[adr].key!=DELKEY)

ha[adr].key=k

ha[adr].count=i

}

n++

}

void CreateHT(HashTable ha,KeyType x[],int n,

Hash，一般翻译做"散列"，也有直接音译为"哈希"的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

HASH主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码里，叫做HASH值. 也可以说，hash就是找到一种数据内容和数据存放地址之间的映射关系。Hash算法在信息安全方面的应用主悔粗要体现在以下的3个方面：文件校验、数字签名、鉴权协议

程程序实现

// 说明：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

}

应该激搭是这个意思：

第一次冲突就是散列的位置+1，这次发生冲突了燃和就继续第二次

第二次用的是平方取中，55^2= 3025，当然第二次冲突的明段拿RH2就是02了，答案(2)

---