哈希游戏- 哈希游戏平台- 哈希游戏官方网站

　　第8章 哈希表 《数据结构(C#语言描述)》配套PPT 北京大学出版社 制作：陈广 博客： 引入 在C#的万物之母object对象中定义了一个虚方法GetHashCode()，这个方法用于获取对象的哈希码。什么是哈希码？它有什么作用？为什么要在如此重要的类中定义这个方法？哈希码跟哈希表有什么内在的联系吗？本章将对这些问题展开论述。。 8.1 概念引入 【例8-1 Demo8-1.cs】使用学号查找学生地址 【例8-2 Demo8-2.cs】哈希查找 8.2 构造哈希函数的方法 构造哈希函数的目标是使哈希地址尽可能均匀地分布在连续的内存单元地址上，以减少冲突发生的可能性，同时使计算尽可能简单以达到尽可能高的时间效率。根据关键字的结构和分布不同，可构造出与之适应的各不相同的哈希函数。这里主要讨论几种常用的整数类型关键字的哈希函数构造方法。 8.2 构造哈希函数的方法 直接定址法取关键字或关键字的某个线性函数为哈希地址。即： h(key) = key 或 h(key) = a * key + b 其中a、b为常数，调整a与b的值可以使哈希地址取值范围与存储空间范围一致。这种哈希函数计算简单，并且不会有冲突发生。它适合于关键字的分布基本连续的情况，若关键字分布不连续，将造成存储空间的大量浪费。 8.2 构造哈希函数的方法 该方法是提取关键字中随机性较好的数字位，然后把这些数位拼接起来作为哈希地址。它适合于所有关键字值都已知的情况，并需要对关键字中每位的取值分布情况进行分析。 8.2 构造哈希函数的方法 除留余数法采用取模运算（%），把关键字除以某个不大于哈希表表长的整数得到的余数作为哈希地址。哈希函数的形式为： h(key) = key % p 除留余数法的关键是选好p，使得记录集合中的每个关键字通过该孩子数转换后映射到哈希表范围内任意地址上的概率相等，从而尽可能减少发生冲突的可能性。 8.3 哈希冲突解决方法 哈希函数的目标是尽量减少冲突，但实际应用中冲突是无法避免的，所以在冲突发生时，必须有相应的解决方案。而发生冲突的可能性又跟以下两个因素有关： 装填因子α 所采用的哈希函数 8.3 哈希冲突解决方法 冲突解决技术可分为两大类：开散列法（又称为链地址法）和闭散列法（又称为开放地址法）。哈希表是用数组实现的一片连续的地址空间，两种冲突解决技术的区别在于发生冲突的元素是存储在这片数组的空间之外还是空间之内 8.3 哈希冲突解决方法 闭散列法是把所有的元素存储在哈希表数组中。当发生冲突时，在冲突位置的附近寻找可存放记录的空单元。寻找“下一个”空位的过程称为探测。上述方法可用如下公式表示： hi = (h(key) + di) % m 其中 i = 1，2，…，k (k ≤ m - 1) 其中h(key)为哈希函数；m为哈希表长；di为增量的序列。根据di取值的不同，可以分成几种探测方法， 8.3 哈希冲突解决方法 线性探测法的基本思想是：当发生冲突时，从冲突位置的下一个单元顺序寻找，只要找到一个空位，就把元素放入此空位中。顺序查找时，把哈希表看成一个循环表，即如果到最后一个位置也没有找到空位，则回到表头开始继续查找。此时，如果仍然未找到空位，则说明哈希表已满，需要进行溢出处理。 8.3 哈希冲突解决方法 已知一组关键字为（12，19，23，28，39，51，56，76，84），哈希表长m=13，哈希函数为：h(key) = key%11 8.3 哈希冲突解决方法 每个元素经哈希函数计算出来的地址称为基地址，这种不同基地址的元素争夺同一个单元的现象叫做二次聚集。二次聚集实际上是在处理同义词之间的冲突时引发的非同义词的冲突。显然，这种现象对查找不利。线性探测很容易出现二次聚集，小的聚集能汇合成大的聚集，最终导致很长的探测序列，从而降低哈希表的运算效率。 8.3 哈希冲突解决方法 线性探测法的缺点是容易出现二次聚集，为了减少二次聚集的产生，可以加大探测序列的步长，使发生冲突的元素的位置比较分散。如果在地址i产生冲突，不是探测i+1地址，而是探测i + 12，i - 12，i + 22，i - 12，…的地址。该方法的优点是可以减少二聚集的产生，缺点是不易探测到整个哈希空间。 8.3 哈希冲突解决方法 双重散列法又称二度哈希，是闭散列法中较好的一种方法，它是以关键字的另一个散列函数值作为增量。设两个哈希函数为：h1和h2，则得到的探测序列为： (h1(key)+h2(key))%m，(h1(key)+2h2(key))%m，(h1(key)+3h2(key))%m，… 其中，m为哈希表长。由此可知，双重散列法探测下一个开放地址的公式为： (h1(key) + i * h2(key)) % m (1≤i≤m-1) 8.3 哈希冲突解决方法 定义h2的方法较多，但无采用什么方法都必须使h2(key)的值和m互素才能使发生冲突的同义词地址均匀地分布在整个哈希表中，否则可能造成同义词地址的循环计算。若m为素数，则h2取1至m-1之间的任何数均与m互素，因此可以简单地将h2定义为： h2(key) = key % (m - 2) + 1 8.3 哈希冲突解决方法 开散列法的常见形式形式是将所有关键字为同义词的结点链接在同一个单链表中。每个单链表中除了表头指针存储在哈希表数组中以外，所有元素都存储在数组以外的空间，哈希表没有“边界”，这也是“开散列法”名称的来源。 8.3 哈希冲突解决方法 关键字为（12，19，23，28，39，51，56，76，84），哈希表长m=13，哈希函数为h(key) = key % 11，如果使用开散列法进行存储，元素插入单链表时总是插在表头作为第一个结点。设插入顺序为（12，28，19，23，39，56，76，51，84），其结果将如图所示 8.3 哈希冲突解决方法 与开放地址法相比，链地址法有如下优缺点。 优点： 使用链地址法处理冲突无二次聚集现象，因此平均查找长度较短。 由于链地址法中各链表上的结点空间是动态申请的，因此适合于无法确定表长的情况。 在用链地址法构造的哈希表中，删除结点的操作易于实现，只要删除链表上相应的结点即可。 缺点： 指针需要额外空间，故当记录规模较小时，闭散列法较为节省空间。 在，链表的各个元素分散于托管堆各处，这会给自动垃圾回收带来压力，影响程序性能。 8.4 剖析lections.Hashtable C#中实现了哈希表数据结构的集合类有： System.Collections.Hashtable System.Collections.Generic.DictionaryTKey,TValue 前者为一般类型的哈希表，后者是泛型版本的哈希表。Dictionary和Hashtable之间并非只是简单的泛型和非泛型的区别，两者使用了完全不同的哈希冲突解决办法。 8.4 剖析System.Collections.Hashtable object类中定义了一个GetHashCode()方法，这个方法默认的实现是返回一个唯一的整数值以保证在object的生命期中不被修改。 GetHashCode()方法使得C#中的所有类型都能以唯一的数字值来表示。 由于GetHashCode()方法是一个虚方法，可以通过重写这个方法来构造自己的哈希函数。 8.4 剖析System.Collections.Hashtable Hashtable使用了闭散列法来解决冲突，它通过一个结构体bucket来表示哈希表中的单个元素，这个结构体中有三个成员： key ：表示键，即哈希表中的关键字。 val ：表示值，即跟关键字所对应值。 hash_coll ：它是一个int类型，用于表示键所对应的哈希码。 8.4 剖析System.Collections.Hashtable Hashtable解决冲突使用了双重散列法，但又跟前面所讲的双重散列法稍有不同。它探测地址的方式为： h(key, i) = h1(key) + i * h2(key) 其中哈希函数h1和h2的公式如下： h1(key) = key.GetHashCode() h2(key) = 1 + (((h1(key) 5) + 1) % (hashsize - 1)) 由于使用了二度哈希，最终的h(key, i)的值有可能会大于hashsize，所以需要对h(key, i)进行模运算，最终计算的哈希地址为： 哈希地址 = h(key, i) % hashsize 8.5 剖析DictionaryTKey,TValue Dictionary的哈希地址求解较之Hashtable简单许多： 哈希地址 = key.GetHashCode() % hashsize Dictionary内有两个数组： 一个数组名为buckets，用于存放由多个同义词组成的静态链表头指针； 另一个数组名为entries，它用于存放哈希表中的实际数据，同时这些数据通过next指针构成多个单链表。 8.5 剖析DictionaryTKey,TValue buckets中所存放的是Entry结构体，它由四个部分组成： key ：元素的键 value ：元素的值 hashCode ：元素的哈希码 next ：指向哈希表中下一个同义词的指针，实际为下一个同义词在数组中的索引，当不存在下一个同义词时，next的值为-1。 8.5 剖析DictionaryTKey,TValue 为了正确添加和删除元素，Dictionary内部维护了三个成员变量： count freeCount freeList 8.6 本章小结 本章介绍了哈希表及C#中在现了哈希表的两个集合类Hashtable和Dictionary。两种哈希表的区别如下： Hashtable使用了闭散列法来解决冲突，而Dictionary使用了开散列法解决冲突。 Dictionary相对Hashtable来说需要更多的存储空间，但它不会发生二次聚集的情况，并且由于使用泛型实现，Dictonary的速度更快些。 Hashtable使用了填充因子的概念，Dictionary不存在填充因子的概念。 哈希表在扩容时由于需要重新计算哈希地址，会消耗大量时间进行计算，但Dictonary的扩容相对Hashtable来说更快些。 单线程程序中推荐使用 Dictionary，多线程程序中推荐使用 Hashtable。默认的 Hashtable 允许单线程写入，多线程读取，对 Hashtable 进一步调用 Synchronized() 方法可以获得完全线程安全的类型。而 Dictionary 非线程安全，必须人为使用 lock 语句进行保护，效率大为降低。 * * Company LOGO 《数据结构(C#语言描述)》配套PPT 《数据结构(C#语言描述)》配套PPT 《数据结构(C#语言描述)》配套PPT 地址(Address) 0 学号(StuNum) 索引 200809001 广西南宁 200809002 广西南宁 200809003 北京 200809004 上海 200809005 广东深圳 1 2 3 4 《数据结构(C#语言描述)》配套PPT 《数据结构(C#语言描述)》配套PPT 8.2.1 直接定址法 《数据结构(C#语言描述)》配套PPT 8.2.2 数字分析法 位 6 1 3 1 7 6 3 2 6 2 3 2 6 8 7 5 6 2 3 4 3 6 3 4 6 2 7 0 6 6 1 6 6 1 7 7 4 6 3 8 6 1 3 8 1 2 6 1 6 1 3 9 4 2 2 0 ⑧ ⑦ ⑥ ⑤ ④ ③ ② ① 提取结果 12 25 44 6 78 81 90 《数据结构(C#语言描述)》配套PPT 8.2.3 除留余数法 507683的二进制 0011 507683%25相当于取低5位二进制数 《数据结构(C#语言描述)》配套PPT 《数据结构(C#语言描述)》配套PPT 《数据结构(C#语言描述)》配套PPT 8.3.1 闭散列法（开放地址法） 《数据结构(C#语言描述)》配套PPT 8.3.1 闭散列法（开放地址法） 线 《数据结构(C#语言描述)》配套PPT 8.3.1 闭散列法（开放地址法） 线 key h(key) 0 1 2 3 4 5 6 7 8 9 10 11 12 比较次数 插入12 h(key)=12%11=1 12 1 1 插入28 h(key)=28%11=6 28 6 1 19 8 1 插入19 h(key)=19%11=8 插入23 h(key)=23%11=1 23 1 2 插入39 h(key)=39%11=6 39 6 2 插入56 h(key)=56%11=1 56 1 3 插入76 h(key)=76%11=10 76 10 1 插入51 h(key)=51%11=7 51 7 3 插入84 h(key)=84%11=7 84 7 5 《数据结构(C#语言描述)》配套PPT 8.3.1 闭散列法（开放地址法） 线 《数据结构(C#语言描述)》配套PPT 8.3.1 闭散列法（开放地址法） 二次探测法 2 《数据结构(C#语言描述)》配套PPT 8.3.1 闭散列法（开放地址法） 双重散列法 3 《数据结构(C#语言描述)》配套PPT 8.3.1 闭散列法（开放地址法） 双重散列法 3 《数据结构(C#语言描述)》配套PPT 8.3.2 开散列法（链地址法） 《数据结构(C#语言描述)》配套PPT 8.3.2 开散列法（链地址法） 0 1 2 3 4 5 6 7 8 9 10 11 12 56 23 12 39 28 84 51 19 76 《数据结构(C#语言描述)》配套PPT 8.3.2 开散列法（链地址法） 《数据结构(C#语言描述)》配套PPT 《数据结构(C#语言描述)》配套PPT 《数据结构(C#语言描述)》配套PPT 8.4.1 Hashtable的实现原理 《数据结构(C#语言描述)》配套PPT 8.4.1 Hashtable的实现原理 Hashtable动态演示程序网址：/abatei/archive/2009/06/23/1509790.html 《数据结构(C#语言描述)》配套PPT 8.5.1 DictionaryTKey,TValue的实现原理 《数据结构(C#语言描述)》配套PPT 8.5.1 DictionaryTKey,TValue的实现原理 entries buckets 0 1 2 3 4 5 6 0 1 2 3 4 5 6 hashCode key value next 键 值 哈希码 指向下一个同义词的指针 Entry结构体 《数据结构(C#语言描述)》配套PPT 8.5.1 DictionaryTKey,TValue的实现原理 运行虚拟Dictionary 《数据结构(C#语言描述)》配套PPT *