hash链表

千次阅读

2014-03-23 19:29:32

hash链表概述

hash链表是hash表和链表的结合，使用比较方便。

hash链表实现

本文的hash链表实现：hash头部用单链表、其他的hash节点用双向链表。实现主要取自Linux内核实现，本文做了移植。本文代码可从http://download.csdn.net/detail/it_pcode/6632905下载。

hash实现

#ifndef HLIST_H_
#define HLIST_H_

#include <stdlib.h>
#include <stddef.h>
#include <stdio.h>
#include <time.h>
#include <string.h>

/*通过父结构体type中的成员member的已知地址ptr，来寻找当前ptr地址所属的父结构体type的地址*/
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})

/*内核预加载内容到RAM，在此不做实现*/
#define prefetch(x) (x)

/*
 * Double linked lists with a single pointer list head.
 * Mostly useful for hash tables where the two pointer list head is
 * too wasteful.
 * You lose the ability to access the tail in O(1).
 */

struct hlist_head {
	struct hlist_node *first;
};

struct hlist_node {
	struct hlist_node *next, **pprev;
};

#define HLIST_HEAD_INIT { .first = NULL }
#define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
static inline void INIT_HLIST_NODE(struct hlist_node *h) {
	h->next = NULL;
	h->pprev = NULL;
}

static inline int hlist_unhashed(const struct hlist_node *h) {
	return !h->pprev;
}

static inline int hlist_empty(const struct hlist_head *h) {
	return !h->first;
}

static inline void __hlist_del(struct hlist_node *n) {
	struct hlist_node *next = n->next;
	struct hlist_node **pprev = n->pprev;
	*pprev = next;
	if (next)
		next->pprev = pprev;
}

static inline void hlist_del(struct hlist_node *n) {
	__hlist_del(n);
	n->next = NULL;
	n->pprev = NULL;
}

static inline void hlist_del_init(struct hlist_node *n) {
	if (!hlist_unhashed(n)) {
		__hlist_del(n);
		INIT_HLIST_NODE(n);
	}
}

static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h) {
	struct hlist_node *first = h->first;
	n->next = first;
	if (first)
		first->pprev = &n->next;
	h->first = n;
	n->pprev = &h->first;
}

/* next must be != NULL */
static inline void hlist_add_before(struct hlist_node *n,
		struct hlist_node *next) {
	n->pprev = next->pprev;
	n->next = next;
	next->pprev = &n->next;
	*(n->pprev) = n;
}

static inline void hlist_add_after(struct hlist_node *n,
		struct hlist_node *next) {
	next->next = n->next;
	n->next = next;
	next->pprev = &n->next;

	if (next->next)
		next->next->pprev = &next->next;
}

/*
 * Move a list from one list head to another. Fixup the pprev
 * reference of the first entry if it exists.
 */
static inline void hlist_move_list(struct hlist_head *old,
		struct hlist_head *new) {
	new->first = old->first;
	if (new->first)
		new->first->pprev = &new->first;
	old->first = NULL;
}

#define hlist_entry(ptr, type, member) container_of(ptr,type,member)

#define hlist_for_each(pos, head) \
	for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
	     pos = pos->next)

#define hlist_for_each_safe(pos, n, head) \
	for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
	     pos = n)

/**
 * hlist_for_each_entry	- iterate over list of given type
 * @tpos:	the type * to use as a loop cursor.
 * @pos:	the &struct hlist_node to use as a loop cursor.
 * @head:	the head for your list.
 * @member:	the name of the hlist_node within the struct.
 */
#define hlist_for_each_entry(tpos, pos, head, member)			 \
	for (pos = (head)->first;					 \
	     pos && ({ prefetch(pos->next); 1;}) &&			 \
		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
	     pos = pos->next)

/**
 * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
 * @tpos:	the type * to use as a loop cursor.
 * @pos:	the &struct hlist_node to use as a loop cursor.
 * @member:	the name of the hlist_node within the struct.
 */
#define hlist_for_each_entry_continue(tpos, pos, member)		 \
	for (pos = (pos)->next;						 \
	     pos && ({ prefetch(pos->next); 1;}) &&			 \
		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
	     pos = pos->next)

/**
 * hlist_for_each_entry_from - iterate over a hlist continuing from current point
 * @tpos:	the type * to use as a loop cursor.
 * @pos:	the &struct hlist_node to use as a loop cursor.
 * @member:	the name of the hlist_node within the struct.
 */
