Hash表

散列表（也叫 Hash 表）是一种应用较为广泛的数据结构，几乎所有的高级编程语言都内置了散列表这种数据结构。在现代的编程语言中，几乎都会有散列表的身影，故而难以忽视它为程序员所带来的种种便利性。散列跟数组是很相似的，较大的区别在于，数组直接通过特定的索引来访问特定位置的数据，而散列表则是先通过散列函数来获取对应的索引，然后再定位到对应的存储位置。这是比较底层的知识了，一般的散列表，在底层都是通过数组来进行存储，利用数组作为底层存储的数据结构最大的好处在于它的随机访问特性，不管数组有多长，访问该数组的时间复杂度都是O(1)。当然这是针对某些情况，在实际应用中它的时间复杂度不一定的O（1）；显而易见这是一种空间换时间的做法、

散列表有多简单呢

散列表在结构上真的是不能再简单了，它是一个包含关键字的具有固定数组的大小。每个关键字被映射到0~TableSize-1这个范围中的某个数，并且被放到适当的单元中，这个映射就叫做散列函数，当然映射的方式就是根据散列函数来制定的。最常见的就是这个关键字(Key)是几就映射到第几个单元，不过这样子的话空间利用率显然不让人感到满意。

当然要设计一个能用的散列表，在底层仅仅用普通的数组是不够的，毕竟我们需要存储的不仅仅是数值类型，还可能会存储字符串为键，字符串为值，或者以字符串为键，某个函数的指针为值 的键值对。在这类情况中，我们需要对底层的结点进行精心设计，才能够让散列表存储更多元化的数据。

无论以何种数据类型为键，我们始终都需要有把键转换成底层数组任意位置索引的能力，通过散列函数可以做到这一点。散列函数是个很考究的东西，设计得不好可能会导致频繁出现多个不同的键映射到同一个索引值的现象，这种现象称之为冲突。除此之外，每次为散列表所分配的空间是有限的，随着元素的插入，散列表会越来越满，这时，冲突的几率就越高。故而，我们需要定期对散列表进行扩张，并把已有的键值对重新映射到新的空间中去，让散列表中的键值对更加分散，降低冲突的几率。这个过程被称为 Resize。这个过程能够在一定程度上降低散列表的冲突几率，提高查找效率。

为什么不用链表来储存键值

对于链表虽然不会有所谓的冲突产生，但是对于链表来说不管是插入，查找还是删除都需要遍历整个链表，假设稍稍运气不好点最坏情况下时间复杂度可能都是O(n)，假设我们储存少量的键值。看起来是没什么问题，但是如果储存大量的键值所花费的时间成本可能真的是令人难以接受。然而对于散列来说只要保证没有冲突发生，它的时间时间复杂度都为O（1），当然这是非常理想的情况，在实际应用中复杂度往往是大于O(1)的。但是我们可以通过设计让它尽量接近O（1）或者达到O(1);

那么如何提高Hash表的查找效率呢

使用平均查找长度ASL来衡量查找效率，ASL取决于

• 散列函数
• 处理冲突的方法
• 散列表的装填因子 a=表中填入的记录数/哈希表长度

接下来是一个超级简单的散列函数

Index Hash(ElementType Key, int TableSize)
{
    return Key % TableSize;
}

这个就是前面提到的Key是几就映射到第几个位置，这个是最直观最简单的方法了，虽然是空间利用效率不怎么样，但“不也挺好的吗”。虽然空间利用率有些低，但同时也尽可能的避免了不同的键映射到相同的索引值。我觉得是利大于弊的。相比于冲突太多会降低影响效率这点来看，显然除留余数法做散列函数优于其他类型的散列函数。当然往往都是去TableSize的最大质数来避免冲突

如何避免冲突

