|
Linux内核哈希表分析与应用
http://blog.csdn.net/tigerjb/article/details/8450995
深入分析 Linux 内核链表
http://www.ibm.com/developerworks/cn/linux/kernel/l-chain/index.html
拿pid做hash的例子剖析 linux内核哈希查找（1）
http://blog.chinaunix.net/uid-27033491-id-3291637.html
几个问题:
如何预估hashtable的容量? 能否动态的扩容? 和nginx的hash设计一样,不能动态的扩容. 一旦估算好容量后,即使元素再多,冲突再多,也只能通过拉链法解决冲突. 查找函数是如何实现的? 由于hash容量是用户自己实现估算好的,所以,定位一个数据结果在那个hash结点时,用户自己根据hash值取模bash表大小得到结点位置. hash函数是自带的还是用户自行根据自己的数据结构实现? 散列函数的设计包括两部分 1: 从自定义数据结构散列到一个整型值. 比如将string转换为int 2: 将int散列到某个具体的hash结点. 比如教科书中的对hash表长度取模法. // 这一步非常关键
一般可以用户根据自己的数据场景,自己设计hash函数, 但是注意,自行设计的hash函数有两大风险
1) 是否高效? 2) 散列性如何? 如果散列不好,则性能会大大折扣.
3) 是否存在漏洞? 其实指的是hash漏洞,如果hash设计的不好,可能导致ddos攻击.攻击者使用精心设计的数据让hash退化为链表.
这要求在hash函数中要加入一点随机性以增加安全性.
hash_long系统也自带了一些hash函数,比如: hash_long、jhash 参考:
linux hash表的桶数量的确定
http://bbs.chinaunix.net/thread-1968247-1-1.html
Linux内核中的hash和bucket
http://www.2cto.com/os/201301/184395.html
// pidhash_shift是hash表元素最大个数对应的有效bit位个数. 举例,1024个元数对应bits:10, 2048对应:11 // 直接根据进程id得到该id在hash表的结点索引. // 内核中,一般pid的hash中桶的个数为2018. 对一应pidhash_shift为11 #define pid_hashfn(x) hash_long((unsigned long) x, pidhash_shift) unsigned long hash_long(unsigned long val, unsigned int bits) { unsigned long hash = val * 0x9e370001UL; return hash >> (32 - bits); } 参考: pid hash table
http://hi.baidu.com/zengzhaonong/item/efced6eed2d5ce0e560f1d23
正因为此函数需要传入bits参数, 所以, 一般的hash表的大小都是2的整数次方.
如果传入的初始表大小不是2的整数次方,会被调整为整数次方.
比如dentry hash表创建时,有如下两个参数:
&d_hash_shift,
&d_hash_mask, 拉链法.
linux的hash表(hhash)的设计看上去和双向链表list的基本一样,为何?
因为,linux的hhash表的设计,其实只是一个解决hash冲突的设计,也就是拉链法解决冲突设计. 冲突的原始被放置在一个单向链表里.
hash函数以及,如果根据有key定位到hash结点,都不包含在其中. 用户自己搞.
既然hash冲突的设计是拉链法,为何不直接使用list?而是自己又搞出个hlist? 当然,直接使用list解决冲突时没问题的,但是,list是个双向循环链表,其头结点包含了next,prev两个元素. 而hash的冲突链表只需要单向链表即可.也就是hash表的头结点只需要有个next元素即可. 特别的,hash结构需要大量的头结点(否则就不叫hash了),如果使用list的头结点,则浪费了一半的空间. 所以, 专门设计了hlist_head及诶单,只包含了一个元素first(相当于next)了. hash表的普通结点的占用空间消耗和list是一样的.
=============================================
struct hlist_head { struct hlist_node *first; }; struct hlist_node { struct hlist_node *next, **pprev; }; (责任编辑：IT) |