如何实现一个 Map

和同事聊天的时候提到了一个有趣的面试题,如何实现一个 Map

Map 的核心在于哈希,利用哈希在一段连续的存储空间上实现键值对存储。

假设现有一段连续的存储空间,有一组 key 和 value 需要存储。

首先将 key 哈希成值,映射到存储空间的某个地址,在这个地址上存储下 key 和对应的 value,读取时采用同样的哈希算法将 key 哈希后映射到地址,由于是直接寻址,效率要比数组高的多。

还有一个关键问题就是如何处理碰撞,即两个不同的 key 哈希后映射到同一个地址了,教科书上有各种方法的总结,我们讨论了两种:

方法一,向后延续,即碰撞后将后来的键值对存储在映射地址的下一个地址。

方法二,使用链表,将映射的地址指向一个链表,将映射到此地址的键值对都添加到链表里。

解决碰撞有一个先决条件就是要在存储空间中同时记录 key 和 value,防止在读取时无法分辨碰撞的 value

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容