#define hlist_for_each_entry_from(tpos, pos, member)			 \
	for (; pos && ({ prefetch(pos->next); 1;}) &&			 \
		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
	     pos = pos->next)

/**
 * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 * @tpos:	the type * to use as a loop cursor.
 * @pos:	the &struct hlist_node to use as a loop cursor.
 * @n:		another &struct hlist_node to use as temporary storage
 * @head:	the head for your list.
 * @member:	the name of the hlist_node within the struct.
 */
#define hlist_for_each_entry_safe(tpos, pos, n, head, member) 		 \
	for (pos = (head)->first;					 \
	     pos && ({ n = pos->next; 1; }) && 				 \
		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
	     pos = n)

#endif /* HLIST_H_ */

hash链表实例

首先实现了自己的hash list初始化、键存在与否判定以及key值查找等函数。然后是主测试程序。

#define MAX_LEN 20

struct hash_node {
	struct hlist_node hnode;
	int age;
};

struct hlist_head hashead[MAX_LEN];

void init_hlist() {
	int i = 0;
	for (i = 0; i < MAX_LEN; i++) {
		INIT_HLIST_HEAD(&hashead[i]);
	}
}

int key_exists(struct hlist_head *head, int key) {
	struct hash_node * node;
	struct hlist_node *hlistnode;
	hlist_for_each_entry(node, hlistnode, head,hnode) {
		if (node->age == key) {
			return 1;
		}
	}
	return 0;
}

struct hash_node * hlist_search(int age) {
	struct hash_node *node, *data;
	int i = 0;
	struct hlist_node *hlistnode;
	for (i = 0; i < MAX_LEN; i++) {
		hlist_for_each_entry(node, hlistnode, &hashead[i],hnode) {
			data = container_of(&node->hnode, struct hash_node, hnode);
			if (data->age == age) {
				return data;
			}
		}
	}
	return NULL;
}

void testhlist() {

	init_hlist();
	int i = 0;
	struct hash_node * node;
	struct hlist_node *hlistnode;

	srand(time(NULL));
	for (i = 0; i < 4 * MAX_LEN; i++) {
		node = malloc(sizeof(struct hash_node));
		INIT_HLIST_NODE(&node->hnode);
		node->age = rand() % (4 * MAX_LEN);
		if (key_exists(&hashead[node->age % MAX_LEN], node->age) == 0) {
			hlist_add_head(&node->hnode, &hashead[node->age % MAX_LEN]);
		}
	}
	for (i = 0; i < MAX_LEN; i++) {
		printf("head %d has member :", i);
		hlist_for_each_entry(node, hlistnode, &hashead[i],hnode) {
			printf("%d  ", node->age);
		}
		printf("\n");
	}

	for (i = 0; i < MAX_LEN; i++) {
		node = hlist_search(i);
		if (NULL != node) {
			printf("found %d\n", i);
			hlist_del(&node->hnode);
		}
	}
	printf("after clear \n");
	for (i = 0; i < MAX_LEN; i++) {
		printf("head %d has member :", i);
		hlist_for_each_entry(node, hlistnode, &hashead[i],hnode) {
			printf("%d  ", node->age);
		}
		printf("\n");
	}

}

在main函数里，调用主测试程序即可。

更多相关内容

HASH链表
千次阅读 2019-04-19 10:18:06
一，HASH链表与逻辑读 oracle要从高速缓冲区中拿到5号文件1234号块buffer的信息，就需要使用到HASH算法。 Buffer Cache:高速缓冲区中包含多个buffer,每一个buffer就记录一个数据块对应的缓冲信息。 Buffer Header:...
Oracle内核技术揭密_吕海波学习笔记

一，HASH链表与逻辑读

oracle要从高速缓冲区中拿到5号文件1234号块buffer的信息，就需要使用到HASH算法。
Buffer Cache:高速缓冲区中包含多个buffer,每一个buffer就记录一个数据块对应的缓冲信息。
Buffer Header:每一个Buffer Cache都有一个Buffer Header(BH)，它用来记录这个高速缓冲区中所有的buffer address(BA),通过BA可以定位到缓冲区中的buffer。
Buffer Bucket:它里面只记录一系列Buffer Header双向链的链表头信息，oracle通过文件号和块号计算出HASH值，来定位到相应的Bucket,当不同Buffer Header下的buffer计算HASH值发生冲突时就会定位到同一个bucket，这时多个Buffer Header会构成一个双向链，叫cache buffer chain链表(CBC链表)，并将链表头信息记录在bucket中。

