【查找算法】哈希查找法

Myth丶恋晨 2023-07-07 15:57 26阅读 0赞

本篇文章将介绍一种新的查找算法——哈希查找。

文章目录

  • 何为哈希查找?
  • 散列表
  • 冲突
  • 构造散列函数
    • 直接定址法
    • 除留余数法
  • 解决冲突的方式
    • 开放地址法
    • 链地址法
  • 查找效率分析

何为哈希查找?

先看定义:

哈希查找是通过计算数据元素的存储地址进行查找的一种方法。

哈希查找通过给定的哈希函数构造哈希表(也叫散列表),然后通过计算存储地址进行元素查找。

所以我们先来聊聊散列表。

散列表

散列是一种新的存储方式,它既不是按给定形式顺序存储,也不是毫无规律地进行存储,而是通过计算元素的存储地址实现存储。

计算元素存储地址的基本思想是:记录的存储位置与关键字之间存在对应关系,这个对应关系称为一个hash函数。

举个例子,现有一个数据元素序列,{1,3,5,7,9},若规定每个元素k的存储地址H(k) = k,则其存储结构

发表评论

表情:
评论列表 (有 0 条评论,26人围观)

还没有评论,来说两句吧...

相关阅读