前面所设计的散列函数真的超级十分简单，然而所分配的空间却最多只能够存储 TableSize 个键值对，这种情况下很快就会产生冲突。所谓冲突就是不同的键，经过散列函数处理之后得到相同的散列值。也就是说这个时候，它们都指向了数组的同一个位置。我们需要寻求一些手段来处理这种冲突，常见的有开放地址法以及链地址法

开放地址法

是当冲突产生的时候通过某种探测手段来在原有的数组上寻找下一个存放键值对位置。如果下个位置也存有东西了则再用相同的探测算法去寻找下下个位置，直到能够找到合适的存储位置为止。常用的大概有下面这三种。

• 线性探测法

• 平方探测法

• 伪随机探测法

线性探测法

线性探测法其实就像线性函数一样，一个自变量对应一个因变量。这样就避免了冲突的产生。，计算公式为hashNext = (hash(key) + i) mod size。举个直观点的例子，目前散列表中索引为 5 的位置已经有数据了。当下一个键值对也想在这个位置存放数据的时候，冲突产生了。我们可以通过线性探测算法来计算下一个存储的位置，也就是(5 + 1) % 7 = 6。如果这个地方也已经有数据了，则再次运用公式(5 + 2) % 7 = 0，如果还有冲突，则继续(5 + 3) % 7 = 1以此类推，直到找到对应的存储位置为止。很明显的一个问题就是当数组越满的时候，冲突的几率越高，越难找到合适的位置。这里本人比较倾向平法探测法，所以这里具体的实现代码使用平法探测法。啊还有一点就是虽然平方探测法可以有效减少聚集，但是他也是避免不了聚集的，只是比线性探测法稍微好那么一点罢了。同样也会产生二次聚集问题。

Give me your code！！！

-------fatal.h-------
#include < stdio.h>
#include < stdlib.h >

#define Error( Str )        FatalError( Str )
#define FatalError( Str )   fprintf( stderr, "%s\n", Str ), exit( 1 )

这里和下面链地址法是同一个fatal.h。专业强迫症人士表示必须要加上。

---------hashquad.h---------
/* Interface for quadratic probing hash table */
typedef int ElementType;

/* START: fig5_14.txt */
        #ifndef _HashQuad_H
        #define _HashQuad_H

        typedef unsigned int Index;
        typedef Index Position;

        struct HashTbl;
        typedef struct HashTbl *HashTable;

        HashTable InitializeTable( int TableSize );
        void DestroyTable( HashTable H );
        Position Find( ElementType Key, HashTable H );
        void Insert( ElementType Key, HashTable H );
        ElementType Retrieve( Position P, HashTable H );
        HashTable Rehash( HashTable H );
        /* Routines such as Delete are MakeEmpty are omitted */

        #endif  /* _HashQuad_H */

-------HashEntry----------
#include "fatal.h"
#include "hashquad.h"
#include <stdlib.h>
#include < bits/stdc++.h >
#define NumItems 400
#define MinTableSize (10)
using namespace std;
enum KindOfEntry
{
    Legitimate,
    Empty,
    Deleted
};

struct HashEntry
{
    ElementType Element;
    enum KindOfEntry Info;
};

typedef struct HashEntry Cell;

/* Cell *TheCells will be an array of */
/* HashEntry cells, allocated later */
struct HashTbl
{
    int TableSize;
    Cell *TheCells;
};

/* Return next prime; assume N >= 10 */

static int
NextPrime(int N)
{
    int i;

    if (N % 2 == 0)
        N++;
    for (;; N += 2)
    {
        for (i = 3; i * i <= N; i += 2)
            if (N % i == 0)
                goto ContOuter; /* Sorry about this! */
        return N;
    ContOuter:;
    }
}

/* Hash function for ints */
Index Hash(ElementType Key, int TableSize)
{
    return Key % TableSize;
}