Bucket数量由隐藏参数_db_block_hash_buckets决定：
```
SQL> SELECT   ksppinm, ksppstvl, ksppdesc FROM   x$ksppi x, x$ksppcv y WHERE   x.indx = y.indx AND  ksppinm = '_db_block_hash_buckets';

KSPPINM                    KSPPSTVL      KSPPDESC
----------------------     ---------    -------------------------------------
_db_block_hash_buckets     262144        Number of database block hash buckets
```
搜索buffer步骤如下：
1，进程根据要访问块的文件号和块号，计算HASH值得到到数字X。
2，根据HASH值X,定位到相应HASH Bucket，如BucketX。
3，搜索Bucket后的链表，查找哪个Buffer Header(BH)是目标BH。
4，找到目标BH后，从中取出Buffer的Buffer Address(BA)。
5，按BA访问Buffer

上述为oracle逻辑读的过程，如果搜索Bucket后的BH链表，没有找到包含目标块的BH，就说明目标块不在缓存中，只能物理读了。

二，catch buffer chain latch 与buffer pin 锁

SGA是公共内存，因此在访问buffer时是需要锁保护机制的，oracle采用的锁机制是latch和mutex。

正常情况下一个bucket后面的catch buffer chain就需要一个catch buffer chain latch来保护，但latch也是占用空间的，于是oracle这里是一个CBC latch负责多个bucket的锁管理。一个latch的大小为192字节：
```
SQL> select to_number(b.addr,'xxxxxxxxxxxxxxxxxxxxx')- 
            to_number(a.addr,'xxxxxxxxxxxxxxxxxxxxx')
     from (select rownum rid,addr from v$latch_children where name='cache buffers chains' order by addr) a,
          (select rownum rid,addr from v$latch_children where name='cache buffers chains' order by addr) b 
     where a.rid=b.rid+1 and rownum <=1;

TO_NUMBER(B.ADDR,'XXXXXXXXXXXXXXXXXXXXX')-TO_NUMBER(A.ADDR,'XXXXXXXXXXXXXXXXXXXX
--------------------------------------------------------------------------------
                                                                             192
```
当我们搜索CBC链表时，需要先获取CBC latch进行锁保护；当找到目标所在BH，访问buffer前要修改buffer pin进行锁保护，修改完buffer pin后就可以释放CBC latch ，后续的buffer访问只需要在buffer pin保护下进行即可；当访问完buffer需要释放buffer pin时，这时又需要CBC latch 来保护。CBC latch的功能就是保护CBC链的访问和buffer pin的修改。

buffer pin锁有多种模式，常见的为共享模式(S)和独占模式(X)。在没有加锁时buffer pin值为0。

CBC latch也有共享和独占两种模式，模式的选择取决于以下4个要素：

1）对象类型（唯一索引，非唯一索引等）

2）块类型（根块，叶块，表块等）

3）操作（读，修改）

4）访问路径

对于一般的逻辑读，我们在读取buffer信息前都需要修改buffer pin值，这时的CBC latch基本都是独占锁。步骤如下：

当我们要访问索引的叶块时，需要频繁的访问它的根块和枝块，但对根块和枝块修改的频繁度又很低，这时没有必要使用独占模式的CBC latch。优化后的步骤如下：

可以看到在CBC latch 共享模式中搜索CBC链表和访问buffer，中间没有修改buffer pin,也没有释放CBC latch，这样CBC latch的加载时间比独占模式要长，但它缓解了独占模式下的争用。

在有唯一索引、唯一索引扫描情况时，根块、枝块、叶块、表块都是使用共享模式的CBC latch。也就是说当唯一索引使用‘where id = ?’这样的等值条件查询时，就使用共享模式的CBC latch；当使用的是范围查询时，则和非唯一索引一样，只有根块、枝块共享模式的CBC latch，不修改buffer pin，而叶块、表块还是使用独占模式的CBC latch。可以理解为使用索引唯一访问路径时，所有块的访问都是共享模式的CBC latch；另外，rowid方式直接逻辑读表块时是使用独占模式的CBC latch。

除了唯一索引外，在多数情况下，读或者写表块，都是使用独占模式的CBC latch。

另外根块和枝块，只要不修改，就使用共享模式的CBC latch。
收起
展开全文
oracle 内核

linux内核之哈希链表

