数据结构_哈希

哈希

关键:不比较关键码,直接搜索得到需要的数。
特点:与搜索树不一样,哈希结构元素的储存位置与关键码直接对应,可以不用进行比较遍历。
哈希001
如图,创建一个数组,把a[4]中的数据按特定的规则保存到相应的位置,比如a[i]%n,到时候搜索数据的时候可以按照同样的规律直接找到这个位置,如果这个位置有数,则存在。

哈希冲突

比如按照特定方式处理数据,不同数据处理得到的结果可能相同,这样就都指向同一个储存位置。
闭散列解决
存储时,如果该位置有数据,则往下一个位置保存,如果后面还有冲突,则一直往后面找,直到找到空处,保存下来。读取时,如果处理得到的位置有数据,但是不是想要的数,则一直往后面找,直到找到为止,如果遇到了空处还没找到,则没有保存过该数。
具体代码接口实现

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>


typedef int KeyType;
typedef int ValueType;


enum Status
{
    EMPTY,    //空 
    EXITS,    //存在
    DELETE,   //被删除
};

typedef struct HashNode
{
    KeyType _key;
    ValueType _value;
    enum Status _status;
}HashNode;

typedef struct HashTable
{
    HashNode* table;
    size_t _size;
    size_t N;
}HashTable;

size_t HashFunc(KeyType key, size_t N)    //算位置
{
    return key%N;
}

void HashTableInit(HashTable* ht)   //初始化
{
    assert(ht);

    ht->table = NULL;
    ht->_size = 0;
    ht->N = 0;
}

int HashTableInsert(HashTable* ht, KeyType key, ValueType value)    //插入
{
    assert(ht);

    size_t N = 53;
    size_t i = 1;
    int index = 0;
    int tail = 0;

    const int _PrimeSize = 28;

    static const unsigned long _PrimeList[28] =
    { 53ul, 97ul, 193ul, 389ul, 769ul, 1543ul, 3079ul, 6151ul,
    12289ul, 24593ul, 49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
    1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, 50331653ul, 100663319ul,
    201326611ul, 402653189ul, 805306457ul, 1610612741ul, 3221225473ul, 4294967291ul
    };


    if (ht->table == NULL)
    {
        ht->table = (HashNode*)malloc(sizeof(HashNode)*N);
        assert(ht->table);
        memset(ht->table, 0, N);
        index = HashFunc(key, N);
        ht->table[index]._key = key;
        ht->table[index]._value = value;
        ht->table[index]._status = EXITS;
        ht->_size = 1;
        ht->N = N;

        return 0;
    }

    tail = ((ht->_size) * 10 )/ (ht->N);
    if (tail >= 7)
    {
        while (tail >= 7 && i < _PrimeSize)
        {
            i = 1;
            N = _PrimeList[i];
            i++;
            tail = (ht->_size) * 10 % N;
        }
        HashNode* NewTable = (HashNode*)malloc(sizeof(HashNode)*N);
        assert(NewTable);
        memset(NewTable, 0, N);

        for (i = 0; i < ht->N; i++)
        {
            if (ht->table[i]._status != EMPTY)   //需复制位置不为空
            {
                index = HashFunc(ht->table[i]._key, N);
                while (NewTable[index]._status != EMPTY)  //复制到的位置不为空
                {
                    index++;
                    if (index == N)
                        index = 0;
                }
                NewTable[index]._key = ht->table[i]._key;
                NewTable[index]._value = ht->table[i]._value;
                NewTable[index]._status = ht->table[i]._status;
            }
        }
        free(ht->table);
        ht->table = NewTable;
        ht->N = N;
    }

    index = HashFunc(key, ht->N);
    while (ht->table[index]._status == EXITS)
    {
        if (ht->table[index]._key == key)
            return -1;
        index++;
        if (index == N)
            index = 0;
    }
    ht->table[index]._key = key;
    ht->table[index]._value = value;
    ht->table[index]._status = EXITS;
    ht->_size++;

    return 0;
}

