数据结构深入剖析（19）--Hash

一、      哈希技术

1.    哈希的定义：在数据元素的存储位置和它的关键字之间建立一个映射关系f，通过f可以直接得到关键字所代表的数据元素。

2.    哈希表：哈希技术中用于存储数据元素的数据结构。

3.    哈希函数：哈希技术中的映射关系f。

4.    哈希的一些常用操作

创建哈希

销毁哈希

清空哈希

加入键值对

删除键值对

根据键值取值

获取键值对数目

5.    实现。使用二叉排序树做为存储结构

//Hash.h

#ifndef _HASH_H

#define _HASH_H

 

//使用二叉排序树做为数据存储结构

typedef void Hash;

typedef void HashKey;

typedef void HashValue;

 

typedef int (Hash_Compare)(HashKey*,HashKey*);

 

Hash* Hash_Create();

void Hash_Destroy(Hash* hash);

void Hash_Clear(Hash* hash);

int Hash_Add(Hash* hash, HashKey* key, HashValue* value,Hash_Compare* compare);

HashValue* Hash_Remove (Hash* hash, HashKey* key,Hash_Compare* compare);

HashValue* Hash_Get(Hash* hash, HashKey* key,Hash_Compare* compare);

int Hash_Count(Hash* hash);

 

#endif

//Hash.c

#include

#include

#include "Hash.h"

#include "BSTree.h"

 

typedef struct _tag_HashNode HashNode;

struct _tag_HashNode

{

      BSTreeNode header;

      HashValue* value;

};

 

void recursive_clear(BSTreeNode* node)

{

      if(node != NULL){

           recursive_clear(node->left);

           recursive_clear(node->right);

           free(node);

      }

}

Hash* Hash_Create()

{

      return BSTree_Create();

}

void Hash_Destroy(Hash* hash)

{

      Hash_Clear(hash);

      BSTree_Destroy(hash);

}

void Hash_Clear(Hash* hash)

{

      recursive_clear(BSTree_Root(hash));

      BSTree_Clear(hash);

}

int Hash_Add(Hash* hash, HashKey* key, HashValue* value,Hash_Compare* compare)

{

      int ret = 0;

      HashNode* node = (HashNode*)malloc(sizeof(HashNode));

     

      if(ret = (node != NULL)){

           node->header.key = key;

           node->value = value;

          

           ret = BSTree_Insert(hash,(BSTreeNode*)node,compare);

           if(!ret){

                 free(node);

           }

      }

      return ret;

}

HashValue* Hash_Remove (Hash* hash, HashKey* key,Hash_Compare* compare)

{

      HashValue* ret = NULL;

      HashNode* node = (HashNode*)BSTree_Delete(hash,key,compare);

      if(node != NULL){

           ret = node->value;

           free(node);

      }

      return ret;

}

HashValue* Hash_Get(Hash* hash, HashKey* key,Hash_Compare* compare)

{

      HashValue* ret = NULL;

      HashNode* node = (HashNode*)BSTree_Get(hash,key,compare);

      if(node != NULL){

           ret = node->value;

      }

      return ret;

}

int Hash_Count(Hash* hash)

{

      return BSTree_Count(hash);

}

//使用

#include

#include

#include

#include "Hash.h"

#include "BSTree.h"

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

struct Student

{

      char* id;

      char* name;

      int age;

};

int compare_id(HashKey* k1,HashKey* k2)

{

      return strcmp((char*)k1,(char*)k2);

}

int main(int argc, char *argv[])

{

      Hash* hash = Hash_Create();

      struct Student s1 = {"9001201","Delphi",30};

      struct Student s2 = {"0xABCED","JAVA",20};  

      struct Student s3 = {"koaba","C++",40};

      struct Student s4 = {"!@#","C#",10};     

      struct Student s5 = {"Python","Python",15};  

      struct Student* ps = NULL;

      Hash_Add(hash,s1.id,&s1,compare_id);

      Hash_Add(hash,s2.id,&s2,compare_id);

      Hash_Add(hash,s3.id,&s3,compare_id);

      Hash_Add(hash,s4.id,&s4,compare_id);

      Hash_Add(hash,s5.id,&s5,compare_id);

     

      ps = Hash_Get(hash,"koaba",compare_id);

     

      printf("ID: %s\n",ps->id);

      printf("Name: %s\n",ps->name);

      printf("Age: %d\n",ps->age);

      Hash_Destroy(hash);

      return 0;

}

6.    总结

哈希技术是大型程序设计中的常用技术。

哈希技术提供键值对的直接存取。

哈希技术实现的关键是

数据存储结构的设计

哈希函数的设计

哈希技术在程序设计中表现为一种数据结构。