千次阅读 2020-09-22 20:50:36

本文只是对linux内核中的链表进行...由上图可以知道hash链表中存在两种结构体，一种是hash表头，一种是hash节点。 hash表头： struct hlist_head{ struct hlist_node *first; }; 表头里面只存放一个hlist_node的指.

本文只是对linux内核中的链表进行分析。内核版本是2.6.32。文件在：/include/linux/hlist.h。

一、简述哈希表

根据设定的哈希函数H(key)和处理冲突的方法将一组关键字映像到一个有限的连续的地址集上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为哈希表。

大家对数组的概念想必都不陌生，众所周知，数组通过数组号就可以找到对应的存储的数据，时间复杂度O（1）。但数组的缺点也很明显，不便于增删数据。

大家对双向链表的概念也一定不陌生，双向链表比起数组，增删方便，但是查找数据就需要遍历整个链表，时间负责度O（n）。

如果可以有一种数据结构，既增添方便，也可以直接进行数据的访问而不必O（n）比较那就太好了。哈希表就是这样的一种折中。

二、哈希函数的构造

可以想象，如果一个索引号对应着不止一个数据，那这时候就会有矛盾产生。我们有必要构造哈希函数来使一组关键字的哈希地址尽量均匀分布在整个地址区间中，从而减少冲突。

常用构造哈希函数的方法有：

（1）直接定址法
（2）数字分析法
（3）平方取中法
（4）折叠法
（5）除留余数法
（6）随机数法

三、处理冲突的方法

常用的处理冲突的方法有：

（1）开放定址法（Linux glib库hash表GHashTable）
（2）再哈希法
（3）链地址法
（4）建立一个公共溢出区

四、Linux内核关于hash链表的使用

linux内核中的哈希链表和其他链表不一样。他是头节点用单个的链表，只有next指针，但其他链表节点是有next和prev两个指针的双链表。

在这里插入图片描述
由上图可以知道，linux内核处理冲突的方法是链地址法，hash链表中存在两种结构体，一种是hash表头，一种是hash节点。

hash表头：
struct hlist_head{ 
	struct hlist_node *first;
};
表头里面只存放一个hlist_node的指针，指向链表。

hash节点：
struct hlist_node{
	struct hlist_node *next; 
	struct hlist_node **pprev;
};
有两个指针，所以链表是双链表。但和一般的双链表又有点不一样，
next自然是指向链表的下一个节点，但pprev则不是指向当前节点的前一个节点，
而是指向当前节点的前一个节点的next指针。所以ppre是二级指针。

为什么要设计成这样呢？因为为了统一操作，如果设计的和我们平时使用的双链表的话（prev指向的是前一个节点），那头节点和链表节点之间的操作就要重新定义一套（因为头结点结构体和链表节点结构体是不一样的）。所以干脆直接指向前一个节点的next指针，next的类型是hlist_node*，first的类型也是hlist_node*。这样就统一了链表操作函数了。

还有个问题：为什么头结点要设计的和链表节点不一样呢？官方解释是为了节约空间，因为一般来说哈希表中有非常多的表项，即可能有上千个表项，也即是有上千个hlist_head。如果头结点不用pprev则可以节约非常大的空间。我个人认为还有种解释是头结点的pprev（如果有这个指针）用处不大。因为所有的操作都是要通过哈希函数来算出值在哈希表中的位置，然后再有链表中查找。哈希链表本来就是个处理碰撞现象的，说明链表中的关键字通过哈希函数后能得到一样的值。所以你不知道在链表中的哪个位置，那头结点有pprev的话你也没必要从后面开始查找（也许从前面查找开些，也许是从后面）。也就是说对于头节点来说这个指针可有可无。

/*
 * Double linked lists with a single pointer list head.
 * Mostly useful for hash tables where the two pointer list head is
 * too wasteful.
 * You lose the ability to access the tail in O(1).
 */
// 哈希节点，这是个表头，注意只有一个first指针。这是为了有多个哈希链表时，可以减少空间上的浪费
struct hlist_head {
	struct hlist_node *first;
};
// 这个哈希链表和其他链表不一样，单指针表头双循环链表。所以头节点和其他节点不一样。
// 下面是链表节点有两个指针，next是指向下一个节点，pprev则是指向前一个节点的next，表头则是first。
// 所以pprev是二级指针
struct hlist_node {
	struct hlist_node *next, **pprev;
};
// 初始化哈希链表头节点
#define HLIST_HEAD_INIT { .first = NULL }
#define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
// 让某个节点变成空节点
static inline void INIT_HLIST_NODE(struct hlist_node *h)
{
	h->next = NULL;
	h->pprev = NULL;
}
// 这是个设计的非常巧妙的函数，因为pprev是指向前一个节点的next，
// 所以如果h节点在链表上则*pprev是指向自己的。如果不在则指向空的。
static inline int hlist_unhashed(const struct hlist_node *h)
{
	return !h->pprev;
}

