数据结构之哈希表

The night's sky is so big that you must find stars with your heart.

0_01291925244503.jpg

哈希表
基本思想：在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每一个关键字和结构中一个唯一的存储位置相对应。在此，称f为哈希函数，按这个思想建立的表成为哈希表。
哈希冲突：若有不同的关键字key1 ,key2，并且key1 != key2，当f(key1) = f(key2)时，这种现象成为哈希冲突。
哈希函数的构造方法，一般都用的是除留余数法，即取关键字被某个不大于哈希表长m的数p除后所得余数为哈希地址，有如下：

 H（key） = key MOD p p <= m

用于解决哈希冲突的方法：线性探测，也就是当产生哈希冲突时，后来的关键码顺序查找哈希表，并将它插入为空的地方。但用它删除一个关键码的时候，若被删除的关键码的前一个位置为空，就找不到要删除的关键码，并且利用线性探测容易产生二次聚集，所以一般建议采用链式哈希（链地址法）来解决哈希冲突。

example：一组关键字{19,14,23,01,68,20,84,27,55,11,10,79},将它们按哈希函数H(key) = key MOD 13和链地址法处理冲突，所得到的哈希表如下：

链式哈希

代码实战：

    //基本结构定义
    #define M 13//选取求哈希地址（散列地址）的除数(哈希表的长度)
    typedef int KeyType；
    #define NIL -1
    typedef struct {}Record;//记录集
    typedef struct //key_recptr
    {
         KeyType key;
         Record *recptr;
    } ElemType;
    typedef struct HashNode//哈希表中链表的每一个节点的定义
    {
         ElemType data;
         HashNode *next; 
    }HashNode;
    typedef struct HashTable
    {
          HashNode *table[M];//指针数组
          int sum;
    }HashTable;

---

  //购买节点和释放节点
  HashNode *_BuyNode()
  {
       HashNode *s = (HashNode *)malloc(sizeof(HashNode));
       if(NULL == s)   exit(1);
       memset(s,0,sizeof(HashNode));
       return s;
  }
  
  void  _FreeNode( HashNode *p)
  {
        free(p);
  }

---

  //初始化
  void Init_Hash(HashTable *pt)
  {
       for(int i = 0;i < M;++i)
       {
            pt->table[i] = NULL;
       }
       pt->sum = 0;
  }

---

   //求哈希地址函数
   int Hash(KeyType kx)
   {
         return kx % M;
   }
   //查找函数
   int SearchNot(HashTable *pt,KeyType kx)
   {
        int pos = Hash(kx);
        HashNode *p = pt->table[pos];
        while(p != NULL && p->data.key != kx)
                     p = p->next;
        if(p == NULL)  return pos;
        else return -1;
   }
   //插入函数
    bool Insert(HashTable *pt,ElemType x)//利用头插法，时间复杂度O（1）
    {
          bool res = false;
          int pos = SearchNot(pt,x.key);
          if(pos ！= -1)
          {
                HashNode *s = _BuyNode();
                s->data = x;
                s->next = pt->table[pos];
                pt->table[pos] = s;
                pt->sum += 1;
                res = true;
          }
          return res;
    }
    //删除函数
    bool Remove(HashTable *pt,KeyType kx)
    {
          bool res = false;
          int pos = Hash(kx);
          HashNode *pr =  NULL,*p = pt->table[pos];
          while(p != NULL)
          {
                if(p->data.key == kx)
                {
                      if(pr == NULL)
                              pt->table[pos] = p->next;
                       else
                              pr->next = p->next;
                _FreeNode(p);
                res = true;
                break;
                }  
          pr = p;
          p = p->next;
          }
     return res;
    }