数据--第52课 - 哈希表及其实现

第52课 - 哈希表及其实现

1. 哈希的定义

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

 

2. 哈希表

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

 

3. 哈希函数

哈希技术中的映射关系f。

 

4. 关键特点

哈希表:

• 哈希技术需要具体的数据结构为基础 – 如数组,链表 ,链表

哈希函数

• 哈希技术需要映射关键字和数据元素的存储位置 –依赖于数学运算,如四则运算,逻辑元素 ,逻辑元素,比较…

 

5. 基本操作

创建哈希

销毁哈希

清空哈希

加入键值对

删除键值对

根据键获取值

获取键值对数目

 

6. 操作的实现

哈希在程序中表现为一种特殊的数据类型。

哈希的操作在程序中的表现为一组函数。

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);

 

7. 程序

main.c

#include <stdio.h>

#include <stdlib.h>

#include "Hash.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 = {"0xABCDE", "Java", 20};

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

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

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

    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, "koabc", 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;

}

BSTree.h

BSTree.c

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 <stdio.h>

#include <malloc.h>

#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);

}

 

小结:

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

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

哈希技术实现的关键是:数据存储结构的设计,哈希函数的设计。

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

上一篇:“12306” 是如何支撑百万 QPS 的?


下一篇:虽然难用,但12306面临的业务场景复杂度可能是世界之最