开放地址法和封闭地址法，开放哈希法和封闭哈希法

Question

我在某本高教社出版的数据结构书中翻阅到了和波波老师讲的很近似的一个概念

转念一想好像和我以前学过波波老师的好像是反着的，结果再重新看视频发现真的是反的。这是两个不同的概念(开放地址法和开放哈希法)吗？

Answer 1

提问者 Heartlaughter 2020-05-15 15:14:41

就是我记得您好像在课程中在哈希表这一章最后说过，seperate chaining是一种封闭地址法，因为那M个元素的数组中，只能根据所算得的哈希码到固定的索引下存储。但是开放地址法，您课程中举例的线性探测法和平方探测法好像说的是开放地址法，因为他们虽然会计算出一个哈希码，但他们有可能不会存储在对应的索引下。 于是我看到这本书，他讲的是开放哈希法，然后他把链地址法归类到了开放哈希法之下，这与您讲的，把链地址法归类于封闭地址法之下有点不一样。(这就是我想说的相反，因为他说的开放，您说的封闭)于是我就想，封闭地址法是不是就是开放哈希法，开放地址法是不是就是封闭哈希法？ 可能有点绕(书上后面讲的线性探测法，它归类成了封闭哈希法，然后这与您讲的开放地址法，emmm又相反了，这就是我所说的相反) 希望我这一次表达明白了相反?，对之前言语没表达清晰表示抱歉鸭～

• liuyubobobo #1

  明白你的意思了。开放地址和封闭地址是对应的，对象是“地址”；开放哈希和封闭哈希是对应的，对象是“哈希”。所谓的开放地址是指，每一个地址是否只对一个哈希值有效？链地址法每一个地址只容忍一个哈希值，同样哈希值的元素在同一个地址组成一个链，所以叫封闭地址；但是开放地址法则一个地址有可能被其他哈希值的元素占据（当初是哈希值所在的地址产生冲突的时候）。开发哈希和封闭哈希的概念，你的这本书上的定义没问题。连地址是开放哈希的；开放地址法是封闭哈希的。

Answer 2

liuyubobobo 2020-05-15 05:42:09

我不太了解你说的“反着”是什么意思。

这段内容说的是，开放哈希/封闭哈希 是一个比某种具体处理哈希冲突的方法更大的概念。

链地址法是一种开放哈希法，还有其他的开放哈希法；

开放地址法是一种封闭哈希法，还有其他的封闭哈希法。

开放哈希和封闭哈希这个概念我在课程中并没有讲。其实我个人认为这个概念本身挺小众的。

继续加油！：）