哈希表与哈希（Hash）算法

根据设定的 哈希函数H（key） 和 处理冲突的方法 将一组关键字影像到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便成为 哈希表 ，这一映像过程称为哈希造表或 散列 ，所得存储位置称 哈希地址 或 散列地址 。

上面所提到的 哈希函数 是指：有一个对应关系 f ，使得每个关键字和结构中一个唯一的存储位置相对应，这样在查找时，我们不需要像传统的查找算法那样进行比较，而是根据这个对应关系 f 找到给定值K的像 f（K） 。

哈希函数也可叫哈希算法，它可以用于检验信息是否相同（ 文件校验 ），或者检验信息的拥有者是否真实（ 数字签名 ）。

下面分别就哈希函数和处理冲突的方法进行讨论;

构造哈希函数的方法有很多。在介绍各种方法前，首先需要明确什么是“好” 的哈希算法。若对于关键字集合中的任一个关键字，经哈希函数映像到地址集合中任何一个地址的概率是相等的，则称此类哈希函数是 均匀的 （Uniform）哈希函数。换句话说，就是使关键字经过哈希函数得到一个“随机的地址”，以便使一组关键字的哈希地址均匀分布在整个地址区间中，从而减少冲突。

常用的构造哈希函数的方法有：

理论研究表明， 除留余数法的模 p 取不大于表长且最接近表长 m 的素数效果最好，且 p 最好取11 n ~ 17 n 之间的一个素数（n为存在的数据元素个数） 。

以上便是常用的6种构造哈希函数的方法，实际工作中需视不同的情况采用采用不同的哈希函数，通常考虑的因素有：

前面有提到过 均匀的哈希函数可以减少冲突，但不能避免 ，因此，如何处理冲突是哈希造表不可缺少的另一方面。

通常用的处理冲突的方法有下列几种：

在哈希表上进行查找的过程和哈希建表的过程基本一致。 给定K值，根据建表时设定的哈希函数求得哈希地址，若表中此位置上没有记录，则查找不成功；否则比较关键字，若和给定值相等，则查找成功；否则根据造表时设定的处理冲突的方案找“下一地址” ，直到找到为止。

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

}

· 输入数据长度为l比特，1≤l≤264-1

· 输出哈希值的长度为256比特

(1) 常量与函数

SHA-256算法使用以下常数与函数：

① 常量

初始值IV为：

0x6a09e667 bb67ae85 3c6ef372 a54ff53a

510e527f 9b05688c 1f83d9ab 5be0cd19

这些初值是对自然数中前8个质数(2,3,5,7,11,13,17,19)的平方根的小数部分取前32比特而来。

举个例子来说，√2小数部分约：

0414213562373095048

而0414213562373095048 ≈ 6∗16−1 +a∗16−2+0∗16−3 +9∗16−4 +

于是，质数2的平方根的小数部分取前32比特就对应出0x6a09e667。

和8个初始值类似，这些常量是对自然数中前64个质数(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97…)的立方根的小数部分取前32比特而来。

② 函数

SHA-256用到了以下函数

ROTRi(x)表示循环右移i比特；SHRi(x)表示右移i比特；

(2) 算法描述

① 填充

· 对数据填充的目的是使填充后的数据长度为512的整数倍。因为迭代压缩是对512位数据块进行的，如果数据的长度不是512的整数倍，最后一块数据将是短块，这将无法处理。

· 设消息m长度为l比特。首先将比特“1”添加到m的末尾，再添加k个“0”，其中，k是满足下式的最小非负整数l+1+k = 448mod512。

· 然后再添加一个64位比特串，该比特串是长度l的二进制表示。填充后的消息m的比特长度一定为512的倍数。

· 以信息“abc”为例显示补位的过程。a, b, c对应的ASCII码分别是97, 98, 99；于是原始信息的二进制编码为：01100001 01100010 01100011。

补一个“1” ：0110000101100010 01100011 1

补423个“0”：01100001 01100010 01100011 10000000 00000000 … 00000000

补比特长度24 (64位表示)，得到512比特的数据：

C#

byte[] bytes = EncodingUTF8GetBytes("即将进行 MD5 哈希运算的明文");

MD5CryptoServiceProvider md5Csp = new MD5CryptoServiceProvider();

byte[] hashBytes = md5CspputeHash(bytes);

string hashBase64 = ConvertToBase64String(hashBytes);

在 RSA 数字签名中，HASH 函数起到了关键的作用。具体来说，HASH 函数会对待签名的原始数据进行摘要处理，生成一个固定长度的 HASH 值，并将该 HASH 值作为数字签名的输入。在验证数字签名时，接收方会再次计算原始数据的 HASH 值，并将其与数字签名中包含的 HASH 值进行比较。如果两个 HASH 值相等，则认为该签名是有效的；否则则认为签名无效。

使用 HASH 函数的主要目的是增强数字签名的安全性和可靠性。因为HASH 函数具有以下特点：

1 不可逆性：HASH 函数可以将任意长度的消息转化为固定长度的 Hash 值，在计算过程中不可逆，无法从 Hash 值推导出原始数据。

2 抗碰撞性：HASH 函数能够最大限度地避免不同数据产生相同的 HASH 值，从而防止数字签名被篡改或伪造。

3 高效性：HASH 函数的计算速度非常快，可以快速处理大量数据并生成固定长度的 Hash 值，不会影响数字签名的性能。

因此，在实际应用中，使用 HASH 函数可以提高 RSA 数字签名的安全性和可靠性，避免数字签名被篡改或伪造，确保数据的完整性和准确性。