【查找算法】哈希查找法
本篇文章将介绍一种新的查找算法——哈希查找。
文章目录
- 何为哈希查找?
- 散列表
- 冲突
- 构造散列函数
- 直接定址法
- 除留余数法
- 解决冲突的方式
- 开放地址法
- 链地址法
- 查找效率分析
何为哈希查找?
先看定义:
哈希查找是通过计算数据元素的存储地址进行查找的一种方法。
哈希查找通过给定的哈希函数构造哈希表(也叫散列表),然后通过计算存储地址进行元素查找。
所以我们先来聊聊散列表。
散列表
散列是一种新的存储方式,它既不是按给定形式顺序存储,也不是毫无规律地进行存储,而是通过计算元素的存储地址实现存储。
计算元素存储地址的基本思想是:记录的存储位置与关键字之间存在对应关系,这个对应关系称为一个hash函数。
举个例子,现有一个数据元素序列,{1,3,5,7,9},若规定每个元素k的存储地址H(k) = k,则其存储结构
还没有评论,来说两句吧...