Linux内核常用数据结构——顺序表之哈希表

2024-03-15 14:32

本文主要是介绍Linux内核常用数据结构——顺序表之哈希表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、线性表

线性表按照数据结构的存储形式有分为:顺序表和链式表。

顺序表中数据存储的地址在内存中是连续的,所以可以通过计算地址实现随机存取;如:数组、哈希表等。

链式表中数据存储的地址不一定连续,只能通过结点的指针顺序存取;如:我们常用的线性链表、线性循环链表等。

二、顺序表和链式表各自优势

1.顺序表:查找速度快,尤其是哈希表可以根据关键字进行查找、更灵活和方便;缺点是内存必须提前分配好,并且必须是连续内存空间。

2.链式表:内存可以在使用是malloc随机分配;缺点是查找必须单独实现算法,而且算法查找速度慢。

以上就是时间和空间的矛盾。

三、哈希表

1.哈希表与数组的关系

区别:哈希表是通过元素关键码的值直接查找元素存储位置的数据结构;数组是通过下标可以直接访问到下标对应位置上元素的数据结构。

联系:元素的关键码通过散射/哈希函数映射得到的函数值就是哈希表数组的下标(一般的哈希表组织元素的方法还是数组)。

2.哈希冲突算法

  因为哈希函数根据关键码计算哈希表数组下标会出现不同关键码计算得到同一个数组下标的可能性;这也是散射/哈希函数不能避免的。

如“除余留数”法实现的哈希函数:hash(key) = key%17;

此时,当key为6、23、40和57时,下标值都为6;这时就需要添加冲突解决。

常用冲突解决有如下两种:

1).再哈希法:采用“再哈希”法解决冲突的哈希表是一个固定大小的结构体数组,然后给哈希表元素设置一个冲突标志位,同时、当执行哈希函数时对使用过的数组下标对应的元素冲突位置1;当下次获得的下标值对应的元素冲突位为1时,则再次利用哈希算法再次算出一个下标值。在查找时,方法类似。下边将实现这种方法。

2).链地址法:采用“链地址”法解决冲突的哈希表是一个固定大小的指针数组,数组的每个元素是一个链表(单向或双向)的头指针。将关键字作为参数、利用哈希函数计算出数据应该属于哈希表中的哪个指针数组;然后,从该指针数组所指地址处构建线性链表。Linux2.6内核的哈希表就是采用这种方法实现。

其实这种方法是将哈希查找算法和链表有机结合起来。不仅利用了hash提高查找速度,并且能很好的解决冲突;同时、比起其他哈希表,该方法中元素是指针(哈希表是一个指针数组)、这时除了指针数组元素空间需要提前分配外,具体数据存储还是动态分配的、提高了内存使用率。这种方法在内存使用率和查找效率上是一个很好的权衡。

  最后,总的来说、哈希表的查询是飞快的。因为它不需要从头搜索,它利用Key的“哈希算法”直接定位,查找非常快,各种数据库中的数据结构基本都是它。但带来的问题是,哈希表的尺寸、哈希算法。

3.看看我们的demo

test.c

