数据结构-哈希表

1 基本原理

我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数(哈希函数),使得每个元素的关键字都与一个函数值(即数组下标)相对应,于是用这个数组单元来存储这个元素;也可以简单的理解为,按照关键字为每一个元素”分类”,然后将这个元素存储在相应”类”所对应的地方。

但是,不能够保证每个元素的关键字与函数值是一一对应的,因此极有可能出现对于不同的元素,却计算出了相同的函数值,这样就产生了”冲突”,换句话说,就是把不同的元素分在了相同的”类”之中。后面我们将看到一种解决”冲突”的简便做法。

总的来说,”直接定址”与”解决冲突”是哈希表的两大特点。

2 函数构造

构造函数的常用方法(下面为了叙述简洁,设 h(k) 表示关键字为 k 的元素所对应的函数值):

a) 除余法:

选择一个适当的正整数 p ,令 h(k ) = k mod p
这里, p 如果选取的是比较大的素数,效果比较好。而且此法非常容易实现,因此是最常用的方法。

b) 数字选择法:

如果关键字的位数比较多,超过长整型范围而无法直接运算,可以选择其中数字分布比较均匀的若干位,所组成的新的值作为关键字或者直接作为函数值。

3 冲突处理

闭散列(线性探测法)

当发生哈希冲突时,如果哈希表还没有被装满,说明哈希表中必然还有空位置。那么可以把key存放到在列表中“下一个”位置去。

开散列(哈希桶)
首先对 集合用散列函数计算散列地址,具有相同地址关键码归于同一集合,每个集合称为一个桶,各个桶中的元素连接起来,各链表节点存储在哈希表中。

下面用线性探测法实现哈希表。

这里写图片描述
harh.h文件



#pragma once
#include <stddef.h>
//////////////////////////////////////////////
//此处hash表的期望存储的数据是键值对这样的结构
/////////////////////////////////////////////
#define HashMaxSize 1024
typedef int KeyType;
typedef int ValType;
typedef enum
{
      Empty,//无效状态
      Vaild,//有效状态
      Delete;//删除标志
}Stat;
//把KeyType转换成数组下标的哈希函数
typedef int (*HashFunc)(KeyType key);


//这个结构体表示哈希表中一个元素
//这个元素中同时包含了键值对
typedef struct HashElem
{
      KeyType key;
      ValType value;
      Stat stat;
}HashElem;
//定义一个哈希表
//[0,size)  这个区间就不能表示哈希表中有效元素的区间了
typedef struct HashTable
{

    HashElem data[HashMaxSize];
    size_t size;
    HashFunc func;//这是一个函数指针,指向hash函数

}HashTable;
void HashInit(HashTable* ht,HashFunc hash_func);

void HashDestory(HashTable* ht);

void HashInsert(HashTable* ht,KeyType key,ValType value);

int HashFind(HashTable* ht,KeyType Key,ValType* value);

void HashRemove(HashTable* ht,KeyType Key);



#include "hash.h"

int HashFuncDefault(KeyType key)
{
      return key % HashMaxSize;
}
void HashInit(HashTable* ht,HashFunc hash_func)
{
      ht->size=0;
      ht->func=hash_func;
      size_t i=0;
      for(  ;i<HashMaxSize;++i)
      {
            ht->data[i].stat=Empty;
      }
      return ;
}
void HashDestory(HashTable* ht)
{
      ht->size=0;
      ht->func=NULL;
      size_t i=0;
      for(  ;i<HashMaxSize;++i)
      {
            ht->data[i].stat=Empty;
      }
      return ;
}
void HashInsert(HashTable* ht,KeyType key,ValType value)
{
    //非法输入
    if(ht==NULL)
    {
          return ;
    }
    //1.判定hash是否可以继续插入
    //(通过负载因子来判定如果负载因子达到限制就不能再插入,此时负载因子设置0.8)  
    //负载因子越小,插入效率越高,空间浪费越多
    if(ht->size>=0.8*HashMaxSize)
    {
          //发现此时hash已经达到负载因子的上限,插入失败
          return;
    }
    //根据key值求得offect,由offect开始往后找到合适位置开始插入
    size_t offset=ht->func(key);
    while(1)
    {
          if(ht->data[offset].stat!=Empty)
          {
                //此时找到一个合适的位置可以插入
                ht->data[offset].stat=Vaild;
                ht->data[offset].key=key;
                ht->data[offset].value=value;
                ++ht->size;
                return ;
          }


          else if(ht->data[offset].stat==Vaild
                  && ht->data[offset].key==key)
          {
                //hash表中已经找到一个key相同的元素
                //此时认为插入失败。直接返回
                //如果需要修改value的值,就放开下面的代码
                //ht->data[offset].value=value;
                return ;
          }
          //此时key相同,但是value值不同的元素,则继续向下探测,找到
          //下一个empty的位置
          else
          {
                ++offset;
                if(offset>=HashMaxSize)
                {
                      offset=0;
                }
          }
    }



}
int HashFind(HashTable* ht,KeyType key,ValType *value)
{
    if(ht==NULL||value==NULL)
    {
          return ;
    }
    if(ht->size==0)
    {
          return ;
    }
     //从offset开始,一次判定当前元素的key和要查找元素的key是否相同
    size_t offset=ht->func(key);
    while( 1)
    {
        //如果找到key相同的元素,直接把value返回就行,并且认为查找成功
        if(ht->data[offset].key==key&&ht->data[offset].stat==Valid)
        {
              *value=ht->data[offset].value;
              return 1;
        }
        //如果发现当前元素是一个空元素,则认为查找失败
        else if(  ht->data[offset].stat==Empty)
        {
              return 0;
        }
        //剩下的情况就是继续向后查找
        else
        {
              ++offset;
              offset=offset>HashMaxSize?0:offset;
        }

    }


}
void HashRemove(HashTable* ht,KeyType key)
{
     if(  ht==NULL)
     {
           return ;
     }
     if(  ht->size==0)
     {
           return ;
     }
     size_t offset=ht->func(key);
     //从offset开始,一次判定当前元素的key和要删除元素的key是否相同
     while(1)
     {
         //如果当前key就是要删除的key,删除当前元素即可,删除一个元素引入新的状态
         if(ht->data[offset].key==key&&ht->data[offset].stat==valid)
         {
               ht->data[offset].stat=Delete;
               --ht->size;
               return ;

         }
         //如果当前元素为 空,则删除失败
         else if(ht->data[offset].stat==Empty)
         {
               return ;
         }
         //剩下的情况就++offset,线性探测删除的目标元素
         else
         {
               ++offset;
               offset=offset>HashMaxSize?0:offset;
         }


     }
}