// 判空函数，h是头节点，判断first是否为空来判断hash链表是否存在。
static inline int hlist_empty(const struct hlist_head *h)
{
	return !h->first;
}

// 这是个删除n节点的函数。n节点的前后节点指针指向改变了，
// 但n节点的指针指向没有改变。
static inline void __hlist_del(struct hlist_node *n)
{
	struct hlist_node *next = n->next;
	struct hlist_node **pprev = n->pprev;
	*pprev = next;
	if (next)
	next->pprev = pprev;
}
// 在上面函数的基础上，改变了被删除的n节点指向。
static inline void hlist_del(struct hlist_node *n)
{
	__hlist_del(n);
	n->next = LIST_POISON1;
	n->pprev = LIST_POISON2;
}

// 先判断将被删除的n节点是否在链表中，在则删除，然后初始化该节点。
static inline void hlist_del_init(struct hlist_node *n)
{
	if (!hlist_unhashed(n)) {
		__hlist_del(n);
		INIT_HLIST_NODE(n);
	}
}
// 这个函数是在头节点后面，增加一个节点。
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
	struct hlist_node *first = h->first;
	n->next = first;
	if (first)
		first->pprev = &n->next;
	h->first = n;
	n->pprev = &h->first;
}

/* next must be != NULL */
// 把n节点增加到next节点前面
static inline void hlist_add_before(struct hlist_node *n, struct hlist_node *next)
{
	n->pprev = next->pprev;
	n->next = next;
	next->pprev = &n->next;
	*(n->pprev) = n;
}

// 把n节点增加到next节点后面
static inline void hlist_add_after(struct hlist_node *n, struct hlist_node *next)
{
	next->next = n->next;
	n->next = next;
	next->pprev = &n->next;
	
	if(next->next)
		next->next->pprev  = &next->next;
}

/*
 * Move a list from one list head to another. Fixup the pprev
 * reference of the first entry if it exists.
 */
// 这是个替换函数，把new头节点替换掉old头结点，然后让old节点为NULL
static inline void hlist_move_list(struct hlist_head *old, struct hlist_head *new)
{
	new->first = old->first;
	if (new->first)
		new->first->pprev = &new->first;
	old->first = NULL;
}

#define hlist_entry(ptr, type, member) container_of(ptr,type,member)
// 下面的都是遍历函数，这个是简单的遍历函数
#define hlist_for_each(pos, head) \
for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
    pos = pos->next)
 
// 这个是带有存储临时变量的遍历函数
#define hlist_for_each_safe(pos, n, head) \
for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
    pos = n)

/**
 * hlist_for_each_entry - iterate over list of given type
 * @tpos: the type * to use as a loop cursor.
 * @pos: the &struct hlist_node to use as a loop cursor.
 * @head: the head for your list.
 * @member: the name of the hlist_node within the struct.
 */
 // 这是个加了tpos（数据类型），且是从头节点开始的遍历
