首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
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 删除。

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

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
C++核心准则Per.7:设计要为优化做准备
Because we often need to optimize the initial design. Because a design that ignores the possibility of later improvement is hard to change.
面向对象思考
2020/06/24
4700
C++核心准则T.120:只在确实有需要时使用模板元编程
T.120: Use template metaprogramming only when you really need to
面向对象思考
2020/09/28
5540
C++核心准则CP.8:不要使用volatile关键字实现同步处理​
CP.8: Don't try to use volatile for synchronization
面向对象思考
2020/07/03
3970
C++核心准则ES.1: 标准库好于其他库和手写代码
ES.1: Prefer the standard library to other libraries and to "handcrafted code"
面向对象思考
2020/04/16
4290
C++核心准则Per.5,6 关于性能的误解
Low-level code sometimes inhibits optimizations. Optimizers sometimes do marvels with high-level code.
面向对象思考
2020/06/24
3600
C++核心准则C.40:如果类包含不变式,则定义构造函数
C.40: Define a constructor if a class has an invariant
面向对象思考
2020/03/25
4610
C++核心准则ES.105:避免被0除
The result is undefined and probably a crash.
面向对象思考
2020/06/19
5140
C++核心准则​NL.19:避免容易被误读的名称
Readability. Not everyone has screens and printers that make it easy to distinguish all characters. We easily confuse similarly spelled and slightly misspelled words.
面向对象思考
2020/12/15
5080
C++核心准则ES.42: 使用指针时要简单且直接
Complicated pointer manipulation is a major source of errors.
面向对象思考
2020/05/20
4730
C++核心准则C.49:构造函数中应该做的是初始化而不是赋值
C.49: Prefer initialization to assignment in constructors C.49:构造函数中应该做的是初始化而不是赋值
面向对象思考
2020/03/25
1.5K0
C++核心准则C.8:存在非公有成员时,使用class而不是struct定义类
Readability. To make it clear that something is being hidden/abstracted. This is a useful convention.
面向对象思考
2020/03/25
5650
C++核心准则C.84:swap函数不应该失败
swap is widely used in ways that are assumed never to fail and programs cannot easily be written to work correctly in the presence of a failing swap. The standard-library containers and algorithms will not work correctly if a swap of an element type fails.
面向对象思考
2020/03/25
4800
C++核心准则CP.200:使用volatile只能表明该变量是非C++内存
volatile is used to refer to objects that are shared with "non-C++" code or hardware that does not follow the C++ memory model.
面向对象思考
2020/07/28
3230
C++核心准则ES.104:防止下溢
Decrementing a value beyond a minimum value can lead to memory corruption and undefined behavior.
面向对象思考
2020/06/17
3230
C++核心准则​SL.con.1:标准库array或vector好于C数组
C arrays are less safe, and have no advantages over array and vector. For a fixed-length array, use std::array, which does not degenerate to a pointer when passed to a function and does know its size. Also, like a built-in array, a stack-allocated std::array keeps its elements on the stack. For a variable-length array, use std::vector, which additionally can change its size and handles memory allocation.
面向对象思考
2020/10/30
6370
C++核心准则​SL.con.1:标准库array或vector好于C数组
C++核心准则R.4: 原始引用(T&)不包含所有权
There is nothing (in the C++ standard or in most code) to say otherwise and most raw references are non-owning. We want owners identified so that we can reliably and efficiently delete the objects pointed to by owning pointers.
面向对象思考
2020/03/26
5630
C++核心准则​​SL.con.2:除非有理由使用其他容器,默认使用STL vector
vector and array are the only standard containers that offer the following advantages:
面向对象思考
2020/10/30
4390
C++核心准则​​SL.con.2:除非有理由使用其他容器,默认使用STL vector
C++核心准则C.152:永远不要将派生类数组的指针赋值给基类指针
Subscripting the resulting base pointer will lead to invalid object access and probably to memory corruption.
面向对象思考
2020/03/25
1K0
C++核心准则C.46:默认状态下明确定义单参数构造函数
C.46: By default, declare single-argument constructors explicit
面向对象思考
2020/03/25
6560
C++核心准则C.9:最小限度暴露成员
Encapsulation. Information hiding. Minimize the chance of unintended access. This simplifies maintenance.
面向对象思考
2020/03/25
4000
推荐阅读
相关推荐
C++核心准则Per.7:设计要为优化做准备
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档