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

来源：15-2 学完整个课程，再回顾一下这三篇文章，可能有不一样的体会

Heartlaughter

2020-05-14

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

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

写回答

2回答

Heartlaughter

提问者

2020-05-15

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

liuyubobobo

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

2020-05-16

共1条回复