Ch6部分习题解答1

散列表的实现和冲突解决方法 散列表（Hash Table）是一种常用的数据结构，通过散列函数将关键字映射到数组的索引上，以便快速地查找、插入和删除元素。然而，在散列表中可能会出现冲突，即两个不同的关键字映射到同一个索引上。因此，需要解决冲突问题。 散列函数 散列函数（Hash Function）是将关键字映射到数组的索引上的函数。它的目的是尽量均匀地分布关键字，以减少冲突的可能性。在上面的例子中，散列函数为H(key)=key % 13，即将关键字除以13取余数作为索引。 冲突解决方法 在散列表中，有三种常用的冲突解决方法：线性探查法、双散列法和开散列法（链地址法）。 1. 线性探查法 线性探查法是一种简单的冲突解决方法。当冲突发生时，探查下一个索引直到找到空闲的位置。在上面的例子中，H(31)=31 % 13=5，发生冲突，于是探查下一个索引，H1=(5+1) % 13=6，H2=(5+2) % 13=7，H3=(5+3) % 13=8，直到找到空闲的位置。 2. 双散列法 双散列法是一种更好的冲突解决方法。当冲突发生时，使用第二个散列函数将关键字映射到另一个索引上。在上面的例子中，H(31)=31 % 13=5，发生冲突，于是使用第二个散列函数RH(31)=(7×31) %10+1=8，H1=(5+8) % 13=0，H2=(0+8) % 13=8，直到找到空闲的位置。 3. 开散列法（链地址法） 开散列法是一种最好的冲突解决方法。在每个索引上，维护一个链表，链表中存储所有映射到该索引的关键字。在上面的例子中，每个索引上都维护一个链表，例如索引0上维护链表{78，15，03，...}，索引1上维护链表{...}，以此类推。 平均查找长度 平均查找长度（Average Search Length，ASL）是衡量散列表查找效率的指标。ASLsucc表示成功查找的平均长度，ASLunsucc表示失败查找的平均长度。在上面的例子中，ASLsucc=（8×1+2+4）/10 = 14/10 = 1.4，ASLunsucc=（2+1+3+2+1+5+4+3+2+1+5+4+3）/13 = 36/13。 散列表的应用 散列表有很多应用，例如集合、字典、数据库索引等。在集合和字典中，散列表可以快速地查找、插入和删除元素。在数据库索引中，散列表可以快速地查找记录。 散列表的实现 散列表的实现可以使用数组、链表或树形结构。数组是最简单的实现方法，链表可以处理冲突，树形结构可以实现高效的查找。上面的例子中，使用数组实现散列表。 结论 散列表是一种高效的数据结构，通过散列函数将关键字映射到数组的索引上，以便快速地查找、插入和删除元素。然而，散列表可能会出现冲突，需要解决冲突问题。线性探查法、双散列法和开散列法是三种常用的冲突解决方法。平均查找长度是衡量散列表查找效率的指标。散列表有很多应用，例如集合、字典、数据库索引等。