Hash Table

散列表(哈希表)的定义

        用于海量数据的快速查找，效率高，时间复杂度接近 O(1)。

        散列表是根据给定一个关键字 Key(整数)，通过散列函数(映射函数)，将关键字 Key 映射到散列表(存放记录的数组)中的一个位置(数组的索引 index)， 那么 arr[index] 就填充 Key。

HashFunction(Key) = index，arr[index] = Key

两种方式寻址

直接寻址表

关键字的全域范围 U 比较小；用数组实现直接寻址表，数组的下标就是关键字的值；没有两个元素具有相同的关键字；查找、插入、删除都为 O(1)；

散列表

适用关键字的范围 U 很大；通过散列函数来计算出数组的索引，将关键字 Key，通过散列函数计算后的索引比关键字的全域 U 要小得多，这样散列表的存储空间小很多，节省空间；存在一个问题：不同的关键字，经过散列函数，可能映射到同一个索引上，这样会起冲突，所以需要解决碰撞问题；

散列函数

        假设所有元素被散列到 m 个槽中的每一个的可能性是相同的，这个假设为简单一致散列(simple uniform hashing)。

        一个好的散列函数应该近似地满足简单一致散列，每个关键字都等可能的散列到 m 个槽位上的任何一个中去，并与其它的关键字已被散列到哪一个槽位无关。

        当关键字不是自然数 N = {0, 1, 2…}，那么需要转换为自然数。例如当关键字是字符串时，可以通过将字符串中的每个字符的 ASCII 码相加，转换为自然数。

散列函数的设计方法

除法散列法(常用)         关键字 Key 映射到 m 个槽中的某一位置，散列函数为：h(Key) = Key mod m，其中 m 不应是 2 的幂，通常 m 的值是与 2 的整数幂不太接近的质数。

arr[h(Key)] = Key

乘法散列法         用关键字 key 乘上常数 A(0<A<1)，并抽取出 key*A 的小数部分。用 m 乘以这个抽取出来的小数，再对乘积向下取整(floor)。总之，散列函数为：

h(Key) = floor(m*(Key*A mod 1))； 其中 mod 1 的意思就是取小数部分。 Key*A mod 1 即为 Key*A - floor(Key*A)。

        乘法散列法的优点是对 m 的选择没什么特别的要求。一般选 m 为 2 的某次幂(2^p，p为某个整数)

全域散列法         为了尽可能地避免最坏情况的发生，我们不使用某个特定的散列函数，而是准备好一系列的散列函数，在执行开始时随机选择一个作为之后的散列函数。这种方法称作全域散列(universal hashing)。

碰撞(collision)问题

        通常有两类方法处理碰撞：开放寻址(Open Addressing)法 和 链接(Chaining)法。前者是将所有结点均存放在散列表 T[0…m-1] 中；后者通常是把散列到同一槽中的所有元素放在一个链表中，而将此链表的头指针放在散列表 T[0…m-1] 中。

开放寻址法

        开放寻址法是将所有的元素都存放在散列表中，每个表项包含一个元素或者包含 NIL，但是不包含链表或者其它的处于散列表外的辅助结构。

        当插入一个元素时，如果映射的位置已经被其它元素占用，那么需要通过散列函数再产生另一个映射值(称为探查)，直到找到空槽或发现表中没有空槽为止。

缺点：删除操作比较困难，解决这个问题的方法是引入一个新的状态 DELETED，而不是 NIL，这样在插入过程中，一旦发现 DELETED 的槽，便可以在该槽中放置数据，而查找过程不需要任何改动。

有三种方式常用来计算开放寻址法中的探查序列：线性探查、二次探查、双重探查。

线性探查(常用)

        给定一个普通的散列函数 h’:U–>{0,1,…,m-1}，称为辅助散列函数，线性探查方法采用的散列函数为

h(Key,i)=(h'(Key)+i) mod m, i = 0,1,...,m-1

        给定一个关键字 Key，首先探查槽 T[h’(Key)], 即由辅助散列函数所给出的槽位。再探测 T[h’(Key)+1]，依次类推，直到槽 T[m-1]。然后，又绕到槽 T[0], T[1],…,直到最后探测到槽 T[h’(Key)-1]。

缺点：随着连续被占用的槽不断增加，平均查找时间也随之不断增加。

二次探查

h(Key,i)=(h'(Key)+c₁i+c₂i²) mod m , i = 0,1,...,m-1

        其中 h’ 是一个辅助散列函数，c₁ 和 c₂ 为正的辅助常数，i = 0,1,…m-1。初始的探查位置为 T[h’(Key)]，后续的探查位置要加上一个偏移量，该偏移量以二次的方式依赖于探查序号i。这种探查方法的效果要比线性探查好很多，但是，为了能够充分利用散列表，c₁，c₂和 m 的值要受到限制。此外，如果两个关键字的初始探查位置相同，那么它们的探查序列也是相同的。这一性质可导致一种轻度的群集，称为二次群集。

缺点：不易探查到整个散列空间。

双重探查

        双重散列是用于开放寻址法的最好方法之一，因为它产生的排列近似于随机选择的排列。它采用如下形式的散列函数：

h(Key, i) = (h1(Key) + i*h2(Key)) mod m

其中 h1 和 h2 为辅助散列函数。初始探测位置为 T[h1(Key)]，后续的探测位置在此基础上加上偏移量 h2(Key) 模 m。

链接法(常用)

将散列到同一槽中的所有元素（冲突的元素）都放在一个链表中。

        若选定的散列表长度为 m，则可将散列表定义为一个由 m 个头指针组成的指针数组 T[0…m-1]。凡是散列地址为 i 的结点，均插入到以 T[i] 为头指针的单链表中。T中各分量的初值均应为空指针。

优点：删除操作比较方便。