45｜哈希表与哈希算法：哈希表适合用在什么样的情景？
王健伟
你好，我是王健伟。
这节课我们来看一个新的数据结构——哈希表。
哈希表也叫散列表或 Hash 表，是由数组演化来的一种扩展，用于存放数据。哈希表跟数组一样，支持查询、插入、删除等操作，但哈希表的表现尤其突出，因为它大大降低了查找数据所消耗的时间。
它是怎么做到这一点的呢？这节课，我就先带你一起了解哈希表。
基本概念、适用范围及范例
哈希表不适合范围查找，不适合排序、找最大值最小值的情形，也不适合用某一个条件一次性找出一堆记录的情形，比如用性别为“男”搜索一个班级的学生。哈希表适合用诸如学生身份证号或学号来快速找到某一位学生的情形。也就是说，哈希表非常适合对于查找性能要求高，查找的数据之间彼此没有关系的场合。
以一个日常生活中的例子来说明哈希表。假设有一个小卖店，店里有 500 种不同的商品，每种商品的价格也各不相同。我们如何通过商品名称获取商品价格信息呢？传统的方法是创建一个商品数组来记录商品名称和对应的价格信息。当顾客询问某种商品的价格时，可以根据商品名称从数组的开始位置向下搜索，当搜索到该名称的商品时，也就获取到了该商品的价格。
上述方法查询商品的价格需要花费大量时间，但是人们总是希望能够根据商品的名称立刻获取到商品的价格。其实这并不难，利用一个被称为“哈希”的函数（哈希函数）就可以做到。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
哈希表及其相关概念是本文的重点内容。哈希表是一种高效的数据结构，通过哈希函数将关键字映射到存储位置，实现了快速的数据查找、插入和删除操作。文章生动地解释了哈希函数的作用和哈希表的建立过程，并介绍了哈希函数的设计要求和常见的哈希算法。此外，文章还详细介绍了哈希函数的设计方法，包括直接定址法、除留余数法、数字分析法、平方取中法、折叠法等。同时，文章提到了哈希冲突的问题，并留下了解决哈希冲突的话题。总的来说，本文通过简洁的语言和生动的例子，让读者快速了解了哈希表的基本概念和适用范围，以及哈希函数的设计和实现要求，为读者提供了一次全面的技术学习体验。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《快速上手 C++ 数据结构与算法》，新⼈⾸单¥68
《快速上手 C++ 数据结构与算法》，新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
精选留言
由作者筛选后的优质留言将会公开显示，欢迎踊跃留言。
收起评论