白话算法(6)中，如何将散列表理论应用于实际操作？
- 内容介绍
- 文章标签
- 相关推荐
本文共计4709个文字，预计阅读时间需要19分钟。
白话算法（6）+散列表（Hash Table）从理论到实用（中）+使用开放寻址法处理冲突+线性探测+二次探测+双重散列+不使用链接法，还有其他处理冲突的方法吗？关心自问，我不便询问这个。
白话算法(6) 散列表(Hash Table)从理论到实用（中） ● 使用开放寻址法处理碰撞 ● 线性探查 ● 二次探查 ● 双重散列 不用链接法，还有别的方法能处理碰撞吗？扪心自问，我不敢问这个问题。链接法如此的自然、直接，以至于我不敢相信还有别的（甚至是更好的）方法。推动科技进步的人，永远是那些敢于问出比外行更天真、更外行的问题，并且善于运用丰富的想象力找到新的可能性，而且有能力运用科学的方法实践的人。
如果可以不用链表，把节省下来的链表的指针所占用的空间用作空槽，就可以减少碰撞的机会，提高查找速度。
使用开放寻址法处理碰撞
不用额外的链表，以及任何其它额外的数据结构，就只用一个数组，在发生碰撞的时候怎么办呢？答案只能是，再找另一个空着的槽啦！这就是开放寻址法(open addressing)。但是这样难道不是很不负责任的吗？想象一下，有一趟对号入座的火车，假设它只有一节车厢，上来一位坐7号座位的旅客。过了一会儿，又上来一位旅客，他买到的是一张假票，也是7号座位，这时怎么办呢？列车长想了想，让拿假票的旅客去坐8号座位。过了一会儿，应该坐8号座位的旅客上来了，列车长对他说8号座位已经有人了，你去坐9号座位吧。哦？9号早就有人了？10号也有人了？那你去坐11号吧。
本文共计4709个文字，预计阅读时间需要19分钟。
白话算法（6）+散列表（Hash Table）从理论到实用（中）+使用开放寻址法处理冲突+线性探测+二次探测+双重散列+不使用链接法，还有其他处理冲突的方法吗？关心自问，我不便询问这个。
白话算法(6) 散列表(Hash Table)从理论到实用（中） ● 使用开放寻址法处理碰撞 ● 线性探查 ● 二次探查 ● 双重散列 不用链接法，还有别的方法能处理碰撞吗？扪心自问，我不敢问这个问题。链接法如此的自然、直接，以至于我不敢相信还有别的（甚至是更好的）方法。推动科技进步的人，永远是那些敢于问出比外行更天真、更外行的问题，并且善于运用丰富的想象力找到新的可能性，而且有能力运用科学的方法实践的人。
如果可以不用链表，把节省下来的链表的指针所占用的空间用作空槽，就可以减少碰撞的机会，提高查找速度。
使用开放寻址法处理碰撞
不用额外的链表，以及任何其它额外的数据结构，就只用一个数组，在发生碰撞的时候怎么办呢？答案只能是，再找另一个空着的槽啦！这就是开放寻址法(open addressing)。但是这样难道不是很不负责任的吗？想象一下，有一趟对号入座的火车，假设它只有一节车厢，上来一位坐7号座位的旅客。过了一会儿，又上来一位旅客，他买到的是一张假票，也是7号座位，这时怎么办呢？列车长想了想，让拿假票的旅客去坐8号座位。过了一会儿，应该坐8号座位的旅客上来了，列车长对他说8号座位已经有人了，你去坐9号座位吧。哦？9号早就有人了？10号也有人了？那你去坐11号吧。