首页 > 其他分享 >【数据结构】散列表

【数据结构】散列表

时间:2023-08-05 20:11:06浏览次数:63  
标签:表长 列表 关键字 查找 key 数据结构 散列

这种查找结构与线性表和树形结构都不同,前两者的共同特点是关键字与记录位置之间没有确定关系,需要从一个起点不断进行比较查找位置。
image
可以知道散列表(哈希表)是一种完全不同机制的查找结构,不采用基于比较选择的查找机制,而是直接在关键字与位置之间建立映射。
所以在讨论它时也和上面的几种查找结构的思路不同。

1.散列函数的构造方法

image
构造散列函数需要参考的几个原则。

几种常用的散列函数
1.直接定址法
根据关键字的线性函数值来取地址 如H(key) = a ×key +b
优点:计算简单,不会有冲突(因为查找表中不会有重复的关键字)
缺点:若关键字分布不连续,则存储空间浪费较多
2.除留余数法
最常用
H(key) = key % p
地址等于关键字key除p取余的结果

关于如何选择合适的除数p:
p一定要小于散列表的表长m(这里的表长注意是查找表的长度,而不是关键字的个数,所以除数p不能大于m,大于的话得到的余数就可能大于表长,这时就溢出了)
p应该是一个质数,并且要在一定范围内尽可能大,p在小于m的情况下取值越大则冲突的可能性越小,反之p越小则冲突可能性越大。p取质数也是为了尽量减少冲突
p如果过大的话也会有缺点,在关键字个数一定的情况下,可以得知余数p取得太大的话会造成很大的空间浪费(空隙太多)

3.数字分析法
4.平方取中法
image
数字分析法这里讲的太拉了
image

标签:表长,列表,关键字,查找,key,数据结构,散列
From: https://www.cnblogs.com/satsuki26681534/p/17608534.html

相关文章

  • C/C++ 数据结构五大核心算法之贪心算法_钱币找零问题
    贪婪算法(贪心算法)是指在对问题进行求解时,在每一步选择中都采取最好或者最优(即最有利)的选择,从而希望能够导致结果是最好或者最优的算法。贪婪算法所得到的结果往往不是最优的结果(有时候会是最优解),但是都是相对近似(接近)最优解的结果。贪婪算法并没有固定的算法解决框架,......
  • 考研数据结构——每日一题[二叉排序树]
    3786.二叉排序树你需要写一种数据结构,来维护一些数,其中需要提供以下操作:插入数值x。删除数值x。输出数值x的前驱(前驱定义为现有所有数中小于x的最大的数)。输出数值x的后继(后继定义为现有所有数中大于x的最小的数)。题目保证:操作1插入的数值各不相同。操作......
  • C/C++ 数据结构五大核心算法之回溯法-N皇后问题
    N皇后问题:在n*n的棋盘上要摆n个皇后,要求:任何两个皇后不同行,不同列也不在同一条斜线上,求给一个整数n,返回n皇后的摆法数。#include<iostream>#include<math.h>#defineN8usingnamespacestd;intq[N+1];//q[i]表示第i个皇后在第i行上的第q[i]列intcheck(i......
  • 数据结构-算法-01-算法初步
     ......
  • 树上数据结构
    树上问题树链剖分学习笔记重链剖分对树进行重链优先搜索,暴力求一条路径的复杂度为logn模板voidtree_build(intu,intfa){//重链优先搜索 siz[u]=1; f[u]=fa; hson[u]=0; for(auto&v:adj[u]){deep[v]=deep[u]+1; if(v==fa)continue; tree_build(v,u);......
  • 【数据结构 | 入门】堆栈与队列(问题引入&实现&算法优化)
    ......
  • 在线直播系统源码,移动端列表左右滑动效果
    在线直播系统源码,移动端列表左右滑动效果<view class="evaluationItem">                <scroll-view class="uni-swiper-tab" scroll-x :style="'height:'+scrollH+'px'">                    <view class="scrollx_i......
  • 前端学习笔记202305学习笔记第二十天-vue3.0-请求用户列表的数据
         ......
  • 【转载】C/C++ 通过初始化列表和构造函数内赋值初始化成员变量的区别
    【结论】一、在有些情况下,必须使用初始化列表。特别是const和引用数据成员被初始化时。二、从效率方面来说,对于内置类型或复合类型,差异不会太大,但对于非内置数据类型,差异还是很明显的【具体参考】C/C++通过初始化列表和构造函数内赋值初始化成员变量的区别_Zju_Jemery的博客-......
  • 数据结构(二)
    目录4.树4.1树和二叉树4.2二叉树4.2.1顺序结构4.2.2链式结构4.2.3二叉树的遍历4.2.4二叉排序树4.2.5平衡二叉树4.5.6哈夫曼树4.3非二叉树和森林5.图5.1图的存储结构5.1.1数组表示法5.1.2邻接表5.2图的遍历5.2.1深度优先搜索(DFS:DepthFirstSearch)5.2.2广度优先搜索(BFS:Breadt......