当前位置： 首页 > news >正文

邯郸企业做网站报价/郑州网站seo服务

news 2025/8/3 10:30:08
邯郸企业做网站报价,郑州网站seo服务,wordpress加入地图,上海建设检测行业协会官网哈希概念 常规搜索：   数据杂乱无章——->顺序查找—–>时间复杂度0(n)。   数据有序—–>二分查找——>时间复杂度0(log(n))。   建立二叉搜索树—–>时间复杂度0(n)（单支树）。 理想的搜索方法是：可以…

哈希概念

常规搜索：
  数据杂乱无章——->顺序查找—–>时间复杂度0(n)。
  数据有序—–>二分查找——>时间复杂度0(log(n))。
  建立二叉搜索树—–>时间复杂度0(n)（单支树）。
理想的搜索方法是：可以不经过任何比较，一次直接从表中得到要搜索的元素，如果构造一种存储结构，通过某种函数使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么查找时通过该函数可以很快的找到该元素。
当该结构中：

  • 插入元素时：根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放。
  • 搜索元素时：对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若相等，则搜索成功。

该方法即为哈希（散列）方法，哈希方法中使用的转换函数称为哈希（散列）函数，构造出来的结构称为哈希表或者散列表。
这里写图片描述
用该方法进行搜索不必进行多次关键码的比较，因此搜索速度比较快。但是哈希函数中一般会选一个最接近m（空间大小）的质数作为除数。
问题：按照上述哈希方法，向集合中插入2，会出现什么问题？？

  对于两个数据元素的关键字M,N(M!=N),但有Hash(M)=Hash(N),即不同的关键字算出了相同的哈希地址，该现象称为哈希冲突或哈希碰撞，把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。
那么如何处理哈希冲突呢？？？？

发生哈希冲突的原因：
  1. 哈希函数设置不合理
   考虑重新设计哈希函数
    哈希函数设计原则：
      ①.哈希函数的定义域必须包含需要存储的全部关键码，如果散列表有m个地址，其值域必须在0~m-1之间。
      ②.哈希函数计算出来的地址能均匀的分布在整个空间中。
      ③.哈希函数应该比较简单。
具体解决方法：

  • 闭散列：开放定值法，当发生哈希冲突时，如果哈希表未被装满，说明哈希表必然还有空位置，那么就把关键字存放到表中“下一个”空位置去。
  • 开散列：链地址法（开链法）首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一个集合，每一个子集称为一个桶，各个桶中的元素通过一个单链表链接起来。

本篇我们主要讲解闭散列：

闭散列：
  当发生哈希冲突时，如果哈希表未被装满，说明哈希表必然还有空位置，那么就把关键字存放到表中“下一个”空位置去。
  那如何寻找下一个空余位置？

1. 线性探测
  从发生冲突的位置开始，依次继续向后探测，直到有空位置。
插入时：使用哈希函数找到待插入元素在哈希表中的位置，如果该位置没有元素则直接插入，如果该位置有元素但不是待插入元素则发生哈希冲突，使用线性探测找到下一个空位置，在找空位置的路上如果遇到元素与待插入元素相同则不插入（即哈希表中不允许有相同的元素），没有遇到等找到空位置就插入。
这里写图片描述
说明： 由于哈希表里不能有相同的元素，所以删除元素时就不能随便删除元素，若直接删除极易导致哈希表中元素重复。
这里写图片描述
优点： 简单
缺陷： 一旦发生哈希冲突，所有的冲突连在一起，容易产生数据堆积。
那如何缓解呢？？
负载因子：
  散列表的负载因子定义为：α=填入表中的元素个数 / 散列表的长度。α是散列表装满程度的标志因子，由于表长是定值，α与填入表中的元素个数成正比，所以，α越大，填入表中的元素就越多，产生冲突的可能性就越大；反之，α越小，标明填入表中的元素就越少，产生冲突的可能性就越小。一般应该严格控制在0.7~0.8之间。超过0.8，查表时的不命中率按照指数曲线上升。

  1. 二次探测
      发生哈希冲突时，二次探测寻找下一个空位置的公式为：H(i)=（H(0)+i^2）^2%m
    这里写图片描述
    优点：不存在数据堆积。
    缺点： 当元素较多时需要比较很多次。

代码实现：
.h文件

#include<assert.h>
#include<malloc.h>
#include<stdlib.h>
#include<math.h>
#include<assert.h>
#include<stdio.h>
//哈希表的状态
typedef enum state
{EMPTY, //空EXIST, //存在DELETE,//删除
}state;typedef int DataType;
typedef struct Elem
{DataType _data;enum state _state;
}Elem;typedef struct Size
{int size; //哈希表中有效元素个数int del;  //哈希表被删除元素的个数
}Size;
//哈希表
typedef struct HashTable
{Elem *data;int capacity;Size size;
}HashTable;//初始化哈希表
void InitHashTable(HashTable *hashtable);
//插入哈希表
void InsertHashTable(HashTable *hashtable, DataType data);
//删除哈希表
int  DeleteHashTable(HashTable *hashtable, DataType data);
//查找
int FindHashTable(HashTable *hashtable, DataType data);
//判空
int EmptyHashTable(HashTable *hashtable);
//哈希表元素个数
int SizeHashTable(HashTable *hashtable);
//打印哈希表
void print(HashTable *hashtable);
//销毁哈希表
void DestroyHashTable(HashTable *hashtable);

