数据结构之哈希表（hash）代码

大家好，又见面了，我是你们的朋友全栈君。

   哈希的关键在于算法，呵呵，我这算法，不说了，见笑了。哈希在内核中用得非常之广，准确来说是链表，下面是一个相对简单的例子，希望能对大家理解hash有些帮助。

/**************************************************************************************************************
 **文件:hash.c
 **编写者:huangminqiang
 **编写日期:2010年2月8号
 **简要描述:
 **修改者:
 **修改日期:
 **注:主要在于查找，算法也比较简单、单一。
 **************************************************************************************************************/
#include <stdio.h>
#include <malloc.h>

//测试数据
static int s_data[] = {4, 3, 2, 5, 1004};

#define MAX_HASH 100
#define HASH_GEN 1000//hash因子

typedef struct _node
{

 int elm;
 struct _node *next;
}node_t;

//HASH表数据结构
typedef struct 
{

 node_t *hash[MAX_HASH];
 int count;
}hash_t;

//定义一个HASH表，用于保存测试数据
static hash_t s_hash;

//HASH函数定义
int hash_code(int data)
{

 int index = 0;
 
 //取余法
 index = data % HASH_GEN; 
 
 return index;
}

//将元素插入HASH表
int insert_hash(hash_t *phash, int data)
{

 int index = 0;
 node_t *pnode = NULL;
 node_t *phead = NULL;

 //通过HASH函数计算表索引
 index = hash_code(data);

 //将data存入index位置链表的链表头
 {

  //为data新建节点
  pnode = (node_t*)malloc(sizeof(node_t));
  pnode->elm = data;
  pnode->next = NULL;

  //取得index位置链表头
  //phead = phash->hash[index];

  if (NULL == phash->hash[index])
  {

   //phead = pnode;
   phash->hash[index] = pnode;
  }
  else
  {

   pnode->next = phash->hash[index];
   phash->hash[index] = pnode;
  }
 } 

 //更新index位置值
 //phash->hash[index] = phead;

 phash->count++;

 return 0;
}

//从HASH表查找元素
int search_hash(hash_t *phash, int data)
{

 int index = 0;
 int elm = 0;
 node_t *phead = NULL;

 //通过HASH函数计算表索引
 index = hash_code(data);

 //取得链表头
 phead = phash->hash[index];

 //从链表phead中查找data
 {

  while(1)
  {

   if (NULL == phead)
   {

    return -1;
   }

   if (phead->elm == data)
   {

    return phead->elm;
   }
   else
   {

    phead = phead->next;
   }
  }
 }

 return elm;
}

int main (void)
{

 int i = 0;

 //将元素插入HASH表
 for (i = 0; i < sizeof(s_data)/sizeof(s_data[0]); i++)
  insert_hash(&s_hash, s_data[i]);

 //在HASH表中查询元素
 {

  int data = 4;
  int ret = 0;

  ret = search_hash(&s_hash, data);
 }
 return 0;
}