#define hlist_for_each_entry(tpos, pos, head, member)\
for (pos = (head)->first;\
    pos && ({ prefetch(pos->next); 1;}) &&\
({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
    pos = pos->next)

/**
 * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
 * @tpos: the type * to use as a loop cursor.
 * @pos: the &struct hlist_node to use as a loop cursor.
 * @member: the name of the hlist_node within the struct.
 */
 // 这个和上面的函数功能差不多，只是是从pos的下一个节点开始遍历，而非头节点
#define hlist_for_each_entry_continue(tpos, pos, member)\
for (pos = (pos)->next;\
    pos && ({ prefetch(pos->next); 1;}) &&\
({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
    pos = pos->next)

/**
 * hlist_for_each_entry_from - iterate over a hlist continuing from current point
 * @tpos: the type * to use as a loop cursor.
 * @pos: the &struct hlist_node to use as a loop cursor.
 * @member: the name of the hlist_node within the struct.
 */
 // 这是从pos节点开始的遍历。
#define hlist_for_each_entry_from(tpos, pos, member)\
for (; pos && ({ prefetch(pos->next); 1;}) &&\
({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
    pos = pos->next)


/**
 * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 * @tpos: the type * to use as a loop cursor.
 * @pos: the &struct hlist_node to use as a loop cursor.
 * @n: another &struct hlist_node to use as temporary storage
 * @head: the head for your list.
 * @member: the name of the hlist_node within the struct.
 */
 // 这是数据项的遍历，且用临时变量n保存了pos数据。防止pos被删除时遍历出错。
#define hlist_for_each_entry_safe(tpos, pos, n, head, member) \
for (pos = (head)->first;\
    pos && ({ n = pos->next; 1; }) && \
({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
    pos = n)

#endif

收起

展开全文

内核数据结构

深度剖析linux内核万能--双向链表,Hash链表模版
千次阅读 2016-01-28 20:48:10

我们都知道，链表是数据结构中用得最广泛的一种数据结构，对于数据结构，有顺序存储，数组就是一种。有链式存储，链表算一种。当然还有索引式的，散列式的，各种风格的说法，叫法层出不穷，但是万变不离其中，只要...

我们都知道，链表是数据结构中用得最广泛的一种数据结构，对于数据结构，有顺序存储，数组就是一种。有链式存储，链表算一种。当然还有索引式的，散列式的，各种风格的说法，叫法层出不穷，但是万变不离其中，只要知道什么场合用什么样的数据结构，那就行了。

那么，标题说的内核万能链表，其实就是内核链表，它到底和我们平常大学学的数据结构的链表有什么不同呢？？内核链表，是在linux内核里的一种普遍存在的数据结构，比如内核调度算法中有这样的结构，摄像头驱动程序，wifi模块，G_sensor等等，用到链表的东西实在实在是太多了，看内核的人务必要懂得这样的数据结构的用法，否则你根本不知道它是怎么产生的。

内核链表，在我们学完数据结构的人看来，它很奇怪，为什么说它奇怪？因为它没有数据域，这就是内核链表和普通链表的最大区别，那有人会问，没有数据域那怎么插入数据到链表呢？还有其它的什么遍历啊，反序啊等等的操作。。。别急，内核链表最大的优势就是内核已经提供了对链表进行常见操作的函数接口&#

收起

展开全文
全面解析Linux 内核 3.10.x - Pid hash 链表
千次阅读 2015-12-25 21:31:52

内核中的pid hash链表 内核在初始化的时候有一个函数为 pidhash_init ,这个函数要做什么呢？我们都知道，我们可能在很多情况下，都想知道进程的一些状态，在这种情况，内核必须能够从进程的PID导出对应的进程...

收起

内核 Linux pid
数据结构之哈希链表Hashtable
千次阅读 2020-07-11 12:32:51

散列（Hashing）在现实中经常遇到按照给定...如图所示这就是整个hashtable的图书，其中红色部分其实是一个数组，里面存放的是链表，大家可以通过蓝色知道里面存放的是链表，绿色部分就是链表的一个结点，有数据域和...

收起

数据结构 c++ c语言
实现LRU(用双链表加hash表的方式实现时间复杂度达到O(1))
千次阅读 2022-04-24 14:14:20

我们如果不强加O(1)可以用vector实现，(删除的时候要移动元素，非常消耗时间)，我们如果要实现O(1)就需要双链表(List默认双链表)和hash表实现，list用来记录每一个bufferpool的page和其对应的pincount，hash表key是...

收起

c++ 数据库开发
哈希表的C语言链表实现
2021-11-23 11:31:28

使用C语言，初步实现了哈希表，使用“链表”的方法，Hash函数是直接“取模”运算

收起

c语言 hashtable 数据结构算法
链表法解决hash冲突
2017-10-15 19:02:00

/* @链表法解决hash冲突 * 大单元数组，小单元链表 */ #pragma once #include <string> using namespace std; template<typename map_t> struct Node { size_t key; map_t content; .....

收起
C语言链表式实现哈希表
2021-02-20 14:29:38

以下哈希表结构为：指定长度的哈希表长度，冲突的节点使用延展链表存储数据(后面统一称为冲突链表) 一、基本结构体定义 1、存储数据的结构体 /* 该结构体成员根据需要设定即可 */ typedef struct tagHashData ...

收起

数据结构哈希表哈希算法 c语言
Java简单实现链式哈希表
千次阅读 2022-02-03 16:08:05

散列表（Hash table 也叫哈希表），是通过关键码值（key value）而直接进行访问的数据结构。也就是说，它通过关键码值映射到表中的一个位置来访问记录，以加快查找的速度。这个映射函数也叫散列函数，存放记录的数组...

收起

java 散列表哈希表
哈希链表的实现C++
千次阅读 2021-12-03 13:25:05

哈希链表的实现

收起

哈希算法 c++
c语言实现hash map（链表散列hash）
千次阅读 2019-06-15 22:39:43

散列(hash)：将字符串转换为固定长度的数组或索引值的方法，叫做散列法。 hashmap的底层结构 hashmap是一个链表散列的数据结构，即是数组和链表的结合体。（也可能是数组+链表+红黑树）数组：存储空间连续，占用...

收起
一篇理解-链表，哈希表，二叉树，平衡二叉树，B树，B+树
2022-03-27 13:52:06

链表：链表的概念：链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表的结构是多式多样的，当时通常用的也就是两种：无头单向非循环列表...

收起

数据结构
HashMap的循环链表图解
千次阅读 多人点赞 2021-03-20 15:35:49

HashMap的循环链表图解 @author：Jingdai @date：2021.03.20 复习HashMap的知识点，总是看到jdk1.7前在多线程操作时可能会出现循环链表问题，不是很理解，于是研究源码并画图终于搞懂，记录一下。由于本人电脑只有...

收起

java hashmap
php数组和链表的区别总结
2020-10-16 08:47:07

在本篇文章里小编给大家整理的是关于php数组和链表的区别的相关知识点内容，有需要的朋友们可以学习下。

收起
内核通用链表哈希链表表list.h
2013-11-12 16:26:31

从内核提取出来的list.h，通用链表，哈希链表数据结构及操作函数，在用户态正常使用

收起
C语言数据结构双向链表简单实例
2021-01-01 03:31:05

双向链表的基本操作１．利用尾插法建立一个双向链表。２．遍历双向链表。３．实现双向链表中删除一个指定元素。４．在非递减有序双向链表中实现插入元素e仍有序算法。５．判断双向链表中元素是否对称...

收起
hashmap什么时候由链表转为红黑树
千次阅读 2020-12-06 14:55:24

1、链表长度大于8，官方源码如下： 2.当满足条件1以后调用treeifyBin方法转化红黑树。该方法中，数组如果长度小于MIN_TREEIFY_CAPACITY（64）就选择扩容，而不是转化为红黑树。

收起

数据结构
双向链表与hash表
2013-11-29 21:49:25

从linux内核提取出来的，双向链表和hash表实现。在普通的用户态C程序中，均可使用

收起
数组、链表和哈希表
2022-03-18 15:20:47

数组、链表和哈希表数组、链表和哈希表关系数组与链表的区别链表总结链表开源库—utlist.h哈希表开源C库—uthash简介uthash能做什么uthash包括的额外内容uthash效率简单使用定义hash数据结构从hash表查找item向hash...

收起

哈希表
HashMap中链表转为红黑树的条件
千次阅读 2021-04-15 12:36:14

HashMap中链表转为红黑树的条件 HashMap的底层是元素为链表的数组。转化条件在JDK1.8之后，HashMap中的链表在满足以下两个条件时，将会转化为红黑树(即自平衡的排序二叉树)： 1. 条件一数组 arr[i] 处存放的...

收起
c语言实现哈希表
千次阅读 2022-03-23 21:00:27

hash_node_t* hash_get_node_by_key(hash_t* hash, void* key, unsigned int key_size) { hash_node_t** bucket = hash_get_bucket(hash, key); hash_node_t* node = *bucket; if (node == NULL) { return ...

收起
判断链表是否为回文链表leetcode-data-structures-hash-tables-starter:第7周第4天的项目启动文件
2021-07-01 00:50:34

判断链表是否为回文链表 leetcode 哈希表项目从 . 学习目标比较和对比数组、链表和哈希表的属性和操作定义哈希冲突以及如何处理它们确定从哈希表中添加和删除元素的机制和复杂性使用哈希表通过缓存（记忆和制表...

收起
数组、链表、Hash的优缺点
千次阅读 2019-06-12 15:17:00

链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起。 2、数组必须事先定义固定的长度，不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存...

收起

数据结构数组
嵌入式物联网工程师，linux内核链表之HashList
2021-12-01 13:58:53

内核链表之HashList 哈希链表（HashList/hlist）的设计初衷是为了方便快捷的查找，为了降低Hash表中键的冲突，一般设计会将...Hash链表这种单头指针设计缺失了对尾结点的时间复杂度的O(1)访问。同样也带来了对不同类..

收起

物联网嵌入式硬件 linux
C++语言实现hash表详解及实例代码
2021-01-20 05:55:48

个人认为，hash表是介于链表和二叉树之间的一种中间结构。链表使用十分方便，但是数据查找十分麻烦；二叉树中的数据严格有序，但是这是以多一个指针作为代价的结果。hash表既满足了数据的查找方便，同时不占用太多的...

收起
哈希算法 C语言实现（采用链表）
千次阅读 2017-12-05 22:27:06

Hash insert(Hash h,int x,char *s) /** 哈希链表的插入 **/ { Hash p =h; while(p) /**先看看是不是空指针**/ { /**看样子是**/ if(strcmp(p->arr,s)==0) /**再看看身份证号是不是已经存在了**/ ...

收起

C语言数据结构与算法哈希算法
(001)HashMap之链表转红黑树-treefyBin方法.docx
2020-06-17 10:37:59

详细解读了HashMap中链表转红黑树的treefyBin方法，该方法中涉及到的诸如：replacementTreeNode方法、treeify方法、comparableClassFor方法、compareComparables方法、tieBreakOrder方法、balanceInsertion方法、...

收起
为什么HashMap中链表长度超过8会转换成红黑树
千次阅读 2019-08-09 17:20:57

https://www.cnblogs.com/rgever/p/9643872.html

收起

hash链表概述

hash实现

hash链表实例

HASH链表

linux内核之哈希链表

深度剖析linux内核万能--双向链表,Hash链表模版

全面解析Linux 内核 3.10.x - Pid hash 链表

数据结构之哈希链表Hashtable

实现LRU(用双链表加hash表的方式实现时间复杂度达到O(1))

哈希表的C语言链表实现

链表法解决hash冲突

C语言链表式实现哈希表

Java简单实现链式哈希表

哈希链表的实现C++

c语言实现hash map（链表散列hash）

一篇理解-链表，哈希表，二叉树，平衡二叉树，B树，B+树

HashMap的循环链表图解

php数组和链表的区别总结

内核通用链表哈希链表表list.h

C语言数据结构双向链表简单实例

hashmap什么时候由链表转为红黑树

双向链表与hash表

数组、链表和哈希表

HashMap中链表转为红黑树的条件

c语言实现哈希表

判断链表是否为回文链表leetcode-data-structures-hash-tables-starter:第7周第4天的项目启动文件

数组、链表、Hash的优缺点

嵌入式物联网工程师，linux内核链表之HashList

C++语言实现hash表详解及实例代码

哈希算法 C语言实现（采用链表）

(001)HashMap之链表转红黑树-treefyBin方法.docx

为什么HashMap中链表长度超过8会转换成红黑树

hash链表

hash链表概述

hash实现

hash链表实例

HASH链表

linux内核之哈希链表

深度剖析linux内核万能--双向链表,Hash链表模版

全面解析Linux 内核 3.10.x - Pid hash 链表

数据结构之哈希链表Hashtable

实现LRU(用双链表加hash表的方式实现时间复杂度达到O(1))

哈希表的C语言链表实现

链表法解决hash冲突

C语言链表式实现哈希表

Java简单实现链式哈希表

哈希链表的实现C++

c语言实现hash map（链表散列hash）

一篇理解-链表，哈希表，二叉树，平衡二叉树，B树，B+树

HashMap的循环链表图解

php数组和链表的区别总结

内核通用链表哈希链表表list.h

C语言 数据结构双向链表简单实例

hashmap什么时候由链表转为红黑树

双向链表与hash表

数组、链表和哈希表

HashMap中链表转为红黑树的条件

c语言实现哈希表

判断链表是否为回文链表leetcode-data-structures-hash-tables-starter:第7周第4天的项目启动文件

数组、链表、Hash的优缺点

嵌入式物联网工程师，linux内核链表之HashList

C++语言实现hash表详解及实例代码

哈希算法 C语言实现（采用链表）

(001)HashMap之链表转红黑树-treefyBin方法.docx

为什么HashMap中链表长度超过8会转换成红黑树

hash链表

C语言数据结构双向链表简单实例