本文主要是介绍【深入解析算法】基于拉链法的散列表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
8.2 基于拉链法的散列表
一个散列函数能够将键转化为数组索引。散列算法的第二步是碰撞处理，也就是处理两个或多个键的散列值相同的情况。一种直接的办法是将大小为M的数组中的每个元素指向一条链表，链表中的每个结点都存储了散列值为该元素的索引的键值对。这种方法被称为拉链法，因为发生冲突的元素都被存储在链表中。这个方法的基本思想就是选择足够大的M,使得所有链表都尽可能短以保证高效的查找。查找分两步:首先根据散列值找到对应的链表，然后沿着链表顺序查找相应的键。拉链法的一种实现方法是使用原始的链表数据类型来扩展SequentialSearchST 。另一种更简单的方法(但效率稍低)是采用一般性的策略，为M个元素分别构建符号表来保存散列到这里的键，这样也可以重用我们之前的代码。下面算法实现的SeparateChainingHashST使用了一个SequentialSearchST对象的数组，在put()和get()的实现中先计算散列函数来选定被查找的SequantialSearchST对象，然后使用符号表的put(和get()方法来完成相应的任务。
因为我们要用M条链表键 散列值保存N个键，无论键在各个链表中的分布如何，链表的平均长度肯定是N/M。例如，假设:所有的键都落在了第一条链表上，所有链表的平均长度仍然是0+0+…+0/M=-NIM。拉链法在实际情况中很有用，因为每条链表确实都大约含有N/M个键值对。在一般情况中，我们能够由它验证假设J并且可以依赖这种高效的查找和插入实现。
算法 基于拉链法的散列表
public class SeparateChainingHashST<Key, Value>{private int N; //键值对总数private int M; //散列表的大小private SequentialSearchST<Key, Value>[] st; //存放链表对象的教组public SeparateChainingHashST(){ this(997);}public SeparateChainingHashST(int M){//创建M条链表this.M = M;st = (SequentialSearchST<Key, Value> []) new SequentialSearchST[M];for(int i = 0; i < M; i++){st[i] = new SequentialSearchST() ;}}private int hash(Key key){ return (key. hashCode() & 0fxffffff) %M;}public Value get(Key key){return (Value) st [hash(key)].get(key); }public void put(Key key, Value val){st[hash(key)].put(key， val); }}
这段简单的符号表实现维护着一-条链表的数组，用散列丽数来为每个键选择- - 条链表。简单起见，我们使用了SequentialSearchST。在创建st[]时需要进行类型转换，因为Java不允许泛型的数组。默认的构造函数会使用997条链表，因此对于较大的符号表，这种实现比SequentialSearchST大约会快1000倍。当你能够预知所需要的符号表的大小时，这段短小精悍的方案能够得到不错的性能。一种更可靠的方案是动态调整链表数组的大小，这样无论在符号表中有多少键值对都能保证链表较短。
命题K：在一张含有M条链表和N个键的的散列表中，(在假设J成立的前提下)任意一条链表中的键的数量均在NIM的常数因子范围内的概率无限趋向于1。
简略的证明：有了假设了，这个问题就变成了一个经典的概率论问题。
性质L：在一张含有M条链表和N个键的的散列表中，未命中查找和插入操作所霄的比较次数为~NIM。
例证：在实际应用中，散列表算法的高性能并不需要散列函数完全符合假设了意义上的均匀性。自20世纪50年代以来，无数程序员都见证了命题K所预言的性能改进，即使有些散列函数不是均匀的，命题也成立。例如，图3.4.4 所示的FrequencyCounter使用的散列表(其中的hash()方法是基于Java的String类型的hashCode()方法中的链表长度和理论模型完全一致。这条性质的例外之一是在许多情况下散列函数未能使用键的所有信息而造成的性能低下。除此之外，大量经验丰富的程序员给出的应用实例令我们确信，在基于拉链法的散列表中使用大小为M的数组能够将查找和插入操作的效率提高M倍。
这篇关于【深入解析算法】基于拉链法的散列表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