“`
这里写图片描述

版权声明:本文为zgege原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/zgege/article/details/80503513

智能推荐

java乐观锁和悲观锁最底层的实现

1. CAS实现的乐观锁 CAS(Compare And Swap 比较并且替换)是乐观锁的一种实现方式,是一种轻量级锁,JUC 中很多工具类的实现就是基于 CAS 的,也可以理解为自旋锁 JUC是指import java.util.concurrent下面的包, 比如:import java.util.concurrent.atomic.AtomicInteger; 最终实现是汇编指令:lock...

Python 中各种imread函数的区别与联系

  原博客:https://blog.csdn.net/renelian1572/article/details/78761278 最近一直在用python做图像处理相关的东西,被各种imread函数搞得很头疼,因此今天决定将这些imread总结一下,以免以后因此犯些愚蠢的错误。如果你正好也对此感到困惑可以看下这篇总结。当然,要了解具体的细节,还是应该 read the fuc...

用栈判断一个字符串是否平衡

注: (1)本文定义:左符号:‘(’、‘[’、‘{’…… 右符号:‘)’、‘]’、‘}’……. (2)所谓的字符串的符号平衡,是指字符串中的左符号与右符号对应且相等,如字符串中的如‘(&r...

JAVA环境变量配置

位置 计算机->属性->高级系统设置->环境变量 方式一 用户变量新建path 系统变量新建classpath 方式二 系统变量 新建JAVA_HOME,值为JDK路径 编辑path,前加 方式三 用户变量新建JAVA_HOME 此路径含lib、bin、jre等文件夹。后运行tomcat,eclipse等需此变量,故最好设。 用户变量编辑Path,前加 系统可在任何路径识别jav...

常用的伪类选择器

CSS选择器众多 CSS选择器及权重计算 最常用的莫过于类选择器,其它的相对用的就不会那么多了,当然属性选择器和为类选择器用的也会比较多,这里我们就常用的伪类选择器来讲一讲。 什么是伪类选择器? CSS伪类是用来添加一些选择器的特殊效果。 常用的为类选择器 状态伪类 我们中最常见的为类选择器就是a标签(链接)上的为类选择器。 当我们使用它们的时候,需要遵循一定的顺序问题,否则将可能出现bug 注意...

猜你喜欢

ButterKnife的使用介绍及原理探究(六)

前面分析了ButterKnife的源码,了解其实现原理,那么就将原理运用于实践吧。 github地址:       点击打开链接 一、自定义注解 这里为了便于理解,只提供BindView注解。 二、添加注解处理器 添加ViewInjectProcessor注解处理器,看代码, 这里分别实现了init、getSupportedAnnotationTypes、g...

1.写一个程序,提示输入两个字符串,然后进行比较,输出较小的字符串。考试复习题库1|要求:只能使用单字符比较操作。

1.写一个程序,提示输入两个字符串,然后进行比较,输出较小的字符串。 要求只能使用单字符比较操作。 参考代码: 实验结果截图:...

小demo:slideDown()实现二级菜单栏下拉效果

效果如下,鼠标经过显示隐藏的二级菜单栏 但是这样的时候会存在一个问题,就是鼠标快速不停移入移出会导致二级菜单栏闪屏现象,一般需要使用stop()来清除事件  ...

基于docker环境的mysql主从复制

1、安装docker 可以参考之前的博客,之前写过了~ 2、拉取mysql镜像 3、创建mysql01和mysql02实例 主: 从: 4、进入容器修改配置 1)修改主数据库配置 进入主数据库容器 切换到 etc/mysql/目录下 查看可以看到my.cnf文件,使用vim编辑器打开,但是需要提前安装 安装vim命令: 安装成功后,修改my.cnf文件 新增配置后的my.cnf: binlog 日...

机器学习算法之决策树

原文:http://www.jianshu.com/p/6eecdeee5012 决策树是一种简单高效并且具有强解释性的模型,广泛应用于数据分析领域。其本质是一颗由多个判断节点组成的树,如: 决策树 在使用模型进行预测时,根据输入参数依次在各个判断节点进行判断游走,最后到叶子节点即为预测结果。 如何构造决策树 决策树算法的核心是通过对数据的学习,选定判断节点,构造一颗合适的决策树。 假设我们从用户...