HashTable
InitializeTable(int TableSize)
{
    HashTable H;
    int i;

    if (TableSize < MinTableSize)
    {
        Error("Table size too small");
        return NULL;
    }

    /* Allocate table */
    H = new HashTbl;
    if (H == NULL)
        FatalError("Out of space!!!");

    H->TableSize = NextPrime(TableSize);

    H->TheCells = (Cell *)malloc(sizeof(Cell) * H->TableSize);
    if (H->TheCells == NULL)
        FatalError("Out of space!!!");

    for (i = 0; i < H->TableSize; i++)
        H->TheCells[i].Info = Empty; //初始化为1

    return H;
}

Position
Find(ElementType Key, HashTable H)
{
    Position CurrentPos;
    int CollisionNum;

    CollisionNum = 0;
    CurrentPos = Hash(Key, H->TableSize);
    cout<<H->TableSize<<" ";
    while (H->TheCells[CurrentPos].Info != Empty &&
           H->TheCells[CurrentPos].Element != Key)
    /* Probably need strcmp!! */
    {
        CurrentPos += 2 * ++CollisionNum - 1;
        if (CurrentPos >= H->TableSize)
            CurrentPos -= H->TableSize;
    }
    return CurrentPos;
}

void Insert(ElementType Key, HashTable H)
{
    Position Pos;

    Pos = Find(Key, H);
    if (H->TheCells[Pos].Info != Legitimate)
    {
        /* OK to insert here */
        H->TheCells[Pos].Info = Legitimate;
        H->TheCells[Pos].Element = Key;
        /* Probably need strcpy! */
    }
}

HashTable
Rehash(HashTable H)
{
    int i, OldSize;
    Cell *OldCells;

    OldCells = H->TheCells;
    OldSize = H->TableSize;

    /* Get a new, empty table */
    H = InitializeTable(2 * OldSize);

    /* Scan through old table, reinserting into new */
    for (i = 0; i < OldSize; i++)
        if (OldCells[i].Info == Legitimate)
            Insert(OldCells[i].Element, H);

    free(OldCells);

    return H;
}

ElementType
Retrieve(Position P, HashTable H)
{
    return H->TheCells[P].Element;
}

void DestroyTable(HashTable H)
{
    free(H->TheCells);
    free(H);
}
int main(void)
{
    HashTable H;
    Position P;
    int i, j = 0;
    int CurrentSize;
    H = InitializeTable(CurrentSize = 17);
    Insert(9, H);
    Insert(13, H);
    Insert(6, H);
    Insert(2, H);
    int m=14;
    P=Find(m,H);
    cout<<P;
    if(Retrieve(P,H)==m)
    cout<<"Find！";
    else cout<<"Not Find!";
     H=Rehash(H);
    
    system("pause");
    return 0;
}

这里加上的测试代码。同时兼顾了平方探测法的特点，加上了Resize函数，具体实现为Rehash函数。

链地址法

链地址法跟开放地址法的线性探测十分相似，最大的不同在于线性探测法中的下一个节点是在当前的数组上去寻找，而链地址法则是通过链表的方式去追加结点。实际上所分配数组的每一个位置都可以称之为桶，总的来说，开放地址法产生冲突的时候，会去寻找一个新的桶来存放键值对，而链地址法则是依然使用当前的桶，但是会追加新结点增加桶的深度。

Give me your code！！！

----------fatal.h------------
#include < stdio.h >
#include < stdlib.h >

#define Error( Str )        FatalError( Str )
#define FatalError( Str )   fprintf( stderr, "%s\n", Str ), exit( 1 )    

-------hashsep.h---------
typedef int ElementType;

typedef unsigned int Index;

#ifndef _HashSep_H
#define _HashSep_H

struct ListNode;
typedef struct ListNode *Position;
struct HashTbl;
typedef struct HashTbl *HashTable;

HashTable InitializeTable(int TableSize);
void DestroyTable(HashTable H);
Position Find(ElementType Key, HashTable H);
void Insert(ElementType Key, HashTable H);
ElementType Retrieve(Position P);


#endif

#include "fatal.h"
#include "hashsep.h"
#include < stdlib.h >
#define NumItems 5
#define MinTableSize (10)