HashNode* HashTableFind(HashTable* ht, KeyType key)   //寻找
{
    assert(ht);

    int index = HashFunc(key, ht->N);
    while (ht->table[index]._status != EMPTY)  //不为空
    {
        if (ht->table[index]._key == key)
            return &(ht->table[index]);
        index++;
    }
    return NULL;
}

int HashTableRemove(HashTable* ht, KeyType key)
{
    assert(ht);

    HashNode* node = HashTableFind(ht, key);
    if (node != NULL)
    {
        node->_status = DELETE;
        ht->_size--;
        return 0;
    }
    else
        return -1;
}

//static size_t BKDRHash(const char* str);


void HashTableDestory(HashTable* ht)
{
    assert(ht);

    free(ht->table);
    ht->table = NULL;
    ht->_size = 0;
    ht->N = 0;
}

void HashTablePrintf(HashTable* ht)
{
    assert(ht);

    for (size_t i = 0; i < ht->N; i++)
    {
        if (ht->table[i]._status == EXITS)  //存在
        {
            printf("[%d]%d ",i, ht->table[i]._key);
        }
    }
    printf("\n");
}

开散列解决
给一个指针数组开拓一块空间,每个元素是一个指向结点的指针,每个结点都可以保存数据,有哈希冲突的数据直接挂在这个结点的下面,就像单链表一样。这样比闭散列更节约空间。
哈希002

具体代码接口实现

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

typedef int KeyType;
typedef int ValueType;

typedef struct HashNode
{
    KeyType _key;
    ValueType _value;
    struct HashNode* _next;
}HashNode;

typedef struct HashTable
{
    //HashNode** _tables; 
    HashNode** _tables;
    size_t _size;
    size_t _N;
}HashTable;

HashNode* BuyHashNode(KeyType key, ValueType value)   //创建结点
{
    HashNode* cur = (HashNode*)malloc(sizeof(HashNode));
    cur->_key = key;
    cur->_value = value;
    cur->_next = NULL;

    return cur;
}

size_t HashFunc(KeyType key, size_t N)    //计算位置
{
    return key%N;
}

size_t GetNextPrimeNum(size_t cur);


void HashTableInit(HashTable* ht)
{
    assert(ht);

    ht->_N = 0;
    ht->_size = 0;
    ht->_tables = NULL;
}

int HashTableInsert(HashTable* ht, KeyType key, ValueType value)
{
    assert(ht);

    int tail = 0;
    size_t index = 0;
    size_t i = 0;
    size_t N = 0;
    HashNode** table = ht->_tables;

    const int _PrimeSize = 28;
    static const unsigned long _PrimeList[28] =
    { 53ul, 97ul, 193ul, 389ul, 769ul, 1543ul, 3079ul, 6151ul,
    12289ul, 24593ul, 49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
    1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, 50331653ul, 100663319ul,
    201326611ul, 402653189ul, 805306457ul, 1610612741ul, 3221225473ul, 4294967291ul
    };


    if (table == NULL)
    {
        i = 0;
        ht->_tables = (HashNode**)malloc(sizeof(HashNode*)*_PrimeList[i]);
        assert(ht->_tables);
        ht->_N = _PrimeList[i];
        for (i = 0; i < ht->_N; i++)
        {
            ht->_tables[i] = NULL;
        }
        index = HashFunc(key, ht->_N);
        ht->_tables[index] = BuyHashNode(key, value);
        return 0;
    }
    tail = (ht->_size+1)/ (ht->_N);
    if (tail == 1)                 //判满扩容
    {
        i = 0;
        while (tail >= 1)
        {
            i++;
            N = _PrimeList[i];
            tail = (ht->_size + 1) / N;
        }
        HashNode** NewTable = (HashNode**)malloc(sizeof(HashNode*)*N);
        for (i = 0; i < N; i++)
        {
            NewTable[i] = NULL;
        }
        assert(NewTable);

        for (i = 0; i < ht->_N; i++)   //把旧表的数据复制到新表
        {
            while (table[i] != NULL)    //判断表的每个位置是否有数据,有就复制
            {
                HashNode* cur = table[i];
                HashNode* next = cur->_next;
                cur->_next = NULL;
                table[i] = next;

                index = HashFunc(cur->_key, N);
                next = NewTable[index];
                if (next != NULL)
                {
                    while (next->_next != NULL)
                    {
                        next = next->_next;
                    }
                    next->_next = cur;
                }
                else
                    NewTable[index] = cur;
            }
        }   //for循环终止
        free(table);
        table = NULL;
        ht->_tables = NewTable;
        ht->_N = N;
    }       //扩容结束

    index = HashFunc(key, ht->_N);    //开始插入
    if (ht->_tables[index] != NULL)
    {
        HashNode* cur = ht->_tables[index];
        if (cur->_key == key)
            return -1;
        while (cur->_next != NULL)
        {
            cur = cur->_next;
            if (cur->_key == key)
                return -1;
        }
        cur->_next = BuyHashNode(key, value);
    }
    else
        ht->_tables[index] = BuyHashNode(key, value);

    return 0;

}



