首页
学习
活动
专区
工具
TVP
发布
您找到你想要的搜索结果了吗?
是的
没有找到

linux内核源码 -- list链表

linux kernel中的list估计已经被各位前辈们写烂了,但是我还是想在这里记录一下; linux kernel里的很多数据结构都很经典, list链表就是其中之一 本篇要介绍的内容: list...的定义 list提供的操作方法 注意事项 使用实例 ---- List 所在文件: List的所有操作可以在 include/linux/list.h找到; List head的定义可以在 include.../linux/types.h找到; 定义 实际上这就是一个双向循环链表, 且有一个头指针 list head的定义: struct list_head { struct list_head *next...new, struct list_head *head) { __list_add(new, head, head->next); } 在尾部插入,在最后一个元素间和头指针间插入, 因为是循环链表嘛...head); } list_entry宏 按之前说的, 这个list_head都有要嵌入到用户定义的struct中,这个宏就是由这个list_head ptr来获取当前所处的struct对象的指针, 用了linux

2.3K10

LRU 缓存机制实现:哈希 + 双向链表

算法详解 LRU 缓存机制可以通过哈希辅以双向链表实现,我们用一个哈希和一个双向链表维护所有在缓存中的键值对。...双向链表按照被使用的顺序存储了这些键值对,靠近头部的键值对是最近使用的,而靠近尾部的键值对是最久未使用的。 哈希即为普通的哈希映射(HashMap),通过缓存数据的键映射到其在双向链表中的位置。...通过哈希定位到该节点在双向链表中的位置,并将其移动到双向链表的头部,最后返回该节点的值。 ?...然后判断双向链表的节点数是否超出容量,如果超出容量,则删除双向链表的尾部节点,并删除哈希中对应的项; 如果 key 存在,则与 get 操作类似,先通过哈希定位,再将对应的节点的值更新为 value...上述各项操作中,访问哈希的时间复杂度为 O(1),在双向链表的头部添加节点、在双向链表的尾部删除节点的复杂度也为O(1)。

1.4K30

java源码之数组、链表哈希

哈希 无论是数组还是链表,其对数据的查询表现都比较无力,要想知道一个元素是否在数组或链表中,只能从前向后挨个对比。出现这个问题的根源在于,我们没有办法直接根据一个元素找到它存储的位置。...哈希就是解决查询问题的一种方案。 哈希与Hash函数 通俗来讲,哈希就是通过关键字来获取数据的一种数据结构,它通过把关键字映射为中的位置来获取元素,这种映射主要是使用Hash函数。...这是当前比较理想的方法,既继承了数组的优点,又在碰撞时继承了链表的优点,这也是哈希强大的地方之一。...哈希的优缺点 哈希是一种优化存储的思想,具体存储元素的依然是其他的数据结构。设计良好的哈希,能同时兼备数组和链表的优点,它能在插入和查找时都具备良好的性能。...然而设计不好的哈希,有可能会出现较多的哈希碰撞,导致链表过长,从而哈希会更像一个链表

1K40

Linux 内核通用链表学习小结

描述 在linux内核中封装了一个通用的双向链表库,这个通用的链表库有很好的扩展性和封装性,它给我们提供了一个固定的指针域结构体,我们在使用的时候,只需要在我们定义的数据域结构体中包含这个指针域结构体就可以了...传统的链表结构 struct node{ int key; int val; node* prev; node* next; } linux 内核通用链表库结构 提供给我们的指针域结构体...,list_add的话是在表头插入,list_add_tail是在尾插入 list_add( &(pstudent[i].list), &student_list);//参数1是要插入的节点地址...list就是student结构定义里的属性list //list_entry的原理有点复杂,也是linux内核的一个经典实现,这个在上面那篇链接文章里也有讲解 tmp_student...内核提供的这个通用链表库里面还有很多其他的接口,这里没有详细的一一举例,有兴趣的可以自己去看看,在源码包 include/linux/list.h 文件里面,不过通过阅读一些源代码确实对我们也有很大的提高

1.2K21

哈希哈希冲突

2.哈希的设计 哈希函数的设计首先不能过于复杂,复杂的哈希函数会间接的影响hash的性能;其次要求哈希值应该尽可能随机且均匀分布,避免或者减少哈希冲突的数量,使每个桶中存储的数据比较平均。...负载因子(加载因子):减少链表长度 低效扩容:乘以2进行扩容 加载因子越大,哈希中存储的元素越多,空闲的位置就越少,哈希冲突的概率就越大,插入、删除和查找数据时的性能就随之降低。...对于线性探测法当哈希中存储的元素越多时,哈希冲突的概率越高,极端情况下需要探测整个哈希,时间复杂度为O(n)。...链表法:链地址法,在具体的应用中使用较多,在哈希中每个桶对应一个链表,把哈希值相同的元素存放在相同桶位置的对应链表中,由于需要对比key值所以插入时间复杂度为O(k),查找和删除时的时间复杂度与链表的长度成正比...需要尽量减少链表长度,可以引入一个参数:负载因子或者称为加载因子。负载因子用于间接的限定链表的长度,如果值越大则允许的链表长度越大,哈希的性能越差,但是加载因子越小空间浪费越严重。

