Hash Table 哈希表介绍

一．定义：
哈希表是为了便于快速搜索而组织的键/值组合的集合。Hash Table是一种数组，可以用任意简单变量值来访问其元素，这种数组叫做关联数组，也叫哈希表。键/值对的集合。

二．优点：
哈希表最大的优点就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。

三．基本原理：
使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标，hash值）相对应，于是用这个数组单元来存储这个元素。也可以简单的理解为，按照关键字为每一个元素“分类”，然后将这个元素存储在相应“类”所对应的地方，称为桶。

但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了“冲突”，换句话说，就是把不同的元素分在了相同的“类”之中。 总的来说，“直接定址”与“解决冲突”是哈希表的两大特点。

四．基本操作：
如果 HashtableObject 是哈希表的obj.， 我们有：

在哈希表中添加一个key/value键值对：HashtableObject.Add(key,value);

在哈希表中去除某个key/value键值对：HashtableObject.Remove(key);

从哈希表中移除所有元素： HashtableObject.Clear();

判断哈希表是否包含特定键key： HashtableObject.Contains(key);

下面控制台程序将包含以上所有操作：

using System; using System.Collections; //使用Hashtable时，必须引入这个命名空间 class hashtable {Key对应于key/value键值对key Console.WriteLine(de.Value);//de.Key对应于key/value键值对value }

五．HashTable是个字典类：
它通过key，将一个个Object放入集合中然后通过key快速的索引到Object.当然是要牺牲一些空间的。一般的线性表、树中，记录在结构中的相对位置是随机的即和记录的关键字之间不存在确定的关系，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较”的基础上，查找的效率与比较次数密切相关。理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。因而查找时，只需根据这个对应关系f找到给定值K的像f(K)。若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上，因此不需要进行比较便可直接取得所查记录。在此，称这个对应关系f为哈希函数，按这个思想建立的表为哈希表（又称为杂凑法或散列法）。

六．哈希表的不可避免冲突(collision)现象：
对不同的关键字可能得到同一个哈希地址 即key1≠key2，而f(key1)=f(key2)。具有相同函数值的关键字对该哈希函数来说称为同义词(synonym)。 因此，在建造哈希表时不仅要设定一个好的哈希函数，而且要设定一种处理冲突的方法。可如下描述哈希表：根据设定的哈希函数H(key)和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间)上并以关键字在地址集中的“象”作为相应记录在表中的存储位置，这种表被称为哈希表。

（ 哈希函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可。）

七．关于动态查找表问题：
1）表长不确定。2)在设计查找表时，只知道关键字所属范围，而不知道确切的关键字。因此，一般情况需建立一个函数关系，以f(key)作为关键字为key的录在表中的位置，通常称这个函数f(key)为哈希函数。(注意：这个函数并不一定是数学函数)

八 关于Hashtable的实现：
Hashtable 类基于 IDictionary 接口，因此该集合中的每一元素是键和值对。

在 Hashtable 中用作元素的每一对象必须能够使用 Object.GetHashCode 方法的实现为其自身生成哈希代码。但是，还可以通过使用 Hashtable 构造函数（该构造函数将 IHashCodeProvider 实现作为其参数之一接受），为 Hashtable 中的所有元素指定一个哈希函数。

在将一个对象添加到 Hashtable 时，它被存储在存储桶中，该存储桶与匹配该对象的哈希代码的哈希代码关联。当在 Hashtable 内搜索一个值时，为该值生成哈希代码，并且搜索与该哈希代码关联的存储桶。(存储桶是 Hashtable 中各元素的虚拟子组，与大多数集合中进行的搜索和检索相比，它可令搜索和检索更简单、更快速。每一存储桶都与一个哈希代码关联，该哈希代码是使用哈希函数生成的并基于该元素的键。)

例如，一个字符串的哈希函数可以采用该字符串中每一字符的 ASCII 代码并它们添加到一起来生成一个哈希代码。字符串“picnic”将具有与字符串“basket”的哈希代码不同的哈希代码；因此，字符串“picnic”和“basket”将处于不同的存储桶中。与之相比，“stressed”和“desserts”将具有相同的哈希代码并将处于相同的存储桶中。

九．哈希函数的构造方法：
1.直接定址法 ：

取关键字或关键字的某个线性函数值为哈希地址。即：

H（KEY）=KEY或H（KEY）=a.key+b

其中A和B为常数（这种哈希望叫做自身函数）/

例如：有一个从1岁到100岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字自身。如表所示：

地址
01 02 03 。。 25 26 27 。。 100

年龄
1 2 3 。。 25 26 27 。。 。。。

人数
3000 2000 5000 。。 1050 。。。 。。。 。。 。。

：

这样若要询问25岁的人有多少，则主要查表的第25项既可。

2.数字分析法：

假设关键字是以R为基的数（如：以10为基的十进制数）。并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。

