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

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

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

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

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

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

散列冲突:

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

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

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

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

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

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

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

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

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

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

$$fi(key) = ( f(key) + di ) 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个时，都没有冲突，直接存入，如下表

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

接下来， 22, 29, 15, 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, 才有空位

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

从这个例子可以看出，在解决冲突时，会遇到如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_i 采用随机函数计算得到。这种方法称之为随机探测法。

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

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

准备多个散列函数。

$$fi(key) = RHi(key) (i=1,2,..,k)$$

这里的RH_i就是不同的散列函数. 每当发生散列冲突时，就换一个散列函数计算.

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

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

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

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

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

![内核hash表][hlist]

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

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头节点: #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);
    }
}

#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 )

hlistforeachsafe是hlistforeach的安全版本。 如果在hlistforeach的循环体内执行hlistdel操作，会导致pos的next或者prev指针指向undefined state, 出现kernel panic. hlistforeach_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; \
	})

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