72510

BAT算法面试题--环形链表(哈希法)

二.解决方案(哈希) 思路 我们可以通过检查一个结点此前是否被访问过来判断链表是否为环形链表.常用方法,一般是使用哈希....算法 我们遍历所有的节点并在哈希中存储每个结点的引用(或内存地址).如果当前节点为空结点null,表示我们已经检测到链表的末尾的下一个节点.那么表示我们已经完成了链表的遍历,并且此链表不是环形链表.如果当前结点的引用已经存在过哈希中...,那么即可立马返回true(表示此链表为环形链表)....三.代码 Java Code 四.复杂度分析 时间复杂度: O(n),对于含有n个元素的链表,我们访问每个元素最多一次.添加一个结点到哈希中只需要花费O(1)的时间....空间复杂度:O(n),空间取决于添加哈希中的元素数目.最多可以添加n个元素. 五.学习建议 只要明白哈希,即可解决这个问题.!

19920

哈希

散列表(Hash table,也叫哈希),是根据关键码值(Key value)而直接进行访问的数据结构 。 也就是说,它通过把关键码值映射到中一个位置来访问记录,以加快查找的速度。...要求: 不使用数据库,速度越快越好=>哈希(散列) 添加时,保证按照id从低到高插入 [思考:如果id不是从低到高插入,但要求各条链表仍是从低到高,怎么解决?]...使用链表来实现哈希, 该链表不带表头[即: 链表的第一个结点就存放雇员信息] 思路分析并画出示意图 代码实现[增删改查(显示所有员工,按id查询)] ?..., 编写散列函数, 并实现Hash的增删改查方法 /** * 哈希实现数据的存储 * * @author TimePause * @create 2020-02-09 10:53 */ public...public static void main(String[] args) { //创建哈希 HashTab hashTab = new HashTab(7);

71110

哈希

什么是哈希 哈希是一种数据结构。它通过哈希函数把数据和位置进行映射,来实现快速的寻找、插入和删除操作。 哈希函数 将数据和位置进行映射的函数。...比如我们把冲突的数据用单链表链接起来。 关于扩容: 数据总数等于位置总数的时候,进行扩容。 开散列的实现 哈希类的设计: 哈希本质上和数组差不多,那么我们为了简单起,用vector容器进行存储。...首先是存储一个键值对,其次还要进行链接,这里我们使用单链表进行链接每个元素的类型,所以要有该类型的指针。...HashDate HashDate; vector _hash; size_t _size = 0; public: }; 插入 插入是时候首先要判断该数据是否已经存在在哈希中...,没有存在哈希中的时候,在进行插入。

24330

哈希

哈希结合了顺序链表两者的优势,顺序随机访问快,链表插入删除元素快。那么怎么将两者结合呢?...只需要判断下数组66索引下的值是否为1 时间复杂度 O(1) 3.场景三 现在又轮到A不乐意了,A觉得他为了几个数字,却要花销100个内存,于是又和B商量 最后,商量结果为:建立一个索引和数字之间的关系,哈希就诞生了...哈希 搞明白了哈希的结构后,理解它也十分简单,键值对中的key,代表了链表数组中的索引,通过hash算法获取索引,之后只需要O(1)的时间就可以获取到value,当然前提是该索引下的链表元素只有1个...存放元素也是同样道理,通过key获取到数组索引后,判断该索引下的链表是否为空,如果为空,直接存入,否则遍历链表,如果有key相同的,直接替换,没有key相同的放入链表头部 下面是一个简单的带有存放和获取的哈希...this.value = value; this.hashCode = hashCode; } } } 简单的哈希就到这边了

61740

哈希

哈希是种数据结构,它可以提供快速的插入操作和查找操作。第一次接触哈希时,它的优点多得让人难以置信。不论哈希中有多少数据,插入和删除(有时包括侧除)只需要接近常量的时间即0(1)的时间级。...哈希运算得非常快,在计算机程序中,如果需要在一秒种内查找上千条记录通常使用哈希(例如拼写检查器)哈希的速度明显比树快,树的操作通常需要O(N)的时间级。...哈希也有一些缺点它是基于数组的,数组创建后难于扩展某些哈希被基本填满时,性能下降得非常严重,所以程序虽必须要清楚中将要存储多少数据(或者准备好定期地把数据转移到更大的哈希中,这是个费时的过程)。...哈希算法 用上述得到的数值作为对应记录在中的位置,得到下表: ? 哈希算法 上面这张哈希。...哈希算法 2、再哈希法 当发生冲突时,使用第二个、第三个、哈希函数计算地址,直到无冲突时。缺点:计算时间增加。 3、链地址法 将所有关键字为同义词的记录存储在同一线性链表中。 ?

