这是一些关于该主题的讲座的引述。我不明白这部分h : {1,...,M} -> {0,...,m-1}
(符号)。有人可以解释一下这是什么意思吗?例如“从 M 哈希函数中选择的哈希函数 h,它返回 1 和 m-1 之间的值”??
谢谢。
散列
我们假设关于哈希表的所有基础知识都已在 61B 中涵盖。
我们将做一个简化的假设,即我们想要散列的键已被编码为整数,并且这些整数在范围内
{1,...,M}
。我们还假设使用链表处理冲突。假设我们正在使用一个大小为 m 的表,我们选择了一个哈希函数
h : {1,...,M} -> {0,...,m-1}
,并且在某个时刻,键Y1,...,Yn
已插入数据结构中,并且我们想要查找、插入或删除该键X。这种操作的运行时间将是元素 Yi 的一个大哦,这样h(yi) = h(x)
。............
............
资料来源:www.cs.berkeley.edu/~luca/cs170/notes/lecture9.pdf