网络编程之 哈希表原理讲解 来自老司机的源码

#pragma once 
#define DEFAULT_SIZE 16 
/*哈希表元素定义*/
typedef struct _ListNode{
  struct _ListNode *next;
  int key;
  void *data;
}ListNode;
typedef ListNode *List;
typedef ListNode *Element;
/*哈希表结构定义*/
typedef struct _HashTable{
  int TableSize;
  List *Thelists;
}HashTable;
/*哈希函数*/
int Hash(void *key, int TableSize);
/*初始化哈希表*/
HashTable *InitHash(int TableSize);
/*哈希表插入*/
void Insert(HashTable *HashTable, int key,  void *value);
/*哈希表查找*/
Element Find(HashTable *HashTable, const int key);
/*哈希表销毁*/
void Destory(HashTable *HashTable);
/*哈希表元素中提取数据*/
void *Retrieve(Element e);

如果觉得代码太长的,博主在这里给大家将模块分解了。大家也可以观看分解之后的代码，这样
压力会小一点。 
头文件就不用说了相信大家都能看明白，就只是声明和定义结构体的类型而已。

/*根据 key 计算索引，定位 Hash 桶的位置*/ 
int Hash(int key, int TableSize) { 
    return (key%TableSize); //返回索引值
}

/*初始化哈希表*/
HashTable *InitHash(int TableSize){ //传入 哈希桶的个数,在函数内部给哈希表分配空间,再将初始化好了的哈希表传出去。
  int i = 0;
  HashTable *hTable = NULL;
  if (TableSize <= 0) {  //如果用户恶意输入数字,那么我们就可以把哈希表的个数定为我们最初的 16个
    TableSize = DEFAULT_SIZE;
  }
  hTable = (HashTable *)malloc(sizeof(HashTable));
  if (NULL == hTable){    //如果地址分配失败
    printf("HashTable malloc error.\n");
    return NULL;
  }
  hTable->TableSize = TableSize;
  //为 Hash 桶分配内存空间，其为一个指针数组 
  hTable->Thelists = (List *)malloc(sizeof(List)*TableSize);  
      //hTable->Thelists其实就是可以来指向哈希表里面的与元素了
  if (NULL == hTable->Thelists){  //分配空间失败,打印错误,然后返回
    printf("HashTable malloc error\n");
    free(hTable);
    return NULL;
  }
  //为 Hash 桶对应的指针数组初始化链表节点 
  for (i = 0; i < TableSize; i++){
    hTable->Thelists[i] = (ListNode *)malloc(sizeof(ListNode));//也就是给头节点分配空间地,这样后续就能完成插入了
    if (NULL == hTable->Thelists[i]){   //如果分配失败,那我们就释放之前分配了的空间地址,以免造成内存泄漏
      printf("HashTable malloc error\n");
      free(hTable->Thelists);
      free(hTable);
      return NULL;
    } else
    {
      memset(hTable->Thelists[i], 0, sizeof(ListNode));   //将好小标指向的元素全部清空。主要是防止意外情况。
    }
  }
  return hTable;
}

/*哈希表插入元素，元素为键值对*/
void Insert(HashTable *HashTable, int key, void *value)
{
  Element e = NULL, tmp = NULL;   //e用来接收查找后的e,tmp是用来插入的
  List L = NULL;  //定位到第几个哈希桶,和我们的find中的L的作用是一样的。
  e = Find(HashTable, key);   //现在就找到了对应的第几个哈希桶的第一个节点了。或者是NULL
  if (NULL == e){ //如果接收到的e为空的话我们就可以进行插入元素的操作了
    tmp = (Element)malloc(sizeof(ListNode));   // 因为我们接收到的是NULL所以非配空间为了插入
    if (NULL == tmp)
    {
      printf("malloc error\n");
      return;
    }
    L = HashTable->Thelists[Hash(key, HashTable->TableSize)];   //\定位到第几个哈希桶
    //经典的头插法
    tmp->data = value;
    tmp->key = key;
    tmp->next = L->next;
    L->next = tmp;
  } else
    printf("the key already exist\n");
}

Element Find(HashTable *HashTable, int key)
{
  int i = 0;  //目的接受调用HashTable函数返回的索引值
  List L = NULL;  //定位到(第几个哈希桶)指针数组里面的第几个头结点。
  Element e = NULL;  //指向定位到的(第几个哈希桶)的第一个节点（第一个节点是不包括头结点的哦）。
  i = Hash(key, HashTable->TableSize);
  L = HashTable->Thelists[i];
  e = L->next;
  while (e != NULL && e->key != key) //目的是为了遍历对应的哈希桶是否存在相同的key值。
    e = e->next;
  return e;   //返回两种情况,找到了就返回e对应的结构体,失败了就返回NULL
}

/*哈希表删除元素，元素为键值对*/
void Delete(HashTable *HashTable, int key){ //key是你要删除的第几个位置的键值对
  Element e = NULL, last = NULL;  
  List L = NULL;
  int i = Hash(key, HashTable->TableSize);    //找到对应的i是第几个
  L = HashTable->Thelists[i]; //找到对应的第几个哈希桶
  last = L;   //让last 等于 对应的第几个哈希桶的头结点
  e = L->next;    //e指向对应的第几个哈希桶的第一个节点。
  while (e != NULL && e->key != key) {    //遍历对应的哈希桶的全部链表,结束条件是 找到了要删除的key或者是遍历完成
    last = e;   //last为e也就是以后要删除的结点的上一个结点
    e = e->next;    //指向后面的结点
  }
  if (e) {//如果键值对存在,那么就可以删除了。
    last->next = e->next;   
    delete(e);
  }
}

/*哈希表元素中提取数据*/
void *Retrieve(Element e)   //在元素e存在的情况下降找到的 e->data 返回出去
{
  return e ? e->data : NULL;  //三目运算符
}
/*销毁哈希表*/
void Destory(HashTable *HashTable)
{
  int i = 0;
  List L = NULL;
  Element cur = NULL, next = NULL;
  for (i = 0; i < HashTable->TableSize; i++)  //将所有的哈希桶都遍历完成
  {
    L = HashTable->Thelists[i];
    cur = L->next;
    while (cur != NULL) //将对应的链表全部销毁,跳出之后只有头结点没有销毁了
    {
      next = cur->next;
      free(cur);
      cur = next;
    }
    free(L);    //释放那一个头结点
  }   //完成之后所有的哈希桶全部销毁
  free(HashTable->Thelists);  //释放那个二级指针
  free(HashTable);    //释放哈希表。
}