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

相关文章

Linux换行符的使用方法详解

《Linux换行符的使用方法详解》本文介绍了Linux中常用的换行符LF及其在文件中的表示,展示了如何使用sed命令替换换行符,并列举了与换行符处理相关的Linux命令,通过代码讲解的非常详细,需要的... 目录简介检测文件中的换行符使用 cat -A 查看换行符使用 od -c 检查字符换行符格式转换将

Linux系统配置NAT网络模式的详细步骤(附图文)

《Linux系统配置NAT网络模式的详细步骤(附图文)》本文详细指导如何在VMware环境下配置NAT网络模式,包括设置主机和虚拟机的IP地址、网关,以及针对Linux和Windows系统的具体步骤,... 目录一、配置NAT网络模式二、设置虚拟机交换机网关2.1 打开虚拟机2.2 管理员授权2.3 设置子

Linux系统中卸载与安装JDK的详细教程

《Linux系统中卸载与安装JDK的详细教程》本文详细介绍了如何在Linux系统中通过Xshell和Xftp工具连接与传输文件,然后进行JDK的安装与卸载,安装步骤包括连接Linux、传输JDK安装包... 目录1、卸载1.1 linux删除自带的JDK1.2 Linux上卸载自己安装的JDK2、安装2.1

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Spring Boot 配置文件之类型、加载顺序与最佳实践记录

《SpringBoot配置文件之类型、加载顺序与最佳实践记录》SpringBoot的配置文件是灵活且强大的工具,通过合理的配置管理,可以让应用开发和部署更加高效,无论是简单的属性配置,还是复杂... 目录Spring Boot 配置文件详解一、Spring Boot 配置文件类型1.1 applicatio

Linux卸载自带jdk并安装新jdk版本的图文教程

《Linux卸载自带jdk并安装新jdk版本的图文教程》在Linux系统中,有时需要卸载预装的OpenJDK并安装特定版本的JDK,例如JDK1.8,所以本文给大家详细介绍了Linux卸载自带jdk并... 目录Ⅰ、卸载自带jdkⅡ、安装新版jdkⅠ、卸载自带jdk1、输入命令查看旧jdkrpm -qa

Linux samba共享慢的原因及解决方案

《Linuxsamba共享慢的原因及解决方案》:本文主要介绍Linuxsamba共享慢的原因及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux samba共享慢原因及解决问题表现原因解决办法总结Linandroidux samba共享慢原因及解决

新特性抢先看! Ubuntu 25.04 Beta 发布:Linux 6.14 内核

《新特性抢先看!Ubuntu25.04Beta发布:Linux6.14内核》Canonical公司近日发布了Ubuntu25.04Beta版,这一版本被赋予了一个活泼的代号——“Plu... Canonical 昨日(3 月 27 日)放出了 Beta 版 Ubuntu 25.04 系统镜像,代号“Pluc

Linux安装MySQL的教程

《Linux安装MySQL的教程》:本文主要介绍Linux安装MySQL的教程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux安装mysql1.Mysql官网2.我的存放路径3.解压mysql文件到当前目录4.重命名一下5.创建mysql用户组和用户并修

Linux上设置Ollama服务配置(常用环境变量)

《Linux上设置Ollama服务配置(常用环境变量)》本文主要介绍了Linux上设置Ollama服务配置(常用环境变量),Ollama提供了多种环境变量供配置,如调试模式、模型目录等,下面就来介绍一... 目录在 linux 上设置环境变量配置 OllamPOgxSRJfa手动安装安装特定版本查看日志在