data structure

近日对于哈希表的归纳总结

A summary of Hash Table

Posted by Zaki on December 26, 2019

最近对于哈希表（Hash Table)这一块一直存在比较大的疑问，所以我试图用博客的形式整理整个哈希表的来龙去脉。

哈希表定义

哈希表（Hash table），说白了就是一种可以用来储存信息的数据结构。

哈希表里的信息主要分为两部分，一部分是key,一部分则是value，我们把它统称为哈希表的关键码值。

工作原理

哈希表需要某种线索并且其中要有某种含义或者记录，这种过程就像是你知道了某条线索，然后顺着线索得到了这条线索的信息。

通俗的来讲，如果把我的名字比如“Zaki”给到了key值，我的电活号码则是value,也就是说，如果知道了key（也就是我的名字），我们就可以知道value。

我们在这里把key和value对应了起来。那么现在我们可以通过绘制数组的形式来探讨一下。

举个简单例子，我们绘制一串数组，并且它们的index依次为 1，2，3，4

正如前提到的，我们要把线索（我的名字）和信息（我的号码）做一个对应，那么我们就要用一种函数的形式把它表示出来，这就是哈希函数（Hash Function)。

哈希函数的作用就类似于去定位一个特殊的线索，评估它然后生成某个特定的index数字，然后它会告诉我们，这个信息在数组的哪个位置储存。

我们可以认为哈希函数的工作是如下面所示

####指令

  Hash(key)->index

接着上面那个例子，我们可以将它假设，我的名字和号码在哈希函数中所生成的index为3

####指令

  Hash(Zaki)->3

那么我的名字和号码现在就去到了数组index为3的位置，值得注意的是，哈希函数对于它的key，都是唯一的，也就是说，无论我什么时候输入Key(我的名字)，哈希函数所运行出来的index都会是3，永远不会变。

那么现在如果用*来表示我的名字和号码，它现在被储存到了3这个位置。

同样的，如果有另一个人steve,假设他的哈希值为2，那么如果用¥来表示他的位置，他的名字和号码会被储存到数组index为2的位置。

那么这儿会产生一个问题，如果有一人，假设他为stark好了，我们用$来表示，stark的哈希值计算出来也为3，也就是会和Zaki在数组中的位置有一个冲突，这时应该怎么办？

这儿处理冲突的方法其实有很多种。

处理冲突的方法

首先有一种方法是开放定址法(open addressing)。这种方法就是当一个地址已经被占用的情况下，我们一次让它继续加1，加2一直这样寻找，也就是用一个增量的方式来寻找，这种我们叫线性探测再散列（Linear Probing)。当然了还有一种二次探测再散列则是先加1再减1，先加4再减4这种形式。

回到那个例子，既然stark的哈希值已经被Zaki所占用了，那么我们先让他的哈希值增量为1，即移动到下一个数组元素位置（即index为4的位置），这里没有被占用，则stark被储存 在这里。

第二种方法则为链地址法(Chaining Operations)。之前说的方法是stark的哈希值为3但是已经被占用了，链地址法不同于开放地址法用增量的形式，它会在冲突的位置，继续创造一个链。也就是说，这种方法是 将所有冲突值储存在同一线性链表中。那么stark的哈希值则会在Zaki的位置向下延伸，创造一条新链，而Stark的信息则被储存在那里。

第三种方法则是公共溢出区法，这种方法是先来的先占位置，后来冲突的部分则被保存到公共溢出区等待。比如我们认为index 5-6为公共溢出区，那么Stark的信息将会被保存到公共溢出区 即先保存到index为5的位置上。

上面则是自己简单的一个哈希表对应冲突三种不同方法的例子，下面是代码部分。

Open Addressing Quadratic Probing

####Hash.h

  typedef int ElementType;
    #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 */

####Hash.c

   #define MinTableSize (10)

    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 = malloc( sizeof( struct HashTbl ) );
   if( H == NULL )
       FatalError( "Out of space!!!" );

   H->TableSize = NextPrime( TableSize );

        /* Allocate array of Cells */
   H->TheCells = 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;

  return H;
    }
 

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

   CollisionNum = 0;
   CurrentPos = Hash( Key, 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! */
        }
    }
 

 
 HashTableRehash( 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;
 }
 /* END */



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

    void
    DestroyTable( HashTable H )
    {
        free( H->TheCells );
        free( H );
    }

