哈希表

概念

哈希表-散列表，它是基于快速存储的角度设计的，也是一种典型的“空间换时间”的做法。

(键值(编号)就代表了这个数据。)

在这里插入图片描述

链式存储实现

#include<iostream>
using namespace std;

#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* ThisList;
}HashTable;

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

//初始化哈希表
HashTable* initHash(int TableSize)
{

    HashTable* hTable = NULL;
    if (TableSize <= 0)
    {
        TableSize = DEFAULT_SIZE;
    }
    hTable = new HashTable;
    hTable->TableSize = TableSize;
    hTable->ThisList = new List[TableSize];//哈希桶    
    if (!hTable->ThisList)    
    {
        return NULL;
    }
    
    //为Hash桶的对应指针数组初始化链表结点    
    for (int i = 0; i < TableSize; i++)
    {
        hTable->ThisList[i] = new ListNode;
        if (!hTable->ThisList[i])
        {
            return NULL;
        }
        else
        {
            memset(hTable->ThisList[i], 0, sizeof(ListNode));
        }
    }

    return hTable;
}

//哈希表中查找元素
Element findHash(HashTable* hashtable, int key)
{
    int i = 0;
    List L = NULL;
    Element e = NULL;
    i = Hash(key, hashtable->TableSize);
    L = hashtable->ThisList[i];
    e = L->next;
    while (e && e->key != key)
    {
        e = e->next;
    }
    return e;
}

//哈希表插入元素
void insertHash(HashTable* hashtable, int key, void* value)
{
    Element e = NULL, tmp = NULL;
    List L = NULL;
    e = findHash(hashtable, key);

    if (!e) 
    {
        tmp = new ListNode;
        if (!tmp)
        {
            return;
        }
        L = hashtable->ThisList[Hash(key, hashtable->TableSize)];//前插法 
        tmp->data = value;
        tmp->key = key;
        tmp->next = L->next;
        L->next = tmp;
    }
    else
    {
        cout << "这个键已经存在" << endl;
    }
}

//哈希表删除元素
void DeleteHash(HashTable* hashtable, int key)
{
    Element e = NULL, last = NULL;
    List L = NULL;
    int i = Hash(key, hashtable->TableSize);
    L = hashtable->ThisList[i];
    last = L;
    e = L->next;
    //key是所对应数据的数字代号，这个每个元素是不同的，i是对应数据所在的hash桶，也就是key % tablesize,多个元素可以是同一个
    while (e && e->key != key)
    {
        last = e;
        e = e->next;
    }
    if (e)
    {
        last->next = e->next;
        delete e;
    }
    else
    {
        cout << "该key不存在" << endl;
    }
}

//找到对应的ListNode提取元素
void* extract(Element e)
{
    return  e ? e->data : NULL;
}
int main(void)
{
      char *elems1 ="王小花";
      char *elems2 ="李小华";
      char *elems3 ="张富贵";


     HashTable* hashtable = NULL;
     hashtable = initHash(31);
     insertHash(hashtable, 1, elems1);
     insertHash(hashtable, 2, elems2);
     insertHash(hashtable, 3, elems3);
        

     //查找方式1
     Element findky = findHash(hashtable, 2);
     if (findky)
     {
         cout << (const char*)findky->data << endl;//强转
     }
     else
     {
         cout << "Not Find this Key!" << endl;
     }


    //查找方式2    
    Element e = findHash(hashtable, 1);
    if (e)
    {
        cout << (const char*)extract(e) << endl;
    }
    else
    {
        cout << "Not Find this Key!" << endl;
    }


    return 0;
}

顺序存储实现

#include<iostream>
using namespace     std;

#define Hash_Size 50
#define Hash_Bucket 128

typedef struct _HashMem//哈希表存储的数据类型
{
    int key;
    void* data;
}HashMember;

typedef struct _hash
{
    HashMember Hash_Table[Hash_Bucket][Hash_Size];
    int _HashSize;//哈希桶的索引
}Hash_Table;


//多个计数器不能指向同一个计数器变量，并且不能是局部变量，所以在这里创建一个全局的计数器变量数组
int CountArry[Hash_Bucket];


//初始化
bool initHashtable(Hash_Table*    hashtable)
{
    if (!hashtable)
    {
        return false;
    }

    hashtable->_HashSize = Hash_Bucket;//哈希桶
    
    if (!hashtable->Hash_Table)
    {
        return false;
    }
    
    //为每个哈希桶在第[0]位置添加一个记录当前桶中元素个数的计数器

    for (int i = 0; i < Hash_Bucket; i++)
    {
        HashMember Count;
        int* count = &(CountArry[i]);
        Count.data = count;
        Count.key = -(i + 1);
        hashtable->Hash_Table[i][0] = Count;
    }
    return true;
}