HashNode* HashTableFind(HashTable* ht, KeyType key)
{
    assert(ht);
    int index = 0;
    HashNode* cur = NULL;
    if (ht->_tables == NULL)
        return NULL;
    index = HashFunc(key, ht->_N);
    cur = ht->_tables[index];
    while (cur != NULL)
    {
        if (cur->_key == key)
            return cur;
        cur = cur->_next;
    }
    return NULL;
}

int HashTableRemove(HashTable* ht, KeyType key)
{
    assert(ht);

    HashNode* cur = HashTableFind(ht, key);
    HashNode* next = NULL;
    if (cur == NULL)
        return -1;

    next = cur->_next;
    if (next != NULL)
    {
        cur->_key = next->_key;
        cur->_value = next->_value;
        cur->_next = next->_next;
    }
    else
    {
        int index = HashFunc(key,ht->_N);
        HashNode* parent = ht->_tables[index];
        if (parent == cur)
        {
            ht->_tables[index] = NULL;
        }

        else
        {
            while (parent->_next != cur)
            {
                parent = parent->_next;
            }
            parent->_next = NULL;
        }
        free(cur);
    }
    return 0;
}

void HashTableDestory(HashTable* ht)
{
    assert(ht);

    HashNode* cur = NULL;
    size_t i = 0;
    if (ht->_size == 0)
        return;
    for (i; i < ht->_N; i++)
    {
        cur = ht->_tables[i];
        if (cur != NULL)
        {
            while (cur == NULL)
            {
                HashNode* next = cur->_next;
                free(cur);
                cur = next;
            }
        }
    }
    free(ht->_tables);
    ht->_tables = NULL;
    ht->_N = 0;
    ht->_size = 0;
}

void HashPrint(HashTable* ht)
{
    assert(ht);

    size_t i = 0;
    HashNode* cur = NULL;
    if (ht->_tables == NULL)
        return;
    for (i = 0; i < ht->_N; i++)
    {
        if (ht->_tables[i] != NULL)
        {
            int j = 0;
            cur = ht->_tables[i];
            while (cur != NULL)
            {
                printf("[%d][%d]%d ", i, j, cur->_key);
                cur = cur->_next;
            }
        }
    }
    printf("\n");
}
版权声明:本文为cute_shuai原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/cute_shuai/article/details/79425274

智能推荐

使用欧几里得算法解决问题——求字符串的最大公因子(力扣第1071题)(JavaScript解法)