struct ListNode
{
    ElementType Element;
    Position Next;
};

typedef Position List;

/* List *TheList will be an array of lists, allocated later */
/* The lists use headers (for simplicity), */
/* though this wastes space */
struct HashTbl
{
    int TableSize;
    List *TheLists;
};

/* Return next prime; assume N >= 10 */
static int
NextPrime(int N)
{
    int i;

    if (N % 2 == 0)
        N++;
    for (;; N += 2)
    {
        for (i = 3; i * i <= N; i += 2)
            if (N % i == 0)
                goto ContOuter; /* Sorry about this! */
        return N;
    ContOuter:;
    }
}

Index Hash(ElementType Key, int TableSize)
{
    return Key % TableSize;
}

HashTable
InitializeTable(int TableSize)
{
    HashTable H;
    int i;

    if (TableSize < MinTableSize)
    {
        Error("Table size too small");
        return NULL;
    }

    /* Allocate table */
    H=new HashTbl;
    if (H == NULL)
        FatalError("Out of space!!!");

    H->TableSize = NextPrime(TableSize);

    /* Allocate array of lists */
    H->TheLists = (List*)malloc(sizeof(List) * H->TableSize);
    if (H->TheLists == NULL)
        FatalError("Out of space!!!");

    /* Allocate list headers *//*实现表头*/
    for (i = 0; i < H->TableSize; i++)
    {
        H->TheLists[i] = new ListNode;
        if (H->TheLists[i] == NULL)
            FatalError("Out of space!!!");
        else
            H->TheLists[i]->Next = NULL;
    }

    return H;
}

Position
Find(ElementType Key, HashTable H)
{
    Position P;
    List L;

    L = H->TheLists[Hash(Key, H->TableSize)];
    P = L->Next;
    while (P != NULL && P->Element != Key)
        /* Probably need strcmp!! */
        P = P->Next;
    return P;
}

void Insert(ElementType Key, HashTable H)
{
    Position Pos, NewCell;
    List L;

    Pos = Find(Key, H);
    if (Pos == NULL) /* Key is not found */
    {
        NewCell = new ListNode;
        if (NewCell == NULL)
            FatalError("Out of space!!!");
        else
        {
            L = H->TheLists[Hash(Key, H->TableSize)];
            NewCell->Next = L->Next;
            NewCell->Element = Key; /* Probably need strcpy! */
            L->Next = NewCell;S
        }
    }
}

ElementType
Retrieve(Position P)
{
    return P->Element;
}

void DestroyTable(HashTable H)
{
    int i;

    for (i = 0; i < H->TableSize; i++)
    {
        Position P = H->TheLists[i];
        Position Tmp;

        while (P != NULL)
        {
            Tmp = P->Next;
            free(P);
            P = Tmp;
        }
    }

    free(H->TheLists);
    free(H);
}

  
int main(void)
{
    HashTable H;
    Position P;
    int i, j = 0;
    int k;
     int CurrentSize;
    H = InitializeTable(CurrentSize = 13);
    for(i = 0; i < NumItems-3; i++, j += 71)
        Insert(j, H);
    for(i = 0, j = 0; i < NumItems; i++, j += 71){
         if( ( P = Find( j, H ) ) == NULL || Retrieve( P ) != j )
            printf("Error at %d\n", j);
    } 
    DestroyTable(H);
    printf("End of program.\n");
    system("Pause");
    return 0;
    }

代码经测试没有问题

除了原来的数据字段之外，还需要维护一个指向下一个冲突结点的指针，实际上就是的链表的方式。这种处理方式有个好处就是，产生冲突的时候，不再需要为了寻找合适的位置而进行大量的探测，只要通过散列函数找到对应桶的位置，然后遍历桶中的链表即可。此外，利用这种方式删除节点也是比较容易的。即便是采用了链地址法，到了一定时候还是要对散列表进行 Resize 的，不然等桶太深的时候，依旧不利于查找。