//计算要存储元素的哈希桶索引
int Hash(int key,int hash_bucket)
{
    return (key % Hash_Bucket);
}
//查找元素
bool findHashtable(Hash_Table* hashtable, int key)
{
    //先找到对应的哈希桶
    int index = Hash(key, Hash_Bucket);
    int count = *((int*)(hashtable->Hash_Table[index][0].data));//对应桶中的元素个数
    for (int i = 1; i < count + 1; i++)
    {
        if (hashtable->Hash_Table[index][i].key == key)
        {
            return true;
        }
    }
    return false;
}

//插入元素
void insertHashtable(Hash_Table* hashtable, int key, void* data)
{
    if (!hashtable)
    {
        return;
    }
 
    int index = Hash(key, hashtable->_HashSize);

    HashMember newHashMember;
    newHashMember.data = data;
    newHashMember.key = key;
    
    bool isExistence = findHashtable(hashtable,key);//先找一下，如果没有就往对应的哈希桶中塞。


    if (!isExistence)
    {
        //找到每个哈希桶的计数器，在当前计数器数量所指向的位置的下一个位置放入元素，然后自增计数器。
        hashtable->Hash_Table[index][*((int*)(hashtable->Hash_Table[index][0].data))+1] = newHashMember;
        (*((int*)(hashtable->Hash_Table[index][0].data)))++;
    }
    else
    {
        cout << "该key已经存在了" << endl;
    }
}

//删除元素
bool deleteHashtable(Hash_Table* hashtable,int key)
{
    if (!hashtable)
    {
        return false;
    }
    
    if (findHashtable(hashtable, key))//找到了才能删除
    {
        //找到了，去那拿对应的哈希桶
        int index = Hash(key, hashtable->_HashSize);
        //拿到桶中的元素个数    
        int count = *((int*)hashtable->Hash_Table[index][0].data);
        int i = 1;
        for (i; i < count + 1; i++)
        {
            if (hashtable->Hash_Table[index][i].key == key)
            {
                break;
            }
        }
        //此时的i的位置就是对应key的位置
        for (int j = i; j < count - 1; j++)
        {
            hashtable->Hash_Table[index][j] = hashtable->Hash_Table[index][j + 1];
        }
        //计数器--
        (*((int*)hashtable->Hash_Table[index][0].data))--;
        return true;
    }
    else
    {
        return false;
    }

}

//清理哈希表
bool cleanHashtable(Hash_Table* hashtable)
{
    if (!hashtable)
    {
        return false;
    }    
    //将每个哈希桶的计数器置为0 
    for (int i = 0; i < Hash_Bucket; i++)
    {
        *((int*)hashtable->Hash_Table[i][0].data) = 0;
    }

    return true;
}

int main(void)
{
    Hash_Table* hashtable = new Hash_Table;
    //初始化
    initHashtable(hashtable);
    char elem1[] = "李小花";
    char elem2[] = "赵铁柱";
    char elem3[] = "张全蛋";
    char elem4[] = "新二";
    char elem5[] = "小明";
    //插入
    insertHashtable(hashtable, 1,elem1);
    insertHashtable(hashtable, 2,elem2);
    insertHashtable(hashtable, 3,elem3);
    insertHashtable(hashtable, 4,elem4);
    insertHashtable(hashtable, 5,elem5);    
    //删除
    bool ret1 = deleteHashtable(hashtable, 1);
    //查找
    bool ret = findHashtable(hashtable, 1);
    if (ret)
    {
        cout << "存在" << endl;
    }
    else
    {
        cout << "不存在" << endl;
    }
    
    //清理
    cleanHashtable(hashtable);
    //销毁
    delete hashtable;
    hashtable = NULL;

    return 0;
}

实际应用

字串匹配

给定几个字符串，判断一个字符串从第2位到第4位的的字符是否在这几个字符串中。
重点在于，这个哈希表的key和对应的value是同一个。

key是由value转化过去的。

hash_table.h

#include<iostream>
using namespace std;

#define BUCKET_SIZE 1024
#define compare(a,b) strcmp((const char*)a,(const char*) b)

#define hash_func SDBMHash


typedef struct    _ListNode
{
    struct _ListNode* next;
    void* key;
    void* data;
}ListNode;

//提高可读性和可维护性
typedef ListNode* List;
typedef ListNode* Element;


typedef struct _HashTable
{
    int TableSize;//哈希桶的大小
    List* ThisList;
}HashTable;



//把字符串对应内容转化为整数类型的key(不改变原来内容)
unsigned int SDBMHash(void* key)
{
    unsigned int hash = 0;
    char* str = (char*)key;
    while (*str)
    {
        hash = (*str++) + (hash << 6) + (hash << 16) - hash;//让映射到的整数尽可能均匀，不出现重叠。

    }
    return (hash & 0x7FFFFFFF);
}


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