例如有80个纪录，其关键字为8位十进制数。假设哈希表的表长为10010，则可取两位十进制数组成哈希地址。取哪两位？原则是使得到的哈希地址尽量避免产生冲突，则需从分析这80个关键字着手。假设这80个关键字中的一部分如下所列：

：

8 1 3 4 6 5 3 2

8 1 3 7 2 2 4 2

8 1 3 8 7 4 2 2

8 1 3 0 1 3 6 7

8 1 3 2 2 8 1 7

8 1 3 3 8 9 6 7

8 1 3 5 4 1 5 7

8 1 3 6 8 5 3 7

8 1 4 1 9 3 5 5

：

1 2 3 4 5 6 7 8

对关键字全体的分析中我们发现：第1 2 位都是“81”，第3位只可能取1 2 3 或者4，第8位只可能取2 5 或7 ，因此这4位都不可取。由于中间的4位可看成是近乎随机的，因此可取其中任意两位，或取其中两位与另外两位的叠加求和后舍去进位作为哈希地址。

十．Hashtable 的简单使用说明：
Hashtable的特点，简单说：用空间换时间。

首先要知道几个常用的名词：散列函数，冲突，链表。

1）链表：链表简单的说就是把数据的集合采用动态分配空间的方式，节约内存，便于动态增减，但访问一般只能遍历。常见的教材上一般如下定义：

struct node /*定义节点*/

{

Data data; /*节点数据*/

struct node * next; /*节点指针，指向下个节点*/

} ;

顺便提下：出现C++后，结构体和类是思想上是等价的。所以以C++为基础讲解hash_table的时候，一般会增加一个构造函数。常见定义如下：

struct node /*定义节点*/

{

node():_next(NULL){} /*构造函数*/

string _value; /*节点数据*/

node* _next; /*节点指针，指向下个节点*/

};

2）散列函数：散列函数严格意思上说，是加密函数，可在获取明文后将其转换为固定长度的加密输出。散列函数一般是单向的，具有不可逆性。在这里散列函数就是通过输入一个值得到目标空间的一个“下标”，然后通过“下标”直接访问空间对应的数据。这就是hash_table的基本原理。当然在这中间就会牵扯到一个冲突的问题。

3）冲突：就是输入的值通过散列函数得到的“下标”是一样的。就也就说明不可能设计一个一一对应的散列函数。在解决冲突的问题上。有很多种方法。这里就采取常用的链表。

程序分析：

/***************************** Hash_table.h**********************************/

#ifndef HASH_TABLE_H

#define HASH_TABLE_H

#include <string>

using namespace std;

struct node /*定义节点*/

{

node():_next(NULL){}

string _value;

node* _next;

};

typedef node* hash_node; /*类型定义*/

const int MULT = 31; /*散列函数的参数*/

const int TABLE = 10000; /*数组的大小*/

class hash_table

{

public:

/*构造函数*/

hash_table(hash_node* table);

/*析构函数*/

~hash_table();

/*向hash_table插入元素*/

void Insert(const string& word);

/*从hash_table中查找元素*/

int Search(const string& word);

private:

/*散列函数*/

unsigned int hash(const string& word);

private:

hash_node* _table;

};

#endif

/************************************end*************************************/

/*****************************hash_table.cpp***********************************/

#include "hash_table.h"

#include <iostream>

using namespace std;

/*构造函数*/

hash_table::hash_table(hash_node* table)

{

_table = table;

}

/*析构函数*/

hash_table::~hash_table()

{

delete[] _table;

}

/*散列函数*/

unsigned int hash_table::hash(const string& word)

{

const char* p = word.c_str();

unsigned int h = 0;

for (; p; p++) /*hash_table的心脏*/

{

h = (h*MULT) % TABLE + (*p) % TABLE;

}

return h;

}

/*插入函数*/

void hash_table::Insert(const string& word)

{

/*得到对应的散列值*/

int h = hash(word);

/*对应节点为空，插入本节点*/

if (_table[h] == NULL)

{

hash_node n = new node();

n->_value = word;

n->_next = NULL;

_table[h] = n;

return ;

}

/*如果节点不为空，连结在本节点为头节点的链表*/

for (hash_node p = _table[h];p != NULL;p = p->_next)

{

/*包含相同的值，直接返回*/

if (p->_value == word) return ;

}

/*发生冲突，处理冲突*/

hash_node n = new node();

n->_value = word;

n->_next = _table[h];

_table[h] = n;

}

/*查询函数*/

int hash_table::Search(const string& word)

{

/*得到对应的散列值*/

int h = hash(word);

/*如果对应的节点为空，直接返回*/

if (_table[h] == NULL)

{

return -1;

}

/*循环本节点，匹配对应的值，返回结果*/

for (hash_node p = _table[h];p != NULL;p = p->_next)

{

if (p->_value == word)

{

return 1;

}

}

return -1;

}

/************************************end***********************************/