首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >散列/散列函数「建议收藏」

散列/散列函数「建议收藏」

作者头像
全栈程序员站长
发布于 2022-08-28 03:09:22
发布于 2022-08-28 03:09:22
1.1K00
代码可运行
举报
运行总次数:0
代码可运行

大家好,又见面了,我是你们的朋友全栈君。

散列是一种用于以常数平均时间执行插入、删除和查找的技术。

每个关键字被映射到从0-TableSize-1这个范围中的某个数,并且被放到适当的单元中。这种映射就叫做散列函数

我认为,先用散列函数将我们所要进行操作的集合整合成散列表,是对之后的操作的一种便利。放到实际中去,我们要进行操作的集合不仅仅只是数字,例如图书馆中的书籍分类等等。而且就算是一组不连续差距较大的数字,要执行后序的插入删除和查找都是很不方便的。我们可以通过某种规定,将每个关键字放到合适的为止上去,编写散列函数。但是难免会遇到两个关键词被单列到同一个值的情况,(称为冲突),如何解决冲突是一个很关键的问题,之后另开博。

对于一般的数字,可以通过模运算

一个简单的代码实现如下(不涉及冲突)

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include<stdio.h>

int main()
{
    //自定义数组,存放初始的数字集合 
    int a[9] = {
  
  22,23,25,21,20,27,24,28,26};
    int b[9];
    int i;
    for(i = 0; i < 9; i++)
    {
        b[a[i]%10] = a[i];   //通过模10运算,将关键字散列合适的位置 
    }
    for(i = 0; i < 9; i++)   //输出散列表 
    printf("%d ", b[i]);
    return 0;
} 

输出结果如图

如果关键字是字符串,另一个很容易想到的办法是将字符中的ASCII码值加起来 伪代码如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
Index
Hash(const char *key, int TableSize)
{
    unsigned int HashVal = 0;
    while(*key != '\0')   //循环将字符中的ASCII值加起来
        HashVal += *key++;
    return HashVal % TableSize;  //对TableSize取余并返回其值
}

虽然这种方法简单又很容易得到答案,但是对于很大的表,此函数并不会很到的分配关键字。设所有关键字最多8个字符长,由于char类型的值最多是127,因此这个散列函数之恩那个取值在0到27*8之间,若TableSize超过了1w,显然这并不是一种均匀的分配。