72770

哈希

哈希 哈希,又称散列表,是一种储存键值对的数据结构。 哈希的基础思想是拿空间换时间,哈希的期望复杂度是 O(1) 的。...一般来说,对于某 key 值,哈希后得到对应的下标,代表其在哈希中的位置。...哈希冲突 哈希冲突是哈希极力避免的情况。...如果不考虑哈希冲突,就会出现误判的情况。而要解决哈希冲突,往往会使哈希复杂度退化。 不同的实现方法,本质上就是用不同方法避免哈希冲突。 桶 可以将桶看做一种特殊的哈希,存储整数型的键值对。...在 \operatorname{hash}(key) 冲突时,在 ht[key] 处创建链表,将元素加入链表即可。 在查询时,遍历对应位置的链表。 最劣情况下,单次操作是 O(n) 复杂度的。

1.2K20

哈希

哈希,又叫散列表,是数据结构的一种。 散列表用途很广泛,比如一个电话薄,每一个姓名对应一个电话号码。姓名与电话号码呈映射关系。假如要创建一个电话薄,可以使用 JavaScript 对象来实现。...b' 和 '=' 并不是一样的,但得到的哈希值却一样,这就是冲突。解决冲突的办法大致有两种。...将稀疏数组的每一项不再直接存储数据,而是使用链表或者数组存储数据,这样有相同的 hash 值时,只需将新的一项插入到数组或链表中即可,最好使用链表,因为如果做删除操作时,链表可以更容易删除要删除的项。...我们让 key 可以是字符串也可以是数字,当是数字时,把数字当作数组的索引,返回对应稀疏数组索引对应的链表的第一项。当是别的类型时,求哈希值再找对应的数据。...不需要引入其它的数据结构就能实现哈希。 对于链表,可以看这篇文章:链表的实现 当有新的值进入哈希时,先判断稀疏数组对应的索引处有没有存储数据,如果有了则往后查找空的存储单元然后存入数据。 ?

81730

哈希

哈希 文章内有一些词语和插图,他是方便大家理解,并对算法产生浓厚的兴趣! 不要根据一些注释,过分曲意理解作者哦!!!!...哈希概述 这个就是我今天要给家人们带来的哈希哈希,别名儿叫散列表,洋名儿叫 Hash Table。 我在上面说,希望有种方法,直接看到数,就知道它在数组中的位置,其实里就用到了哈希思想。...存储时,通过同一个哈希函数的计算 key 的哈希地址,并按照此哈希地址存储该 key。 最后形成的就是哈希,它主要是面向查找的存储结构,简化了比较的过程,提高了效率。...链地址法呢是将得出同一个结果的 key 放在一个单链表中,哈希存储每条单链表的头指针。...当然有得必有失,这样的情况必然造成了查找上的性能损耗,这里的查找的时间复杂度为 O(k),其中 k = n / 单链表条数。 结语和附录 好啦,到这里哈希就讲完辣,是不是看起来还挺简单的。

41010

哈希

# 哈希 哈希 是一种使用 哈希函数 组织数据,以支持快速插入和搜索的数据结构。 有两种不同类型的哈希哈希集合 和 哈希映射。 哈希集合 是集合数据结构的实现之一,用于存储非重复值。...我们常用的散列冲突解决方法有两类,开放寻址法(open addressing)和链表法(chaining)。 # 装载因子 当哈希中空闲位置不多的时候,散列冲突的概率就会大大提高。...# 链表法 在哈希中,每个 “桶(bucket)” 或者 “槽(slot)” 会对应一条链表,所有散列值相同的元素我们都放到相同槽位对应的链表中。 链表法比起开放寻址法,对大装载因子的容忍度更高。...基于链表的散列冲突处理方法比较适合存储大对象、大数据量的哈希,而且,比起开放寻址法,它更加灵活,支持更多的优化策略,比如用红黑树代替链表。...链表法 开放寻址法适用于数据量比较小、装载因子小的场景。 链表法适用于存储大对象、大数据量的哈希。比起开放寻址法,它更加灵活,支持更多的优化策略,比如用红黑树代替链表

96820

哈希函数和哈希

哈希就是这么做的,一会再说!...哈希函数映射 哈希 哈希就是利用哈希函数,可以根据关键码而直接进行访问的数据结构,也就是将关键码(Key value)通过哈希函数映射到中的一个位置来进行访问。...由于是直接访问,所以对于哈希的元素理论上的增删改查时间复杂度都是O(1)。 ?...处理冲突的方法有: 开放地址法 再散列法 公共溢出法 拉链法(经典、重点) 我们来说下拉链法,也如上图所示,拉链法的思路很简单,就是当发生哈希冲突后,会在当前地址区域建立一个链表,将冲突目标添加到链表中去...如果在Linux下使用hash_map,一定要加上一个__gnu_cxx的命名空间声明!

1.5K20
领券