总体而言，采用开放地址法所需要的内存空间比较少，实现起来也相对简单一些，当冲突产生的时候它是通过探测函数来查找下一个存放的位置。但是删除结点的时候需要另外维护一个状态，才不至于查找链的中断。链地址法则是通过链表来存储冲突数据，这为数据操作带来不少便利性。然而，无论采用哪种方式，都需要在恰当的时候进行 Resize，才能够让时间复杂度保持在O(1)左右。

至于伪随机探测法

经过多方参考大概是这个样子【雾】

上面两个算法最大的特点在于，对于相同的地址输入，总会按照一个固定的路线去寻找合适的位置，这样以后要再从散列表中查找对应的键值对就有迹可循了。其实伪随机数也有这种特性，只要随机的种子数据是相同的，那么每次得到的随机序列都是一定的。可以利用下面的程序观察伪随机数的行为

#include < stdio.h >
#include < stdlib.h >

int main()
{
    int seed = 100;
    srand(seed);
    int value = 0;
    int i=0;
    for (i=0; i< 5; i++)
    {
        value =rand();
        printf("value is %d\n", value);
    }
}

伪随机种子是seed = 100，这个程序无论运行多少次打印的结果总是一致的，在我的计算机上会打印以下数值

value is 365
value is 1216
value is 5415
value is 16704
value is 24504

利用这个特性，我们就能够以伪随机的机制来实现伪随机探测函数randomProbing

int randomProbing(Hash *hash, int address, int size) {
  srand(address);
  while (!hash[address].isNull) {
    address = rand() % size;
  }
  return address;
}

无论采用哪种方式，只要有相同的 address 输入，都会得到相同的查找路线。总体而言，用开放地址法来解决地址冲突问题，在不考虑哈希表 Resize 的情况下，实现起来还是比较简单的。不过不难想到，它较大问题在于当散列表满到一定程度的时候，冲突的几率会比较大，这种情况下为了找到合适的位置必须要进行多次计算。另外还有个问题，就是删除键值对的时候，我们不能把键值对的数据简单地 “删除” 掉，并把当前位置设置成空。因为如果直接删除并设置为空的话会出现查找链中断的情况，任何依赖于当前位置所做的搜索都会作废，可以考虑另外维护一个状态来标识当前位置是 “空闲” 的，表明它曾经有过数据，现在也接受新数据的插入。

PSSSSS: 在这个例子中，我们可以只利用isNull字段来标识不同状态。用数值 0 来标识当前结点已经有数据了，用 1 来标识当前结点是空的，采用 2 来标识当前结点曾经有过数据，目前处于空闲状态，并且接受新数据的插入。这样就不会出现查找链中断的情况了。不过需要对上面的探测函数稍微做一些调整，这里不展开说

插入

1. 通过散列函数计算出键所对应的散列值。
2. 根据散列值从数组中找到相对应的索引位置。
3. 如果这个位置是 “空闲” 的，则插入数据。如果该键值对已经存在了，则替换掉原来的数据。4
4. 如果这个位置已经有别的数据了，表明冲突已经产生。
5. 通过特定的探测法，计算下一个可以存放的位置。
6. 返回第三步。

查找

1. 通过散列函数计算出键所对应的散列值。
2. 根据散列值从数组中找到相对应的索引位置。
3. 如果这个位置为空的话则直接返回说找不到数据。
4. 如果这个位置能够匹配当前查找的键，则返回需要查找的数据。
5. 如果这个位置已经有别的数据，或者状态显示曾经有过别的数据，表明有冲突产生。
6. 通过特定的探测法，计算下一个位置。
7. 返回第三步。

链地址法其实也类似的，可以看上面的具体实现代码。区别在于插入键值对的时候如果识别到冲突，链地址法并不会通过一定的探测法来查找下一个存放数据的位置，而是顺着链表往下搜索，增添新的结点，或者更新已有的结点。查找的时候则是沿着链表往下查找，找到目标数据则直接把结果返回。假设穷尽链表都无法找到对应的数据，表明数据不存在。

