#散列表 hlist


[hash_link_addr]: http://data.linuxtoy.cn/image/hash_link_address.png "链接地址法"
[list]: http://data.linuxtoy.cn/image/list.jpg "双向链表"
[hlist]: http://data.linuxtoy.cn/image/hlist.jpg "哈希表"
[hlist_del_first_node]: http://data.linuxtoy.cn/image/hlist_del_first_node.jpg "哈希表删除第一个节点"
[hlist_del_second_node]: http://data.linuxtoy.cn/image/hlist_del_second_node.jpg "哈希表删除第二个节点"

hash表是为快速查找而设计的

设计思想:
通过某个函数，使得 存储位置=f(关键字)
只需要通过查找关键字而不需要比较就可以获得存储位置。这是一种散列技术,也是一种典型的空间换时间的做法。

散列技术在存储位置和它的关键字之间建立一个确定的映射f,使得每个关键字key对应一个存储位置f(key)
这种映射f称为散列函数，又称为hash函数。

散列函数将记录存储在一块连续的存储空间中，这块连续的存储空间称为散列表或者hash表.


# 散列表查找步骤

1. 存储
    存储时，通过散列函数计算关键字对应的散列地址，并按此地址存储该记录。
    
2. 查找
    查找记录时，使用同样的散列函数计算记录的散列地址，使用该散列地址访问该记录。

所以说散列技术即是一种存储方法，也是一种查找方法。
散列技术适合求解的问题是查找与给定关键值相等的记录,所以关键值必须要唯一。

散列冲突:

> 理想情况下，每个关键值通过散列函数计算出来的地址都是不一样的，但实际上，经常会遇到两个关键字通过散列函数
> 计算得到的地址相同:  key<sub>1</sub> ≠ key<sub>2</sub> ,却有f(key<sub>1</sub>) = f(key<sub>2</sub>)
> 这种现象称为冲突, 并把key<sub>1</sub> 和 key<sub>2</sub> 称为这个散列函数的同义词(synonym)


# 构造散列函数的方法

散列函数设计的原则:

1. 计算简单
    
    由于散列查找的目的是提高查找效率，如果散列函数需要复杂的计算，会消耗很多时间，那么就会大大降低查找效率。
    
2.  散列地址分布均匀
    
    尽量让散列地址均匀分布在存储空间中，保证存储空间的有效利用，并减少为处理冲突而耗费的时间。


## 直接定址法

关键字的某个线性函数值为散列地址

$$f(x) = a \times x$$

这种散列函数简单，均匀，不容易产生冲突， 但是需要预先知道关键字的分布情况，适合查找表较小且连续的情况。


## 数字分析法

如果关键字是位数较多的数字, 例如手机号码 "130xxxx1234" , 前3位是接入号，一般对应不同运营商的子品牌.
中间4位表示用户的归属地，后四位才是用户号

如果要存储某家公司员工登记表，极有可能出现前7位都是相同的，那么可以选择后4位数作为散列地址。

这种抽取的方法使用关键字的一部分来计算散列地址，在散列函数中使用得较多.
适用于处理关键字位数较大的情况.如果事先知道关键字的分布且关键字的若干位分布较均匀，可以使用这种方法。


## 平方取中法

假设关键字是1234, 它的平法是1522756, 再抽取中间的3位数227作为散列地址。
这种方式适合不知道关键字的分布情况，而位数又不是很大的情况.


## 折叠法

将关键字从左到右分隔成位数相等的几部分，将这几部分累加求和，并按散列表表长，取后几位作为散列地址。

例如关键字为： 9876543210, 散列表表长为3位, 将这个数字分为4组， 然后求和: 987 + 654 + 321 + 0 = 1962
在取后3为得到962

适用于： 事先不知道关键字的分布，适合关键字位数较多的情况.


## 除留余数法

这个方法为常用的构造散列函数的方法。

对于散列表长为m的散列函数公式为: `f(key) = key mod p`

mode表示取模(求余数), 也可以和前几种方法联合使用，例如：折叠，平方区中后再取模

这种方法的关键点在于p, 如果p选择得不好，就很容易产生同义词。

例如对于有12个记录的关键字构造散列表，使用 f(key) = key mod 12
12 15 16 21 22 25 29 38 47 56 67 78

| 下标   | 0   | 1   | 2   | 3   | 4   | 5   | 6   | 7   | 8   | 9   | 10  | 11  |
| ---    | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 关键字 | 12  | 25  | 38  | 15  | 16  | 29  | 78  | 67  | 56  | 21  | 22  | 47  |

这也由冲突的可能性，因为 $12 = 2 \times 6 = 3 \times 4$
如果关键字中有像18(3x6) 30(5x6) 42(7x6), 他们的余数都为6，也就和78对应的下标位置冲突了

对于下标中的数，如果都让p为12的话，就可能出现所有关键字都得到了0这个地址数


