哈希表概述
哈希表（Hash Table）是一种基于关键字直接计算存储位置的查找技术。
基本思想
基于比较的查找最小时间开销是 级别。哈希表通过在关键字值和存储位置之间建立确定的对应关系，直接找到存储位置，突破了比较查找的下界。
核心概念
- 哈希函数：在关键字与存储位置之间建立的函数关系，用 代表关键字为 key 的记录的存储位置
- 哈希地址：哈希函数得到的存储位置
- 装填因子：（m为填入表中的结点数，n为哈希表空间大小）
- 同义词、冲突：若 ，则 k1 和 k2 称为同义词，产生冲突
- 哈希表：根据设定的哈希函数和处理冲突的方法，将一组关键字映射到地址连续的区间上
特点
哈希既是一种查找技术，也是一种存储技术，通常用于关键字数目远小于关键字所有取值的数量的场景。
链接到
- 上一个知识点：4.8 平衡二叉树
- 下一个知识点：4.10 哈希函数构造