#include <stdio.h>/*
关键在于creathashaddr和hashsearch函数的实现;关键点是哈希表的构造方法和哈希冲突的解决算法
本demo哈希表的构造采用“除留余数”法,处理冲突采用“再哈希”法。
而Linux2.6内核处理冲突使用的是“链地址”法、因此会看到结构体中有线性链表存在。
下面从设计思想上说下链地址法:其实这种方法是将哈希查找算法和链表有机结合起来。不仅利用了hash提高查找速度,并且能很好的解决冲突;同时、比起其他方法,
由于哈希表中元素是指针(哈希表是一个指针数组)、这时除了指针数组元素空间需要提前分配外,具体数据存储还是动态分配的、
提高了内存使用率。这种方法在内存使用率和查找效率上是一个很好的权衡。
*/#define HASH_SIZE 17
typedef struct node{char *name;int age;int flag;//标志位,当前节点是否冲突;Linux2.6内核中“链地址”法,此处是一个链表指针
}mynode;
mynode hashlist[HASH_SIZE];//创建哈希表int creathashaddr(int key)
{int i; int addr = -1;for(i=0; i < HASH_SIZE; i++){addr = key%HASH_SIZE;if(hashlist[addr].flag == 0){hashlist[addr].flag = 1;return addr;}else{//哈希冲突printf("TK------->>>>gethashaddr is chongtu!!!!!\n");//add by tankaido{addr = (key + addr%10 + 1)%HASH_SIZE;}while(hashlist[addr].flag != 0);//二次哈希冲突hashlist[addr].flag = 1;return addr;}}
}void hashsearch(int age)
{int addr = age%HASH_SIZE;if(hashlist[addr].age == age){ printf("TK--------->>>>>>hashlist[%d].name is %s\n",addr,hashlist[addr].name);return;}elseif(hashlist[addr].flag == 0){printf("TK------>>1111>>no this!\n");return;}else{//哈希冲突do{addr = (age + addr%10 + 1)%HASH_SIZE;if(hashlist[addr].age == age){printf("TK--------->>>>>>hashlist[%d].name is %s\n",addr,hashlist[addr].name);return;}}while(hashlist[addr].flag != 0);//二次哈希冲突}printf("TK------>>2222>>no this!\n");return;
}int main()
{int i;for (i=0; i<HASH_SIZE; i++)  {hashlist[i].name="";hashlist[i].age=0;hashlist[i].flag=0;}int j = creathashaddr(23);hashlist[j].name = "tan";hashlist[j].age = 23;printf("TK--------->>>>>>age is %d,hashlist[%d].name is %s\n",hashlist[j].age,j,hashlist[j].name);///j = creathashaddr(40);hashlist[j].name = "kai";hashlist[j].age = 40;printf("TK--------->>>>>>age is %d,hashlist[%d].name is %s\n",hashlist[j].age,j,hashlist[j].name);///j = creathashaddr(6);hashlist[j].name = "tankai";hashlist[j].age = 6;printf("TK--------->>>>>>age is %d,hashlist[%d].name is %s\n",hashlist[j].age,j,hashlist[j].name);int test;do{printf("#######please input user age:##########\n");scanf("%d",&test);printf("TK--------->>>>>age is %d\n",test);hashsearch(test);}while(test != 0);return 0;
}/*
gcc test.c -o test
./test
result is : 
TK--------->>>>>>age is 23,hashlist[6].name is tan
TK------->>>>gethashaddr is chongtu!!!!!
TK--------->>>>>>age is 40,hashlist[13].name is kai
TK------->>>>gethashaddr is chongtu!!!!!
TK--------->>>>>>age is 6,hashlist[10].name is tankai
#######please input user age:##########
23
TK--------->>>>>age is 23
TK--------->>>>>>hashlist[6].name is tan
#######please input user age:##########
40
TK--------->>>>>age is 40
TK--------->>>>>>hashlist[13].name is kai
#######please input user age:##########
6
TK--------->>>>>age is 6
TK--------->>>>>>hashlist[10].name is tankai
#######please input user age:##########
57
TK--------->>>>>age is 57
TK------>>2222>>no this!
#######please input user age:##########
5
TK--------->>>>>age is 5
TK------>>1111>>no this!
#######please input user age:##########
*/

gcc test.c -o test

./test

TK--------->>>>>>age is 23,hashlist[6].name is tan
TK------->>>>gethashaddr is chongtu!!!!!
TK--------->>>>>>age is 40,hashlist[13].name is kai
TK------->>>>gethashaddr is chongtu!!!!!
TK--------->>>>>>age is 6,hashlist[10].name is tankai
#######please input user age:##########
23
TK--------->>>>>age is 23
TK--------->>>>>>hashlist[6].name is tan
#######please input user age:##########
40
TK--------->>>>>age is 40
TK--------->>>>>>hashlist[13].name is kai
#######please input user age:##########
6
TK--------->>>>>age is 6
TK--------->>>>>>hashlist[10].name is tankai
#######please input user age:##########
57
TK--------->>>>>age is 57
TK------>>2222>>no this!
#######please input user age:##########
5
TK--------->>>>>age is 5
TK------>>1111>>no this!
#######please input user age:##########


这篇关于Linux内核常用数据结构——顺序表之哈希表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/812285

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

JS常用组件收集

收集了一些平时遇到的前端比较优秀的组件,方便以后开发的时候查找!!! 函数工具: Lodash 页面固定: stickUp、jQuery.Pin 轮播: unslider、swiper 开关: switch 复选框: icheck 气泡: grumble 隐藏元素: Headroom

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

linux-基础知识3

打包和压缩 zip 安装zip软件包 yum -y install zip unzip 压缩打包命令: zip -q -r -d -u 压缩包文件名 目录和文件名列表 -q:不显示命令执行过程-r:递归处理,打包各级子目录和文件-u:把文件增加/替换到压缩包中-d:从压缩包中删除指定的文件 解压:unzip 压缩包名 打包文件 把压缩包从服务器下载到本地 把压缩包上传到服务器(zip

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

常用的jdk下载地址

jdk下载地址 安装方式可以看之前的博客: mac安装jdk oracle 版本:https://www.oracle.com/java/technologies/downloads/ Eclipse Temurin版本:https://adoptium.net/zh-CN/temurin/releases/ 阿里版本: github:https://github.com/

Linux 网络编程 --- 应用层

一、自定义协议和序列化反序列化 代码: 序列化反序列化实现网络版本计算器 二、HTTP协议 1、谈两个简单的预备知识 https://www.baidu.com/ --- 域名 --- 域名解析 --- IP地址 http的端口号为80端口,https的端口号为443 url为统一资源定位符。CSDNhttps://mp.csdn.net/mp_blog/creation/editor

【Python编程】Linux创建虚拟环境并配置与notebook相连接

1.创建 使用 venv 创建虚拟环境。例如,在当前目录下创建一个名为 myenv 的虚拟环境: python3 -m venv myenv 2.激活 激活虚拟环境使其成为当前终端会话的活动环境。运行: source myenv/bin/activate 3.与notebook连接 在虚拟环境中,使用 pip 安装 Jupyter 和 ipykernel: pip instal