散列表是支持 INSERT 、DELETE 和 SEARCH 的字典操作，其是对普通数组概念的推广，因为可以对数组元素进行直接寻址，故可在 O(1) 时间内访问数组的任意元素。 当实际存储的关键字数比可能的关键字总数较小时，这时采用散列表比直接的数组寻址更为有效，因为散列表通常采用的数组尺寸与索要存储的关键字数是成比例的。在散列表中，根据关键字计算出数组下标。 当关键字的全域 U 比较小并且任意两个关键字都不相同时，其中每个关键字元素取自全域 U={0,1,...,m-1}，此处 m 是一个不大的数，我们用一个数组（寻址表）T[0...m-1]，其中每个位置对应全域 U 中的一个关键字。在这个表中进行字典操作的执行是很快的，只需 O(1) 的时间。 直接寻址技术一个明显的问题是，如果域U很大，在一台典型计算机的可用内存容量**下，为其设计一个对应的直接寻址表T是不太现实的。 当实际存储在字典中的关键字集合 K 比所有可能的关键字域U小得多时，我们使用散列表。 在直接寻址方式下，具有关键字 k 的元素被存放到槽 k 中。在散列方式下，该元素处于 h(k) 中，也就是利用散列函数 h，根据关键字 k 计算出槽的位置，函数 h 将关键字映射到散列表 T[0...m-1] 的槽位上。 h:U→{0...m-1} 采用散列函数的目的就在于缩小需要处理的小标范围,即要处理的值从 |U| 降到了 m，从而降低了空间开销。 这样做存在一个问题，就是两个关键字很可能映射到同一个槽上，我们将这种情形成为发生了碰撞。 我们可以通过如下两种方式解决碰撞： 1）链表法 在链表法中，把散列到同一个槽中的所有元素都放在一个链表中。如槽j中有一个指针，它指向由所有散列到j的元素构成的链表的投，如果不存在这样的元素，则 j 中为 NIL。 用链表法散列的最坏情况是所有的关键字 n 都散列到同一个槽中，从而产生出一个长度为 n 的链表，这时最坏情况下查找的时间为 O(n)。散列方法的平均态依赖于所选取的散列函数 h 在一般情况下，将所有关键字分不在 m 个槽位上的均匀程度。假定任何元素散列到 m 个槽中的每一个的可能性相同，且与其他元素已被散列到什么位置上是独立无关的，这个假定称为简单一致散列。 一个好的散列函数应或近似地满足简单一致散列的假设。 将关键字解释为自然数：多数散列函数都假定关键字域为自然数集 N={0,1,2,...}，如果给定的关键字不为自然数，则必须有一种方法来将他们解释为自然数。
|
|
声明：文章版权归原作者所有 部分文章转自互联网 如有侵权请联系
[邮箱地址] 删除
|
注册
登录
