文档章节

[译]C语言实现一个简易的Hash table(4)

4fun
 4fun
发布于 01/14 22:40
字数 494
阅读 10
收藏 0

上一章我们解释了Hash table中最重要的hash函数,并用伪代码和C语言实现了一个我们自己的hash函数hash函数碰撞是无法避免的,当发生碰撞时我们改如何有效的处理呢?这章我们就来讲解下。

处理碰撞

hash函数中将无限大的输入映射到有限的输出中,当不同的输入映射到相同的输出时,就会发生碰撞,每个的hash表都会采用不同的方法来处理碰撞

我们的哈希表将使用一种称为开放地址的双重哈希的技术来处理冲突。双重哈希使用两个散列函数来计算在发生碰撞后存储记录的索引。

双重哈希

i发生碰撞后我们使用如下方式来获取索引:

index = hash_a(string) + i * hash_b(string) % num_buckets

当没有发生碰撞时,i=0,所以索引就是hash_a的值,发生碰撞后,hash_a的结果就需要经过一次hash_b的处理。

hash_b可能会返回0,将第二项减少到0,这就导致hash表会将多个记录插入到同一个bucket中,我们可以在hash_b的结果后加1来处理这种情况,确保它永远不会为0

index = (hash_a(string) + i * (hash_b(string) + 1)) % num_buckets

算法实现

// hash_table.c
static int ht_get_hash(const char* s, const int num_buckets, const int attempt) {
    const int hash_a = ht_hash(s, HT_PRIME_1, num_buckets);
    const int hash_b = ht_hash(s, HT_PRIME_2, num_buckets);
    return (hash_a + (attempt * (hash_b + 1))) % num_buckets;
}

上一章:hash函数 下一章:完成Hash表API

本文转载自:https://github.com/jamesroutley/write-a-hash-table/tree/master/05-methods

共有 人打赏支持
4fun

4fun

粉丝 4
博文 22
码字总数 11148
作品 0
防城港
个人站长
私信 提问
[译]C语言实现一个简易的Hash table(2)

上一章,简单介绍了,并提出了本教程中要实现的几个的方法,有、和,本章将介绍使用的数据结构。 数据结构 hash表中存储的每一项的数据结构: 我们的hash表中保存着一个指向每一项的指针数组...

4fun
01/10
0
0
[译]C语言实现一个简易的Hash table(5)

上一章中,我们使用了的技术来处理,并用了实现,贲张我们将实现中的、和接口。 实现接口 我们的将会实现如下的接口: Insert函数 在中插入一条记录时,我们需要遍历整个知道找到一个空的位置...

4fun
前天
0
0
[译]C语言实现一个简易的Hash table(1)

说明 翻译过来就是,是一种提供了类似于关联数组的数据结构,可以通过执行搜索、插入和删除操作。由一些列组成,而每一个都是由的形式组成。存储时都是以存储的,因为当要定位一个时,需要把...

4fun
01/10
0
0
[译]C语言实现一个简易的Hash table(3)

上一章,我们讲了的数据结构,并简单实现了的初始化与删除操作,这一章我们会讲解和实现算法,并手动实现一个函数。 Hash函数 本教程中我们实现的将会实现如下操作: 输入一个字符串,然后返...

4fun
01/13
0
0
Redis 专栏(使用介绍、源码分析、常见问题...)

来源http://blog.csdn.net/yangbodong22011/article/details/78529448 https://github.com/hurley25 https://github.com/hurley25/ANet ANet 基于Redis网络模型的简易网络库,网络模块代码取......

libaineu2004
2017/12/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

eggjs与sequelize简单demo

参考 egg 官方文档 安装 // 依赖npm install --save egg-sequelize mysql2// ts 类型npm install --save @types/sequelize 插件,config/plugin.ts import { EggPlugin } from 'egg';......

Geeyu
42分钟前
1
0
看过上百部片子的这个人教你视频标签算法解析

本文由云+社区发表 随着内容时代的来临,多媒体信息,特别是视频信息的分析和理解需求,如图像分类、图像打标签、视频处理等等,变得越发迫切。目前图像分类已经发展了多年,在一定条件下已经...

腾讯云加社区
57分钟前
2
0
2. 红黑树

定义:红黑树(Red-Black Tree,简称R-B Tree),它一种特殊的二叉查找树(Binary Search Tree)。 要理解红黑树,先要了解什么是二叉查找树。在上一章中,我们学习了什么是二叉树,以及二叉树...

火拳-艾斯
58分钟前
3
0
input的button类型,点击页面跳转

一、input type=button 不做任何操作 例如: <input type="button" class="btn btn-primary" style="width: 30%" value="返回" onclick="window.location.href='/users/list'"></input> onc......

Sunki
今天
1
0
踩坑:js 小数运算出现精度问题

背景 在学习小程序商城源码时发现了这个问题,单价可能出现小数,小数之间运算结果会莫名其妙多出一大串数字,比如下面这样👇。 在此之前我是知道 js 中著名的 0.1 + 0.2 != 0.3 的问题的,...

dkvirus
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部