| 下标   | 0   | 0   | 0   | 0   | 0   | 0   | 0   | 0   | 0   | 0   | 0   | 0   |
| ---    | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 关键字 | 12  | 24  | 36  | 48  | 60  | 72  | 84  | 96  | 108 | 120 | 132 | 144 |


如果选p=11, 得到的散列表如下:

| 下标   | 1   | 2   | 3   | 4   | 5   | 6   | 7   | 8   | 9   | 10  | 0   | 0   |
| ---    | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 关键字 | 12  | 24  | 36  | 48  | 60  | 72  | 84  | 96  | 108 | 120 | 132 | 144 |


根据经验值，p通常小于等于表长(最红啊接近于p)的最小质数。


## 随机数法

[[由于随机函数生成的数是伪随机数，所以可以取关键字的随机函数值作为它的散列地址。]] $f(key) = random(key)$

这里的random是随机函数, 当关键字的长度不能确定时，可以采用这个方法构造散列函数.


选择随机函数可以考虑到下列因数:
1. 计算散列地址所需要的时间
2. 关键字的长度
2. 散列表的大小
2. 关键字的分布情况
2. 记录查找的频率


# 处理散列冲突

设计得再好的散列函数也不可能完全避免冲突.当发现$key_1 != key_2$ ,但是却有$f(key_1) = f(key_2)$, 这就称为冲突.


## 开放定址法

一旦发生了冲突，就寻找下一个空的散列地址,只要散列表足够大，总能找到空的散列地址。

$$f_i(key) = ( f(key) + d_i )  MOD  m  (d_i=1,2,3,...,m-1)$$

例如关键字集合为{12,67,56,16,25,37,22,29,15,47,48,34}, 表长为12， 散列函数为$f(key) = key MOD 12$

当计算前5个时，都没有冲突，直接存入，如下表

| 下标   | 0   | 1   | 2   | 3   | 4   | 5   | 6   | 7   | 8   | 9   | 10  | 11  |
| ---    | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 关键字 | 12  | 25  |     |     | 16  |     |     | 67  | 56  |     |     |     |

当计算第6个(37)时， f(37) = 1, 此时与25所在的位置冲突，于是使用上面的公式 f(37) = ( f(37) + 1 ) mod 12 = 2
于是就将37存入下标为2的位置。如下表.

| 下标   | 0   | 1   | 2   | 3   | 4   | 5   | 6   | 7   | 8   | 9   | 10  | 11  |
| ---    | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 关键字 | 12  | 25  | 37  |     | 16  |     |     | 67  | 56  |     |     |     |

接下来， 22, 29, 15, 47都没有冲突 ，正常存入

| 下标   | 0   | 1   | 2   | 3   | 4   | 5   | 6   | 7   | 8   | 9   | 10  | 11  |
| ---    | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 关键字 | 12  | 25  | 37  | 15  | 16  | 29  |     | 67  | 56  |     | 10  | 47  |

key=48, f(48) = 0, 与12所在的位置0冲突了，根据上述解决冲突的公式计算:

f(48) = (f(48) + 1) mod 12 = 1, 又与25所在的位置1有冲突，继续使用开放定址
f(48) = (f(48) + 2) mod 12 = 2, 还是冲突...
一直到 f(48) = (f(48) + 6) mod 12 = 6, 才有空位

| 下标   | 0   | 1   | 2   | 3   | 4   | 5   | 6   | 7   | 8   | 9   | 10  | 11  |
| ---    | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 关键字 | 12  | 25  | 37  | 15  | 16  | 29  | 48  | 67  | 56  |     | 22  | 47  |

把这种解决冲突的开放定址法称为线性探测法.

从这个例子可以看出，在解决冲突时，会遇到如48和37这种本来不是同义词，却要争夺同一个地址的情况，称为堆积。

由于堆积的出现，需要不断处理冲突，导致存入和查找的效率大大降低。

考虑到这样一种情况: 对于最好一个key=34, f(key) = 10, 与22所在的位置冲突，可以22后面已经没有位置了，反而它前面后一个空位置，
尽管可以不断求余数得到最后结果，但效率太差了.

因此可以改进 $d_i = 1^2, -1^2, 2^2, -2^2, ..., q^2, -q^2, q \le m/2$

还有另外一种方法，处理冲突时，位移量d<sub>i</sub> 采用随机函数计算得到。这种方法称之为随机探测法。

这里的随机函数生成的其实是伪随机数，只要使用相同的seed, 则得到的随机数序列是确定的.

$$f(key) = (f(key) + d_i) MOD m (m是一个 随机数列)$$


## 再散列函数法

准备多个散列函数。

$$f_i(key) = RH_i(key) (i=1,2,..,k)$$

这里的RH<sub>i</sub>就是不同的散列函数. 每当发生散列冲突时，就换一个散列函数计算.


## 链地址法

换一个思路，为什么冲突了就要换地址呢，直接在原地想办法不是也可以吗?

将所有关键字为同义词的记录存在一个单链表中，称这种表为同义词子表. 在散列表中只存储所有同义词子表的头指针.

