0

这是一些关于该主题的讲座的引述。我不明白这部分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

4

1 回答 1

1

它说: h 是从输入集 {1,...,M} 到目标集 {0,...,m-1}
的函数,更具体地说,它没有说明函数是如何形成的。
它只是说它处理一定范围的输入和一些其他范围的输出,并且它存在。

编辑:这是一个函数,而不是一个关系。

于 2012-10-04T20:33:36.707 回答