发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/146415.html原文链接:https://javaforall.cn

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022年5月1,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
数据结构基础知识: 表 栈 队列 树 散列 堆
表,栈和队列是计算机科学中最简单和最基本的三种底层数据结构。事实上,每一个有意义的程序都将明晰地至少使用一种这样的数据结构,而栈则在程序中总是要间接地用到,不管你在程序中是否做了声明。
我是一条小青蛇
2019/11/21
1.2K0
散列查找和哈希查找_散列检索
散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使得每个关键字key对应一个存储位置f(key)。建立了关键字与存储位置的映射关系,公式如下:
全栈程序员站长
2022/11/15
1.1K0
查找-散列查找
散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使得每个关键字key对应一个存储位置f(key)。查找时,根据这个确定的对应关系找到给定值key的映射f(key),若查找集合中存在这个记录,则必定在f(key)的位置上。
全栈程序员站长
2022/08/28
1.7K0
查找-散列查找
分离链接的散列散列代码实现
散列 散列为一种用于以常数平均时间执行插入,删除和查找的技术。一般的实现方法是使通过数据的关键字可以计算出该数据所在散列中的位置,类似于Python中的字典。关于散列需要解决以下问题: 散列的关键字如何映射为一个数(索引)——散列函数 当两个关键字的散列函数结果相同时,如何解决——冲突 散列函数 散列函数为关键字->索引的函数,常用的关键字为字符串,则需要一个字符串->整数的映射关系,常见的三种散列函数为: ASCII码累加(简单) 计算前三个字符的加权和$\sum key[i] * 27^{i}$ (不太
月见樽
2018/04/27
1.8K0
散列
选择键值,冲突的时候采取不同的策略 散列函数: 简单的散列函数: 1 int hash(const string & key,int tableSize) 2 { 3 int hashVal = 0; 4 for(int i = 0; i < key.length();++i) 5 { 6 hashVal + = key[i]; 7 } 8 return hashVal % tableSize; 9 } 比较好的散列函数: 1 int hash( c
用户1154259
2018/01/17
9240
散列查找
散列同顺序、链接和索引一样,是又一种数据存储方法。散列存储的方法是:以数据集合中的每个元素的关键字k为自变量,通过一种函数h(k)计算出函数值,把这个值用做一块连续存储空间(即数组或文件空间)中的元素存储位置(即下标),将该元素存储到这个下标位置上。散列存储中使用的函数h(k)被称为散列函数或哈希函数,它实现关键字到存储位置(地址)的映射(或称转换),h(k)被称为散列地址或哈希地址;使用的数组或文件空间是对数据集合进行散列存储的地址空间,所以被称为散列表或哈希表。在散列表上进行查找时,首先根据给定的关键字k,用与散列存储时使用的同一散列函数h(k)计算出散列地址,然后按此地址从散列表中取出对应的元素。
全栈程序员站长
2022/08/27
1.5K0
散列查找
散列表(一):散列表概念、 散列函数构造方法、 常见字符串哈希函数(测试冲突)
一、散列表基本概念 1、散列表(hash table) ,也叫哈希表,是根据关键码而直接进行访问的数据结构。也就是说,它通过把关键码映射到表中一个位置 来访问记录,以加快查找的速度。这个映射函数叫做散
s1mba
2017/12/28
2.3K0
散列表(一):散列表概念、 散列函数构造方法、 常见字符串哈希函数(测试冲突)
散列函数
散列的概念属于查找,它不以关键字的比较为基本操作,采用直接寻址技术。在理想情况下,查找的期望时间为O(1)。
233333
2019/09/24
1.1K0
线性探测再散列
哈希表又称散列表。哈希表存储的基本思想是:以数据表中的每个记录的关键字 k为自变量,通过一种函数H(k)计算出函数值。把这个值解释为一块连续存储空间(即数组空间)的单元地址(即下标),将该记录存储到这个单元中。在此称该函数H为哈函数或散列函数。按这种方法建立的表称为哈希表或散列表。
全栈程序员站长
2022/08/28
6090
散列表(哈希表)
版权声明:本文为博主原创文章,转载请注明博客地址: https://blog.csdn.net/zy010101/article/details/83998492
zy010101
2019/05/25
8030
散列冲突
概念:如果当一个元素被插入时与一个已经插入的元素散列到相同的值, 那么就会产生冲突, 这个冲突需要消除。解决这种冲突的方法有几种:本章介绍两种方法:分离链接法和开放定址法
全栈程序员站长
2022/08/27
7130
数据结构之哈希表(HASH)
   当我们在编程过程中,往往需要对线性表进行查找操作。在顺序表中查找时,需要从表头开始,依次遍历比较a[i]与key的值是否相等,直到相等才返回索引i;在有序表中查找时,我们经常使用的是二分查找,通过比较key与a[i]的大小来折半查找,直到相等时才返回索引i。最终通过索引找到我们要找的元素。    但是,这两种方法的效率都依赖于查找中比较的次数。我们有一种想法,能不能不经过比较,而是直接通过关键字key一次得到所要的结果呢?这时,就有了散列表查找(哈希表)。
全栈程序员站长
2022/07/21
6310
数据结构之哈希表(HASH)
Hash算法的讲解[通俗易懂]
散列表,又叫哈希表,它是基于快速存取的角度设计的,也是一种典型的“空间换时间”的做法。顾名思义,该数据结构可以理解为一个线性表,但是其中的元素不是紧密排列的,而是可能存在空隙。
全栈程序员站长
2022/09/20
2.3K0
Hash算法的讲解[通俗易懂]
Hash查找与HashMap
通过对数据关键字的提取和观察,结合对数据总量的分析,得出合理的hash地址的大小,以及hash地址的函数
逆回十六夜
2020/02/22
4650
Java数据结构与算法解析(十二)——散列表
散列表就是一种以 键-值(key-indexed) 存储数据的结构,我们只要输入待查找的值即key,即可查找到其对应的值。
老马的编程之旅
2022/06/22
1.3K0
Java数据结构与算法解析(十二)——散列表
程序员必读:教你摸清哈希表的脾气
在哈希表中,记录的存储位置 = f (关键字),通过查找关键字的存储位置即可,不用进行比较。散列技术是在记录的存储位置和它的关键字之间建立一个明确的对应关系f 函数,使得每个关键字 key 对应一个存储位置 f(key) 且这个位置是唯一的。这里我们将这种对应关系 f 称为散列函数,又称为哈希(Hash)函数。采用散列技术将记录存储在一块连续的存储空间中,这块连续存储空间称为散列表或哈希表(Hash table)。
谭庆波
2018/08/10
4110
程序员必读:教你摸清哈希表的脾气
散列的基本概念
散列是一种思想。与已经学过的其他数据结构相比较,向量是采用循秩访问(call by rank)的访问方式,列表是采用循位置访问(call by position)的访问方式,二叉搜索树是采用循关键码访问(call by key)的访问方式,散列与他们都不一样,是采用循值访问(call by value)的访问方式。
全栈程序员站长
2022/08/28
1.7K0
解决哈希冲突的方法「建议收藏」
在实际的应用中,选取合适的哈希函数可减少冲突,但冲突是不可避免的。所以我就想给大家说几种解决哈希冲突的方法啦~
全栈程序员站长
2022/07/05
5550
C++ —— 哈希详解 - 开散列与闭散列
1. 从发⽣冲突的位置开始,依次线性向后探测,直到寻找到下⼀个没有存储数据的位置为⽌,如果⾛到哈希表尾,则回绕到哈希表头的位置(回绕方法就是进行取模)
迷迭所归处
2024/11/19
2020
C++ —— 哈希详解 - 开散列与闭散列
海量数据处理
  针对海量数据的处理,可以使用的方法非常多,常见的方法有hash法、Bit-map法、Bloom filter法、数据库优化法、倒排索引法、外排序法、Trie树、堆、双层桶法以及MapReduce法。 1、hash法 hash法也成为散列法,它是一种映射关系,即给定一个元素,关键字是key,按照一个确定的散列函数计算出hash(key),把hash(key)作为关键字key对应的元素的存储地址,再进行数据元素的插入和检索操作。   散列表是具有固定大小的数组,表长应该是质数,散列函数是用于关键字和存储
Mister24
2018/05/14
2.3K0
相关推荐
数据结构基础知识: 表 栈 队列 树 散列 堆
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档