1、欧几里得算法的思想 基于辗转相除法的原理,具体做法:用较大数除以较小数,再用出现的余数(第一个余数)去除除数,,再用出现的余数(第二个余数)去除第一个余数,如此仿佛,直到最后一个余数为0 2、算法流程 3、JavaScript实现欧几里得算法 4、使用欧几里得算法解决问题 力扣1071字符串的最大公因子 题目描述: 对于字符串 S 和 T,只有在 S = T + … + T(T ...

spring与redis整合和序列化问题

spring与redis整合 首先用docker下载redis 下载:docker pull redis 运行:docker run -d -p 6379:6379 --name myredis docker.io/redis 连接redis Desktop Manager 然后开始在springboot上开始配置 application.yml: 自动配置好StringRedisTemplate...

CentOS 7配置南大docker镜像

文章目录 CentOS 7配置南大docker镜像 0.帮助页面 1.系统要求 2.卸载旧版本(没有旧版本可跳过) 3.安装方式 4.准备工作 5.可选操作 Stable Test Nightly 6.安装docker引擎 7. (可选)修改配置文件防止与xshell连接冲突 8.启动docker CentOS 7配置南大docker镜像 0.帮助页面 南大docker源:https://mirr...

Qcon演讲纪实:详解如何在实时视频通话中实现AR功能

2018年4月20日-22日,由 infoQ 主办的 Qcon 2018全球软件开发大会在北京如期举行。声网首席 iOS 研发工程师,iOS 端移动应用产品设计和技术架构负责人龚宇华,受邀分享了《基于 ARkit 和 ARcore,在实时视频通话中实现 AR 功能》,在演讲中剖析了 AR 与 VR 差异,ARKit 的工作原理,以及逐步讲解如何基于 ARKit 与声网Agora SDK 创建 AR...

POJ2348 UVa10368 HDU1525 Euclid's Game【博弈】

Euclid's GameTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4106    Accepted Submission(s): 1947 Probl...

猜你喜欢

使用Breeze.js编写更好的查询

这篇文章是由同行评审Agbonghama柯林斯 。 感谢所有SitePoint的审稿作出SitePoint内容也可以是最好的! 数据量正在迅速发展,他们正在变得越来越复杂,维护。 许多开发人员希望避免由数据问题他们的工作过程中造成的问题和头痛。 一个使我们的工作更轻松的图书馆是Breeze.js 。 在这篇文章中,我们将讨论我们如何能够写出更好的查询与Breeze.js。 但是首先,我们应该知道什...

Netty框架构建Nio编程

~~~ 随手点赞,养成习惯 ~~~ 为什么选择Netty框架 Netty是业界最流行的NIO框架之一,它的健壮性、功能、性能、可定制性和可扩展性在同类框架中都是首屈一指的。 优点: ① API使用简单,开发门槛低 ②功能强大,预置了多种编解码功能,支持多种主流协议 ③ 定制能力强,可以通过ChannelHandler对通信框架进行灵活地扩展; ④性能高,通过与其他业界主流的NIO框架对比,Nett...

【JZOJ5262】【GDOI2018模拟8.12】树(DP,性质题)

Description Solution 首先我们可以知道两个性质:1、路径u-v和路径v-w可以合并为路径u-w;2、路径u1-v1加路径u2-v2和路径u1-v2加路径u2-v1是等价的(就是起始点和终点可以互换) 那么知道这些性质之后就很好做了。我们只用知道每个点多少次做起点和多少次做终点。 我们设f[i]表示满足i子树的需求i上的值要是多少。 那么枚举i的所有儿子,判断a[i]-f[i],...

【String-easy】541. Reverse String II 反转的元素,有反转个数和间隔

1. 题目原址 https://leetcode.com/problems/reverse-string-ii/ 2. 题目描述 3. 题目大意 给定一个字符串,和字符串的间隔k, 这个k表示每k个数反转一次,然后再间隔k个元素再反转k个元素。 4. 解题思路 只要按照间隔去反转就可以了。然后间隔k个元素不反转是通过让i每次递增 2*k完成的。 5. AC代码 6. 相似题型 【1】344. Re...

【C语言笔记结构体】

我们都知道C语言中变量的类型决定了变量存储占用的空间。当我们要使用一个变量保存年龄时可以将其声明为int类型,当我们要使用一个变量保存某一科目的考试成绩时可以将其声明为float。 那么,当我们要做一个学生信息管理系统时,需要保存学生的姓名、学号、年龄等信息,该怎么做呢? 如当要保存三个学生的信息时, 方法一是: 方法二是: 显然,方法二跟更清晰,因为它把name、num、age都集成在一个模板,...