//初始化哈希表
HashTable* initHash(int TableSize)
{

    HashTable* hTable = NULL;
    if (TableSize <= 0)
    {
        TableSize = BUCKET_SIZE;
    }
    hTable = new HashTable;
    hTable->TableSize = TableSize;
    hTable->ThisList = new List[TableSize];//哈希桶    
    if (!hTable->ThisList)
    {
        return NULL;
    }

    //为Hash桶的对应指针数组初始化链表结点    
    for (int i = 0; i < TableSize; i++)
    {
        hTable->ThisList[i] = new ListNode;
        if (!hTable->ThisList[i])
        {
            return NULL;
        }
        else
        {
            memset(hTable->ThisList[i], 0, sizeof(ListNode));
        }
    }

    return hTable;
}

//哈希表中查找元素
Element findHash(HashTable* hashtable, void* key)
{
    int i = 0;
    List L = NULL;
    Element e = NULL;

    i = Hash(key, hashtable->TableSize);//将这个字符串类型的key转化为哈希桶索引，找到该元素要放置的桶


    L = hashtable->ThisList[i];//对应的哈希桶

    e = L->next;

    while (e && compare(e->key, key) != 0)
    {
        e = e->next;
    }
    return e;
}

/*
    不要被类型限制了，本质上和key是int类型的哈希表是一样的。
*/


//哈希表插入元素
void insertHash(HashTable* hashtable, void* key, void* value)
{
    Element e = NULL, tmp = NULL;
    List L = NULL;
    e = findHash(hashtable, key);

    if (!e)
    {
        tmp = new ListNode;
        if (!tmp)
        {
            return;
        }
        //L为其对应位置的哈希桶
        //将新插入的结点与桶链接起来
        L = hashtable->ThisList[Hash(key, hashtable->TableSize)];//前插法 
        tmp->data = value;
        tmp->key = key;
        tmp->next = L->next;
        L->next = tmp;
    }
    else
    {
        cout << "这个键已经存在" << endl;
    }
}

//哈希表删除元素
void DeleteHash(HashTable* hashtable, void* key)
{
    Element e = NULL, last = NULL;
    List L = NULL;
    int i = Hash(key, hashtable->TableSize);//找到对应的哈希桶,然后在对应的哈希桶里面一个一个地遍历
    L = hashtable->ThisList[i];
    last = L;
    e = L->next;
    //key是所对应数据的数字代号，这个每个元素是不同的，i是对应数据所在的hash桶，也就是key % tablesize,多个元素可以是同一个
    while (e && !compare(e->key, key))
    {
        last = e;
        e = e->next;
    }
    if (e)
    {
        last->next = e->next;
        delete e;
    }
    else
    {
        cout << "该key不存在" << endl;
    }
}

//找到对应的ListNode提取元素
void* extract(Element e)
{
    return  e ? e->data : NULL;
}

//销毁哈希表
void destoryHash(HashTable* hashtable)
{
    List L = NULL;
    Element cur = NULL, next = NULL;
    for (int i = 0; i < hashtable->TableSize; i++)
    {
        L = hashtable->ThisList[i];
        cur = L->next;
        while (cur)
        {
            next = cur->next;
            delete cur;
            cur = next;
        }

        delete(L);
    }
    delete (hashtable->ThisList);
    delete (hashtable);
}

test.cpp

#include<iostream>
#include"hash_table.h"
using namespace std;

int main(void)
{
    char elems1[] = "ADBB";
    char elems2[] = "BDDC";
    char elems3[] = "CDBC";
    char elems4[] = "BDBB";

    const char* tester = "ABDBBAC";
    char cur[5] = { '\0' };

    int i = 0;


    HashTable* hashtable = NULL;
    hashtable = initHash(BUCKET_SIZE);

    insertHash(hashtable, elems1, elems1);
    insertHash(hashtable, elems2, elems2);
    insertHash(hashtable, elems3, elems2);
    insertHash(hashtable, elems4, elems4);


    //将要进行检查的字符串的2-4个字符拿过来进行对比
    strncpy_s(cur, tester + 1, 4);

    Element e = findHash(hashtable, cur);
    if (e)
    {
        cout << "找到了" << endl;
    }
    else
    {
        cout << "没找到" << endl;
    }
    destoryHash(hashtable);
    return 0;
}

【数据结构】哈希表(C++)

哈希表

概念

链式存储实现

顺序存储实现

实际应用

字串匹配

hash_table.h

test.cpp

热门文章

最新文章

相关课程

相关电子书