知识卡片
散列查找以桶缩小候选集
先计算键的散列并映射到桶,再在桶内查找满足相等关系的元素。链地址法允许多个键映射到同一桶;相等键必须产生相同散列,但相同散列不代表键相等,仍需比较。
若 n 个元素、b 个桶且分布均匀,平均链长为负载因子 α=n/b;计算散列和比较的成本也应计入。散列糟糕或敌对输入可让单条链增长到 n,最坏查找 O(n)。
126说明原集合不需排序,映射到空桶可直接判定不存在;非空桶需要按键相等规则逐项核对,查询和插入必须使用一致的散列与相等关系。
127以31进制多项式字符串散列、262143个桶和213557个单词举例;03258显示空桶116186个,非空桶为145957个,平均每非空桶约1.46项。图03257中缓存值为0时重新计算,真实哈希为0也会重复计算。
03256–03257展示的Java字符语义是char值及32位整数运算,并非一般UTF-8字节;完美散列只保证针对指定键集合无冲突,未知键仍需验证。原文大小与指针字节数为历史平台假设。
128将均匀散列的平均查找描述为 O(1);需要负载因子受控、散列与相等比较成本有界。动态扩容的平均成本、冲突链节点及对象布局也应计入;历史4字节指针和内存估算不能套用所有运行时。
131将固定词表中字符串最长长度视作常数;若键长随输入增长,散列与相等比较应显式计入键长,而非无条件 O(1)。均匀散列、负载因子有界且操作成本受控时,链式查询期望 O(1+α),集中冲突最坏 O(n)。
03264标注的部分负载因子与正文 n=213557、α=n/b 不符,例如 b=262143 时约0.815而非3.5;表格不可直接当作该定义的计算结果。扩容也带来重散列成本,03263和03265展示特定实验的查找与构建权衡。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 散列查找以桶缩小候选集
- · 输入/输出
- · 使用环境
- · 驱动因素
- · 分析
原书出处 · 5 处
- · 查看原书依据
基于散列的查找 前面讨论的查找算法在处理小数据量(顺序查找)或者有序的数据集合(二分查找)时才使用。我们需要更加强大的算法能够查找较大的集合,而且并不需要有序。最常使用的一个方法是使用散列函数来将目标元素的一个或者多个特征转换成一个值,这个值用来索引一个已经索引的散列表。基于散列的查找有着比本章描述
- · 查看原书依据
散列表A时也不会尝试去保持其有序性。 基于散列的查找的输入是散列表A,以及寻找的目标元素t。如果t在A[h]的指向的链表中,算法返回真,这里h=hash(t)。如果A[h]是空或者不在A[h]指向的链表中,那么返回假表示t不在A中(也就是说也不在C中)。图5-3的伪代码是一个简化版,存储在A中的列表
- · 查看原书依据
hashCode()方法是key()函数。 例5-6:Java hashCode样例 因为hashCode方法尽量尝试优化,它缓存了已经计算过的散列值,避免重复计算(例如,当且仅当散列是0时的计算值)。 下一步,我们构造散列表。我们有n个字符串,那么散列表A的大小应该是多少呢?在最理想的情况下,A有
- · 查看原书依据
平均时间将是常数,也就是O(1)。 有其他的影响实现的因素。主要都是关于如何处理集合的静态或者动态特性。在我们的例子中,我们知道我们的单词表有多大,并且我们不会在单词表中添加或者删除单词,至少不会在程序执行时操作。但是,如果我们有一个动态的集合,会做很多插入或者删除元素的操作,我们必须为散列表选择一
- · 查看原书依据
负载因子,α=n/b,b是散列表中桶的数量,n是存储在散列表中元素的数量。负载因子表示的是在单个链中的平均元素数量。 在链中寻找元素的最坏时间是O(n),只有在所有的元素都被映射到表中同样的桶时。要查找的桶的平均数目是α。如果希望能够知道详细的分析,请参见(Cormen等,2001)的第11章。 表