HashTable.c

#include"HashTable.h"//素数表
#define primesize 28
unsigned long int _PrimeList[primesize] = {53ul, 97ul, 193ul, 389ul, 769ul,1543ul, 3079ul, 6151ul, 12289ul, 24593ul,49157ul, 98317ul, 196613ul, 39324ul, 786433ul,1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,60331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,1610612741ul, 3221225473ul, 4294967291ul
};
//素数
int Prime(int capacity)
{int i = 0;for (i = 0; i < primesize; i++){if ((int)_PrimeList[i] >= capacity){return _PrimeList[i];}}return _PrimeList[primesize - 1];
}
//初始化哈希表
void InitHashTable(HashTable *hashtable)
{int i = 0;int capacity;assert(hashtable);//初始化容量capacity = 5;hashtable->capacity = Prime(capacity);//初始化datahashtable->data = (Elem*)malloc(hashtable->capacity*sizeof(Elem));if (hashtable->data == NULL){assert(0);return ;}//初始化数组for (i = 0; i < hashtable->capacity; i++){hashtable->data[i]._data = 0;hashtable->data[i]._state = EMPTY;}//初始化元素hashtable->size.size = 0;hashtable->size.del = 0;
}//哈希函数
int HashFun(HashTable* hashtable,DataType data)
{assert(hashtable);return data % hashtable->capacity;
}
//判断是否需要扩容
Elem * ExpandCapacity(HashTable *hashtable)
{int i = 0;int addr = 0;int newcapacity = 0;int oldcapacity = hashtable->capacity;Elem *new = NULL;//扩容量newcapacity = Prime(hashtable->capacity);//开辟新空间new= (Elem *)malloc(newcapacity*sizeof(Elem));if (new == NULL){assert(0);return NULL;}//初始化新空间for (i = 0; i < newcapacity; i++){new[i]._data = 0;new[i]._state = EMPTY;}hashtable->capacity = newcapacity;//搬元素for (i = 0; i < oldcapacity; i++){if (hashtable->data[i]._state == EXIST){//新哈希地址addr = HashFun(hashtable, hashtable->data[i]._data);//插入新表while (new[addr]._state != EMPTY){
#if 0//线性探测addr++;if (addr == hashtable->capacity){addr = 0;}
#else//二次探测//二次探测i++;addr = addr + 2 * i + 1;addr = addr%hashtable->capacity;}
#endifnew[addr]._data=hashtable->data[i]._data;new[addr]._state = EXIST;}}hashtable->size.del = 0;free(hashtable->data);hashtable->data = new;return new;
}
//插入哈希表
void InsertHashTable(HashTable *hashtable, DataType data)
{int i = 0;assert(hashtable);//判断是否扩容，如果表中的个数超过自己的哈希因子，则需要扩容if ((hashtable->size.del + hashtable->size.size) * 10 / hashtable->capacity >= 7){ExpandCapacity(hashtable);}int Add = 0;Add = HashFun(hashtable,data);while (hashtable->data[Add]._state!=EMPTY ){//如果有与data相同的结点则不插入if (hashtable->data[Add]._state == EXIST&&hashtable->data[Add]._data == data){return;}
#if 0//线性探测Add++;if (Add == hashtable->capacity){Add = 0;}
#else//二次探测i++;Add = Add + 2 * i + 1;Add = Add%hashtable->capacity;}
#endifhashtable->data[Add]._data = data;hashtable->data[Add]._state = EXIST;hashtable->size.size++;
}//删除哈希表
int  DeleteHashTable(HashTable *hashtable, DataType data)
{int Add = 0;int i = 0;assert(hashtable);if (hashtable->size.size == 0){//哈希表为空，无法删除printf("无法删除\n");return -1;}else{Add = HashFun(hashtable, data);while (hashtable->data[Add]._state != EMPTY){if (hashtable->data[Add]._state == EXIST&&hashtable->data[Add]._data == data){hashtable->data[Add]._state = DELETE;hashtable->size.del++;hashtable->size.size--;return 1;}else{
#if 0Add++;if (Add == hashtable->capacity){Add = 0;}
#else//二次探测i++;Add = Add + 2 * i + 1;Add = Add % hashtable->capacity;
#endif}}//没有找到元素，无法删除return -1;}
}//查找
int FindHashTable(HashTable *hashtable, DataType data)
{int Add = 0;int i = 0;assert(hashtable);if (hashtable->size.size == 0){printf("哈希表为空!\n");return -1;}else{Add = HashFun(hashtable, data);while (hashtable->data[Add]._state != EMPTY ){if (hashtable->data[Add]._state==EXIST&&hashtable->data[Add]._data == data){return Add;}
#if 0Add++;if (Add == hashtable->capacity){Add = 0;}
#else//二次探测i++;Add = Add + 2 * i + 1;Add = Add % hashtable->capacity;
#endif}return -1;}
}//判空
int EmptyHashTable(HashTable *hashtable)
{assert(hashtable);return hashtable->size.size == 0;
}
//哈希表元素个数
int SizeHashTable(HashTable *hashtable)
{assert(hashtable);return hashtable->size.size;
}//打印哈希表
void print(HashTable *hashtable)
{int i = 0;for (i = 0; i < hashtable->capacity; i++){if (hashtable->data[i]._state == EMPTY){printf("add=%d EMPTY %d\n", i,hashtable->data[i]._data);}else if (hashtable->data[i]._state == DELETE){printf("add=%d DELETE %d\n",i, hashtable->data[i]._data);}else{printf("add=%d EXIST %d\n", i,hashtable->data[i]._data);}}
}//销毁哈希表
void DestroyHashTable(HashTable *hashtable)
{assert(hashtable);free(hashtable->data);hashtable->data = NULL;hashtable->size.del = 0;hashtable->size.size = 0;
}

测试.c

#include"HashTable.h"void Test()
{HashTable hashtable;//初始化哈希表InitHashTable(&hashtable);//插入哈希表InsertHashTable(&hashtable, 10);InsertHashTable(&hashtable, 3);InsertHashTable(&hashtable, 19);InsertHashTable(&hashtable, 2);InsertHashTable(&hashtable, 20);//删除哈希表DeleteHashTable(&hashtable, 2);InsertHashTable(&hashtable, 4);InsertHashTable(&hashtable, 6);InsertHashTable(&hashtable, 108);InsertHashTable(&hashtable, 12);InsertHashTable(&hashtable, 8);//删除哈希表DeleteHashTable(&hashtable, 20);DeleteHashTable(&hashtable, 6);//查找if (FindHashTable(&hashtable, 19)!= -1){printf("%d的哈希地址为：%d\n", 19, FindHashTable(&hashtable, 19));}else{printf("没有找到!\n");}printf("哈希表元素个数：%d\n", SizeHashTable(&hashtable));//判空if (EmptyHashTable(&hashtable)){ printf("哈希表为空!\n");}else{printf("哈希表不为空!\n");}print(&hashtable);//销毁哈希表DestroyHashTable(&hashtable);}
int main()
{Test();system("pause");return 0;
}

这里写图片描述
这里写图片描述

http://www.lbrq.cn/news/1469521.html

相关文章：

  • 广州市网站公司/线上广告接单平台
  • 青岛在线制作网站/长沙seo行者seo09
  • 网站是用dw做的吗/品牌全案营销策划
  • 为什么要给企业建设网站/微信营销方式
  • 做企业培训的网站/网络推广服务费
  • 网站制作公司 知乎/友情链接交换平台免费
  • 电商网站策划书/打开百度一下
  • 制作企业网站的app/石家庄seo扣费
  • phpcms v9网站建设入门/磁力天堂最佳搜索引擎入口
  • wordpress 福利源码/六年级下册数学优化设计答案
  • 中英文网站建设费用/做网站用什么软件
  • 张家界做网站的人/日本樱花免m38vcom费vps
  • 长沙网站建设/哪些网站可以seo
  • 高校网站开发/昭通网站seo
  • 如何做网站竞品分析/友情链接交换方式有哪些
  • 免费网站建设制作哪家公司好/百度关键词优化排名
  • 绍兴网站建设哪好/seo模拟点击软件
  • 公司网站要怎么做/有哪些可以免费推广的平台
  • 嘉兴做网站优化哪家好/中国互联网公司排名
  • 深圳市住房和建设委员会网站/外链相册
  • 烟台网站建设开发/百度账号登录入口
  • 营销型网站建设哪个好/seo搜索引擎是什么
  • 怎样做外国石雕产品网站/seo优化方案报价
  • 怎么在阿里巴巴网站做公司/今日头条新闻视频
  • 郑州专业制作网站多少钱/类似凡科建站的平台
  • 网站建设公司线下推广/网络舆情管理
  • wordpress 改网站域名/廊坊seo排名
  • 烟台做网站/美国最新新闻头条
  • 长沙网站建设的公司/如何写推广软文
  • discuz论坛和网站同步登录/陕西网络推广公司
  • JAVA国际版同城服务同城信息同城任务发布平台APP源码Android + IOS
  • rabbitmq消息队列详述
  • cv弹窗,退款确认弹窗
  • golang的函数
  • 新手向:国内外大模型体验与评测
  • [人工智能-综述-17]：AI革命：重塑职业版图，开启文明新篇