双散列

为了避免聚集，在探测时选择跳跃式的探测，即再使用一个散列函数，用来计算探测的位置。假设前面的散列函数为hash1(X)，用于探测的散列函数为hash2(X)，那么一种流行的选择是F(i) = i * hash2(X)，即第一次冲突时探测hash1(X)+hash2(X)的位置，第二次探测hash1(X)+2hash2(X)的位置。模拟表明，双散列的探测几乎和随机冲突解决方法情景相同，这使得双散列在理论上很有吸引力。不过对于平方探测就没有必要使用第二个散列函数了。这个就不在具体说了。

再散列

这个具体的实现方法在前面的开放定址法就已经实现过了，对于平法探测法，如果表的元素填的太满，实际操作估计也就比50%多一点吧。不仅运行时间较长，效率也会变慢。Insert操作也可能失败，所以一种方法是建立另一个大约两倍大的表，扫描整个原始散列表，计算每个未删除的新散列值并将其插入到新表中。具体实现可参考前面实现的源代码。

可扩散列

如果数据量太大而无法装进内存，就需要考虑检索数据所需的磁盘存取次数。前面的两种散列法在发生冲突时可能引起多个区块的读取。

可扩散列允许用两次磁盘访问执行一次查找，插入操作也只需很少的磁盘访问。它可以看作由B-树变化而来，增加 M ，使B-树的深度为1。根保存在内存中，用 D 代表根使用的位数， D 也称为目录，则目录中的项数为 2D 。树叶的元素个数最多为 M ， d**L 为树叶 L 所有元素共有的最高位的位数， d**L≤D 。下图是可扩散列的一个例子。

插入100

插入000000

可扩散列插入时，如果树叶已经满了，则增加目录大小，分裂树叶，未分裂的树叶由相邻的目录项共同指向。可以看到尽管目录被重写，但其他树叶未被访问。需要注意的是，有可能一个树叶的元素有多于 D+1 个前导位相同时需要多次目录分裂，如上图 D=2 时，插入 111010 、 111011 后再插入 111100 ；另一个问题是如果允许重复关键字，若存在超过 M 个重复关键字，则算法无效。

可扩散列提供了对大型数据库插入和查找操作的快速存取。

总结

• 散列表可以以常数时间实现Insert和Find操作，使用散列表是，注意加装填因这样的细节子也是非常重要的，否则时间界不在有效，当关键字不是短串或者整数时，需要仔细选择散列函数也是非常重要的。
• 对于链地址法，装填因子不是很大时性能并不会明显降低，但装填因子黑兽应该接近于1，对于开放定址算法，除非玩去哪不可以避免，否则装填因子不应该超过0.5，如果使用线性探测，那么性能会随着接近于1急速下降。可以通过在散列的扩充来实现。保持合理的装填因子，对于空间紧缺并且不可能声明巨大散列表的情况是很重要的。
• 二叉树也可以用来实现Insert和Find运算，虽然平均时间界为O（log N)。但是显然二叉查找树更强大，散列不可能找出最小元素。除非准确的知道一个字符串。否则对于散列表来说是不可能有效的找到它的，二叉查找树可以在一定范围内迅速查找，而且单单从时间界来看O（log N)也不必O（1）大多少，这是因为使查找树不需要多余的乘法和除法。
• 散列表的应用非常广泛，编译器使用散列表跟踪源代码中的声明变量，这种数据结构叫做符号表。还有用是在为游戏编制的程序中，当程序搜索游戏的不同行时，它要跟踪通过计算基于位置的散列函数而看到的一些位置，如果同样的位置在出现时通常经过简单的移动变换来避免昂贵的重复计算，游戏程序的这种特点一般叫做交换表。

至于可扩散列的具体实现

写是不可能写的,只能偶尔划划水这样子,才能勉强维持的了水博客这样子。