下面是三种方法之一链地址法的代码。

Chaining Operations

####指令

 struct ListNode;
 typedef struct ListNode *Position;
 struct HashTbl;
 typedef struct HashTbl *HashTable;
 
 HashTable initializeTable(int Tablesize);
 void DestoyTable(HashTable H);
 Position find(ElementType Key,HashTable H);
 void Insert(ElementType Key,HashTable H);
 ElementType Retrieve(position P);
 
 #define MinTableSize(10)
 struct ListNode
 {
   ElementType Element;
   Position Next;
 };
 typedef Position List;
 struct HashTbl
 {
 int TableSize;
 List *TheLists;
 };

####initialization

 HashTable InitializeTable(int TableSize) //哈希表初始化
 {
 HashTable H;
 int i;
 if(TableSize < MinTablesize)
 {
 Error("Table size too small); 
 return NULL;
 }
 
 H=malloc(sizeof(struct HashTbl));
 if (H==NULL)
  FatalError("out of space!!!);
  
 H->TableSize=NextPrime(TableSize);
 
 H->TheLists=malloc(sizeof(List)*H->TableSize);
 if(H->TheLists==NULL)
 FataError("Out of space!!!);
 
 for(i=0;i<H->TableSize;i++)
 {
  H->TheLists[i]=malloc(sizeof(struct ListNode));
  if(H->TheLists[i]==NULL)
   FataError("out of space!!!);
  else
   H->TheLists[i]->Next=NULL;
  }
  return H;
  }

####find function

PositionFind(ElementType Key,HashTable H)
{
 Position P:
 List L;
 L=H->TheLists[Hash(Key,H->TableSize)];
 P=L->Next;
 while(P!=NULL&&P->Element!=Key)
  P=P->Next;
 return P;}

####Insertion function

 void Insert(ElementType Key,HashTable H)
 Position Pos,NewCell;
 List L;
 Pos=Find(Key,H);
 if (Pos==NULL)
 Newcell=malloc(sizeof(struct ListNode));
 if (Newcell==NULL)
   FatalError("out of space!!!);
else{
 L=H->TheLists[Hash(Key,H->TableSize)];
 NewCell->Next=L->Next;
 Newcell->Element=Key;
 L->Next=Newcell;
    }
   }
  }

更新：哈希表的双散列（Double Hashing)

双散列，即是在原有哈希函数的基础上，新增的用于解决冲突的一个新的函数。

Ex.如果给定输入89，18，49，58，69，定义哈希函数Hash(X)=Xmod10，第二散列函数为Hash2（X）=7-X（mod7);

####step1

首先我们插入89，计算得出Hash(89)=9;即我们把它储存在index为9的位置上。

####step2

当插入49时，与已经插入的89产生哈希冲突，则采用双散列函数来处理这样的哈希冲突，根据hash2(x)=7-(x mod 7)，带入49计算得到hash2(49)=7-0=7。则从第9个位置开始数7次，到了第6个位置，所以49插入到第6个位置。

####step3

当插入58时，与已经插入的18产生哈希冲突，带入hash2(58)=7-(58 mod 7)=7-2=5。则从第8个位置开始数5次到达第3个位置。

####step4

当插入69时，与已经插入的89产生哈希冲突，带入hash2(69)=7-(69 mod 7)=7-6=1。则从第9个位置开始数1次到达第1个位置。

####step5

假设插入60，与已经插入的69产生哈希冲突，带入hash2(60)=7-(60 mod 7)=7-4=3。则从第1个位置开始数3次到达第3个位置发现已有数据58，冲突，则f(2)=2*3=6，数6次到达第6个位置，与49冲突，则f(3)=3*3=9，数9次到达第9个位置，则与89冲突。则f(4)=4*3=12,12-10=2(减去tablesize)，则数两次可以插入到无数据的第2个位置。

哈希表如下图所示

# Reference

Data structure and algorithm anlysis in C (second edition)

Hash Table wiki

CATALOG
    FEATURED TAGS
    Mac 效率 开发技巧 终端 Xcode Code data structure life 影视 LaTeX Debug 笔记 PHP 网站 Lecture Computer Science 随谈 PUBG Game lecture Computer Computer Networks movie Net PGI.S IELTS Study Interview
    DEVELOP