Hash算法、hash_table、一致hash名词解读
haoteby 2024-11-11 12:45 10 浏览
前言
Hash（哈希）作为一个coder面试中高频出现的名词，了解掌握它非常重要；
但其实，很多同学对于这些名词经常搞混，或答非所问，或不得要领；
本文就这些基本名词作一些解释，希望能帮助看到的同学梳理知识点，提供一些帮助。
本文会围绕名词解释进行。
名词解释
- hash、哈希
- hash也就是哈希，也叫散列，其实算是一种技术；
- 通过hash函数，将一组输入映射到一个限定范围内数值；
- 哈希算法
- 这里就举个最简单的例子，这个例子将一个任意整形，映射到0-9范围内。
int hash_func(int input){
return input%10;
}- 哈希冲突
- hash冲突就是多个输入产生了同样的映射地址，比如上面的例子，1和11输出都是1，这就是hash冲突；
- 由于应用场景的需要，优秀的hash算法总是尽量避免hash冲突；本篇暂不深究冲突解决；
- hash_table
- 一种基于hash（映射）的数据结构，用于存储kv类数据；
- 原理是根据输入key，通过hash算法，直接计算出存储地址；
- 在解决好冲突的前提下，他的存取效率非常之高，因为只需要执行一次hash函数计算，性能O（1），而像map之类的结构，则需要经过多次查询，效率O（lgn）；
- 一般不需要排序并且数据量比较大的数据，都可以使用hash_table来存储。
- hash_map
- 各种库里基于hash_table实现的数据结构基本都叫这个名字，stl里的hash_map已经被unordered_map实现代替了。
- 一致性hash
- 一致哈希 是一种特殊的哈希算法。在使用一致哈希算法后，哈希表槽位数（大小）的改变平均只需要对k/n个关键字重新映射，其中 k是关键字的数量，n是槽位数量。然而在传统的哈希表中，添加或删除一个槽位的几乎需要对所有关键字进行重新映射。【wiki】
- 一致性hash主要用于解决分布式缓存问题；
- 一个典型的用法是，将分布式节点hash到一个整数环，环上的每个间隔视为一个槽或者桶；
- 目标数据的key同样hash到这个整数环上，依据处于环上的位置获取应该存储的节点；
- 当一个节点移除时，只需要将从这个节点位于环上位置到下一位置之间的key进行重新hash缓存即可；
- 当新增一个节点时，也同样只需要将这个节点位于环上位置到下一位置之间的key进行重新hash即可。
如果还有不清楚的，评论区见
相关推荐
- JAVA零基础入门:JDK的概述及安装（jdk完整安装教程）
-
一.什么是jdkJDK(JavaDevelopmentToolKit)是Java开发工具包，JDK是整个JAVA的核心，包括了Java运行环境（JavaRuntimeEnvirnment），一...
- 开源、强大的工作流引擎:camunda入门介绍
-
原创不易，请多多支持！对Java技术感兴趣的童鞋请关注我，后续技术分享更精彩。简介CamundaisaJava-basedframeworksupportingBPMNforwork...
- Centos8搭建Java环境(JDK1.8+Nginx+Tomcat9+Redis+Mysql)
-
一、开篇1.1目的每次换新的服务器，都要找资料配下环境，所以我写这篇文章，重新梳理了一下，方便了自己,希望也能给大家带来一些帮助。安装的软件有：JDK1.8+Nginx+Tomcat9+...
- 记录一次tomcat的升级过程（tomcat6升级tomcat8）
-
原因：ApacheTomcat资源管理错误漏洞(CVE-2021-42340)版本：ApacheTomcat/9.0.46,tomcat解决方法：升级tomcat9到最新版本9.0.581．官...
- Tomcat10安装与配置图文教程（tomcat安装及配置）
-
Tomcat10安装与配置图文教程1、百度搜索“tomcat下载”，进入官网下载https://tomcat.apache.org/index.html...
- VS2022配置x86/x64调用32位和64位汇编语言动态库环境
-
配置X86MASM汇编环境1.创建项目打开VS2022创建新项目，新建asm文件（注意要手动修改cpp文件后缀名为asm文件后缀名）。2.设置入口点选择菜单栏中的“调试”-“demo调试属性”-...
- ARM版Win10用户狂喜 微软全新补丁让应用不再不兼容
-
Windows10onARM仅支持模拟32位的X86应用程序，这意味着大多数的桌面应用是无法在这一平台上运行的，这在很大程度上限制该平台的发展。为了解决这一问题，微软在内部开发频道推出可用于AR...
- 分享收藏的 oracle 11.2.0.4各平台的下载地址
-
概述oracle11.2.0.4是目前生产环境用的比较多的版本，同时也是很稳定的一个版本。目前官网上已经找不到下载链接了，有粉丝在头条里要求分享一下下载地址。一、各平台下载地址...
- Android-x86现已基于5.1.1 Lollipop:支持UEFI和64位内核
-
采用Linux内核的Android-x86，旨在为PC带来最新的Android移动操作系统体验。而近日，该操作系统已经发布了Android-x865.1的首个候选发布（RC）版本。发行说明中提到：A...
- Linux Kernel源码阅读: x86-64 系统调用实现细节(二)
-
特别说明：该文章前两天发布过，但一直在审核中。看头条网友说字数太多可能一直处于审核中状态，我把该文章拆分成几个章节发布，如影响阅读体验还请见谅。五、系统调用编号...
- 树莓派4B安装win10后实测，CPU秒杀AMD Athlon64 3200+
-
在上一篇文章介绍了如何给树莓派4B安装win10系统，这篇就简单对系统进行测试，上一篇文章链接https://www.toutiao.com/i7015518822056886821/因为树莓派是a...
- 一键离线部署x86、arm64 RabbitMQ，花了2天去验证整理，直接拿去
-
最近有一个项目，客户是内网网络，只能离线部署，采用的麒麟ARM64服务器系统，不能远程部署，需要提前准备离线部署包让客户IT拷备上去再现场部署，部署时间就只有1天。自家系统采用的vue+springb...
- Linux软件包管理（linux系统软件包的安装方法,并简要说明其特点）
-
Linux系统如果需要安装软件怎么办？如何安装，大概有以下几种方式1.二级制软件包管理（RPM、YUM）...
- Tachyum要做全球最强64位处理器:性能比X86强，面积比ARM小
-
全球半导体芯片研发、生产最强的国家非美国莫属，如果有某家美国公司宣布要开发性能超强的芯片，大家不会意外，但要是一家斯洛伐克初创公司宣布要研发超级芯片呢？Tachyum公司就是这样一家公司，成立于201...
- Android L 64位模拟器终于来了:x86独享
-
GoogleI/O2014大会已经过去了很久，64位的AndroidL依然停留在纸面上，但现在至少可以让开发者们先行品尝品尝了：64位的AndroidL模拟器已经发布。这次公布的模拟器镜像是专...