|
一．定义： 二．优点： 三．基本原理： 但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了“冲突”，换句话说，就是把不同的元素分在了相同的“类”之中。 总的来说，“直接定址”与“解决冲突”是哈希表的两大特点。 四．基本操作： 在哈希表中添加一个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是个字典类： 六．哈希表的不可避免冲突(collision)现象： （ 哈希函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可。） 七．关于动态查找表问题：
在 Hashtable 中用作元素的每一对象必须能够使用 Object.GetHashCode 方法的实现为其自身生成哈希代码。但是，还可以通过使用 Hashtable 构造函数（该构造函数将 IHashCodeProvider 实现作为其参数之一接受），为 Hashtable 中的所有元素指定一个哈希函数。 在将一个对象添加到 Hashtable 时，它被存储在存储桶中，该存储桶与匹配该对象的哈希代码的哈希代码关联。当在 Hashtable 内搜索一个值时，为该值生成哈希代码，并且搜索与该哈希代码关联的存储桶。(存储桶是 Hashtable 中各元素的虚拟子组，与大多数集合中进行的搜索和检索相比，它可令搜索和检索更简单、更快速。每一存储桶都与一个哈希代码关联，该哈希代码是使用哈希函数生成的并基于该元素的键。) 例如，一个字符串的哈希函数可以采用该字符串中每一字符的 ASCII 代码并它们添加到一起来生成一个哈希代码。字符串“picnic”将具有与字符串“basket”的哈希代码不同的哈希代码；因此，字符串“picnic”和“basket”将处于不同的存储桶中。与之相比，“stressed”和“desserts”将具有相同的哈希代码并将处于相同的存储桶中。
九．哈希函数的构造方法： 取关键字或关键字的某个线性函数值为哈希地址。即： H（KEY）=KEY或H（KEY）=a.key+b 其中A和B为常数（这种哈希望叫做自身函数）/ 例如：有一个从1岁到100岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字自身。如表所示：
地址 这样若要询问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 的简单使用说明： 首先要知道几个常用的名词：散列函数，冲突，链表。 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***********************************/ |
|
|
