linux内核jhash函数
时间: 2023-10-22 07:12:19 浏览: 77
jhash函数是Linux内核中一个用于哈希表操作的散列函数,它的实现代码可以在内核源码的"include/linux/jhash.h"头文件中找到。
jhash函数的输入参数包括要哈希的数据、数据长度和一个初始化的哈希值。函数的返回值是一个32位无符号整数,表示该数据在哈希表中的位置。
jhash函数的实现使用了一些位运算和乘法运算,以及一些常量。具体实现可以参考下面的代码:
```c
static inline u32 jhash(const void *key, u32 length, u32 initval)
{
u32 a, b, c;
const u8 *k = (const u8 *)key;
/* Set up the internal state */
a = b = c = 0xdeadbeef + length + initval;
/* All but the last block: affect some 32 bits of (a,b,c) */
while (length > 12) {
a += k[0];
a += ((u32)k[1])<<8;
a += ((u32)k[2])<<16;
a += ((u32)k[3])<<24;
b += k[4];
b += ((u32)k[5])<<8;
b += ((u32)k[6])<<16;
b += ((u32)k[7])<<24;
c += k[8];
c += ((u32)k[9])<<8;
c += ((u32)k[10])<<16;
c += ((u32)k[11])<<24;
/* Mix */
a -= c; a ^= rol32(c, 4); c += b;
b -= a; b ^= rol32(a, 6); a += c;
c -= b; c ^= rol32(b, 8); b += a;
a -= c; a ^= rol32(c, 16); c += b;
b -= a; b ^= rol32(a, 19); a += c;
c -= b; c ^= rol32(b, 4); b += a;
k += 12;
length -= 12;
}
/* Last block: affect all 32 bits of (c) */
switch (length) {
case 12: c += ((u32)k[11])<<24;
case 11: c += ((u32)k[10])<<16;
case 10: c += ((u32)k[9])<<8;
case 9: c += k[8];
case 8: b += ((u32)k[7])<<24;
case 7: b += ((u32)k[6])<<16;
case 6: b += ((u32)k[5])<<8;
case 5: b += k[4];
case 4: a += ((u32)k[3])<<24;
case 3: a += ((u32)k[2])<<16;
case 2: a += ((u32)k[1])<<8;
case 1: a += k[0];
};
/* Mix */
c ^= b; c -= rol32(b, 14);
a ^= c; a -= rol32(c, 11);
b ^= a; b -= rol32(a, 25);
c ^= b; c -= rol32(b, 16);
a ^= c; a -= rol32(c, 4);
b ^= a; b -= rol32(a, 14);
c ^= b; c -= rol32(b, 24);
return c;
}
```
在上面的代码中,rol32是一个左旋32位的宏,实现如下:
```c
#define rol32(x, n) (((x)<<(n)) | ((x)>>(32-(n))))
```
jhash函数采用了一种叫做"Bob Jenkins' Hash"的哈希算法,它被广泛应用于Linux内核中的哈希表操作中,具有较好的散列性能和分布特性。
相关推荐
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)