例如对于关键字集合 {12,67,56,16,25,37,22,29,15,47,48,34}, 使用除留余数法，除数为12, 可得到如下图的结构:

![链地址法示例][hash_link_addr]

链地址法对于可能造成很多冲突的散列函数来说，解决了堆积的问题，但是也带来了查找是需要遍历同义词子表的性能损耗。
如果同义词子表比较长，那么也说明了散列函数不够好.


# kernel中的hash表hlist


## hlist的数据结构

![内核hash表][hlist]

这是采用链地址法处理散列冲突的哈希表,左边是一个hlist_head类型的数组，右边是一个双向链表,每个节点的类型为hlist_node
hlist_head和hlist_node的定义如下:

```
struct hlist_head {
	struct hlist_node *first;   // 存放同义词子表的第一个节点的地址
};

struct hlist_node {
	struct hlist_node *next;    // 存放下一个节点的地址
    struct hlist_node **pprev;  // 存放上一个节点的next成员的地址
};
```

hlist的数据结构为什么要这样设计呢?

1. 哈希表的目的是快速查找，所以hash桶的数量通常比较大，否则冲突的概率会很大.
2. 采用链地址法是为了解决散列冲突，设计的hash函数应保证冲突越少越好,所以同义词子表的长度应该越小越好.

为了做到既能维护一张大表，又能节省内存，所以头节点和普通节点使用了不同的数据结构。
由于hash桶的数量比较大，所以头节点中只有包含一个指针.
而由于同义词子表的长度不会太大，所以双向链表带来的内存开销占的权重不大.

hlist_node为何要让pprev指向上一个节点的next成员的地址呢?

采用传统的next, prev指针的链表如下图

![传统双向链表][list]

对第一个节点和后面的节点的处理会不一致，也会影响效率.

例如删除非第一个节点的代码如下:
```
void list_del(struct list_head* entry)
{
    struct list_head *prev, *next;
    
    prev = entry->prev;
    next = entry->next;
    
    next->prev = prev;
    prev->next = next;
}
```

由于头节点和其他节点才有不同的数据类型，所以第1个节点的prev不能指向头节点,也就无法构成一个完整的双向链表.
如果要删除的节点是第1个节点，那么上述代码就无法工作，需要使用另外的接口才能完成.

hlist巧妙地将pprev指向前一个节点的next指针的地址。对于节点提供了一致的操作.
```
void hlist_del(hlist_node* entry)
{
    struct hlist_node *next, **pprev;
    
    next = entry->next;
    pprev = entry->pprev;
    
    *pprev = next;
    if (next) {
        next->pprev = entry->pprev;
    }
}
```

hlist删除非第一个节点:

![hlist删除非第一个节点][hlist_del_second_node]

![hlist删除第一个节点][hlist_del_first_node]

pprev指向了头节点中first的地址，所以通过*pprev可以改变first的指向.


## hlist operations


### 初始化节点

定义hlist头节点:
`#define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }`

初始化hlist普通节点:
```
static inline void INIT_HLIST_NODE(struct hlist_node *h)
{
    h->next = NULL;
    h->pprev = NULL;
}
```

判断节点是否在hash链表中
```
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;
}
```


### 插入节点

插入到head后面(第一个节点)
```
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之前插入
```
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;
}
```

在节点prev之后插入
```
static inline void hlist_add_behind(struct hlist_node *n, struct hlist_node *prev)
{
    n->next = prev->next;
    prev->next = n;
    n->pprev = &prev->next;
    
    if (n->next) {
        n->next->pprev = &n->next;
    }
}
```


### 删除节点

从链表中删除节点
```
static inline void __hlist_del(struct hlist_node *n)
{
    struct hlist_node **prev = n->pprev;
    struct hlist_node *next  = n->next;
    *pprev = next;
    if (next) {
        next->pprev = pprev;
    }
}
```

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

删除节点，并重新初始化节点
```
static inline void hlist_del_init(struct hlist_node *n)
{
    if (!hlist_unhashed(n)) {
        __hlist_del(n);
        INIT_HLIST_NODE(n);
    }
}
```


### 遍历hlist

```
#define hlist_for_each(pos, head) \
    for (pos = (head)->first; pos; 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_safe是hlist_for_each的安全版本。
如果在hlist_for_each的循环体内执行hlist_del操作，会导致pos的next或者prev指针指向undefined state, 出现kernel panic.
hlist_for_each_safe使用了中间变量n来保存pos->next, 在本次循环结束后在将n赋值给pos
({n = pos->next; 1;}) 的值始终为true, 不影响原来的循环条件.

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

#define hlist_entry_safe(ptr, type, member) \
	({ typeof(ptr) ____ptr = (ptr); \
	   ____ptr ? hlist_entry(____ptr, type, member) : NULL; \
	})
```

hlist_entry_safe是hlist_entry的安全版本，保证了ptr不会为空指针.