Hash算法解决哈希冲突的四种方法_雪人奥特曼Q的博客-程序员宅基地
目录
一、开放地址法：
所谓的开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。
寻址方法：
1、线性探测
某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。
元素的查找：通过散列函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列值的元素和要查找的元素。如果相等，则说明就是我们要找的元素；否则就顺序往后依次查找。如果遍历到数组中的空闲位置，还没有找到，就说明要查找的元素并没有在散列表中。
元素的删除：通过线性探测方法，找到一个空闲位置，就可以认定散列表中不存在这个数据。但是，如果这个空闲位置是我们后来删除的，就会导致原来的查找算法失效。本来存在的数据，会被认定为不存在。这个问题如何解决呢？我们可以将删除的元素，特殊标记为 deleted。当线性探测查找的时候，遇到标记为 deleted 的空间，并不是停下来，而是继续往下探测。
存在的问题：当散列表中插入的数据越来越多时，散列冲突发生的可能性就会越来越大，空闲位置会越来越少，线性探测的时间就会越来越久。极端情况下，我们可能需要探测整个散列表，所以最坏情况下的时间复杂度为 O(n)。同理，在删除和查找时，也有可能会线性探测整张散列表，才能找到要查找或者删除的数据。
2、二次探测
二次探测 探测的步长就变成了原来的“二次方”，下标序列就是 hash(key)+0，hash(key)+1^2，hash(key)+2^2
3、双重散列
就是不仅要使用一个散列函数。我们使用一组散列函数 hash1(key)，hash2(key)，hash3(key)……我们先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置；
装载因子
不管采用哪种探测方法，当散列表中空闲位置不多的时候，散列冲突的概率就会大大提高。
装载因子（填入表中的元素个数/散列表的长度）来表示空位的多少。装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。
二、链表法
存在多HashMap使用的处理hash冲突的方式，链表的形式，在同一个位置存放多个元素。
潜在的问题：
恶意的攻击者，可能通过精心构造的数据，所有的数据经过散列函数之后，都散列到同一个槽里。基于链表的冲突解决方法，在这个时候，散列表就会退化为链表，查询的时间复杂度就从 O(1) 急剧退化为 O(n)。
三、建立公共溢出区：
基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表
智能推荐
看这里！Java面试你必须要知道的那些知识，帮你解决95%以上的问题！-程序员宅基地
前言我想对所有程序员说：除了看视频、做项目来提高自身的技术之外，还有一种提升自己的专业技能就是：多！看！书！（本文内提到的书单笔者整理出了一份电子档作为分享，文末有免费获取方式）网络框架、中间件、容器、并发编程、虚拟机等最近几年在互联网行业是越来越火热，Netty、Docker、并发编程、虚拟机也是程序员不得不掌握的技术点，掌握熟练这些技术点，必能让你在“互联网寒冬”的这场大战中立于不败之地！今天我们就来了解当下最流行的那些新兴技术。第1章：Dubbo的简史、后续的规划和整体架构大图————Du
vnc使用方法-程序员宅基地
VNC：优秀的远程控制专家 远程控制能让你不用离开本机，就可以对其他计算机进行管理操作。能实现此功能的软件很多，比如Windows自带的终端服务、PCAnyWhere、冰河等，但是它们要么“块头”很大多占空间，要么使用麻烦不宜配置，要么需要注册缴费让人心痛，要么使用效率低下速度奇慢；要么是黑.客软件难登“大雅”之堂……像VNC（Virtual Network Computing，虚拟网络计算机
力扣：最大值 (lambda)_lambda表达式获取最大值_ZhangyiA*的博客-程序员宅基地
题目描述给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。力扣：179.最大数输入：nums = [3 , 30 , 34 , 5 , 9]输出：“9534330”题目分析：要想组成最大的整数，一种直观的想法是把数值大的数放在高位。实际上对于 nums 中的任意两个值 a 和 b，我们无法直接从常规角度上确定其大小/先后关系。下面考虑输入数组 有相同数字开头 的情况，例如 [4 , _lambda表达式获取最大值
程序化模型测试软件,程序化交易模型 指标_木头骨头石头的博客-程序员宅基地
好股票软件下载网(www.goodgupiao.com)提示：您正在下载的是：程序化交易模型 指标LC:=REF(CLOSE,1);RSI1:=SMA(MAX(CLOSE-LC,0),6,1)/SMA(ABS(CLOSE-LC),6,1)*100;卖点:=CROSS(85,RSI1)*30,COLOR00FF00,LINETHICK2;卖:IF(卖点,6.5,0),STICK,COLORGREEN..._程序化交易模型
python数据分析与挖掘实战—时间序列_时间序列挖掘分析 python-程序员宅基地
拿到一个观察值序列后，首先对它的纯随机性和平稳性进行检验，这个连个重要的检验称为序列的预处理。根据检验结果可以将序列分为不同的类型，对不同类型的序列会采取不同的分析方法。 对于纯随机序列，又称为白噪声序列。 序列的各项之间没有任何相关关系，序列在进行完全无序的随机波动，可以终止对该序列的分析。白噪声序列是没有信息可以提取的平稳序列。 对于平稳非白噪声序列，它..._时间序列挖掘分析 python
cPanel面板的三种登陆方式_cpanel 登录-程序员宅基地
临沂做网站使用国外服务器的朋友可能知道cPanel，它功能强大易于管理，我们今天说的是cPanel面板的三种登陆方式： 1、用空间的IP地址登陆，在浏览器中输入http://YourSitesIPAddress/cpanel（例如：http://1.2.3.4/cpanel这种方法）。 2、使用SSL安全登陆，即https://YourSitesIPAddress:2083。 3_cpanel 登录
随便推点
python3环境下pipenv的使用介绍_python3 pipenv-程序员宅基地
简介：virtualvenv是相对古老的一个了，有些过时了，比如说，你有时候如果不在requirements.txt文件中写入下载的包，你可能会不知道当前环境中有啥？面对这流行的npm等包管理工具，pipenv应运而生。它的一个明显的优点就是，有了一个文件，自动的记录当前环境使用的包。使用流程：1.安装python3的环境--这里就不多说了2.任意项目内根目录输入pip3 inst..._python3 pipenv
第八周实践换分币-程序员宅基地
问题及代码：/*时间：2016.10作者：夏晓林内容：换分币*/#include #include int main(){ int x,y,z,nummer=0; for(x=0; x<=100; x++) for(y=0; y<=50; y++) for(z=0; z<=20; z++)
SpringBoot多跨域请求的支持（JSONP）-程序员宅基地
在我们做项目的过程中，有可能会遇到跨域请求，所以需要我们自己组装支持跨域请求的JSONP数据，而在4.1版本以后的SpringMVC中，为我们提供了一个AbstractJsonpResponseBodyAdvice的类用来支持jsonp的数据（SpringBoot接收解析web请求是依赖于SpringMVC实现的）。下面我们就看一下怎么用AbstractJsonpResponseBodyAdvic
MIPI的DSI接口(协议/时序/时钟计算) DPHY/CPHY_dphy 时序_cy413026的博客-程序员宅基地
1.DPHY下的DSI接口可以参考以下几篇文章：液晶接口系列——MIPI之DSI协议讲解_carolven的博客-程序员宅基地_dsi接口文章目录参考链接总述接口定义DSI分层物理层：通道管理层协议层应用层DSI支持的液晶类型DSI液晶屏的三种传输模式结语参考链接[笔记分享] [Display] MIPI 协议之DSIMIPI_DSI协议简要介绍别人的MIPI自学笔记[笔记分享] [Display] MIPI 协议之PHYMIPI-DSI 三种 Video Mode 理解总述作为嵌入式Android_dphy 时序
java--List转换成json格式_json-rpc.jar-程序员宅基地
方法一首先导入jar包，json-rpc-1.0.jarpublic class List2Json { public static JSONArray ProLogList2Json(List<ProgramLog> list){ JSONArray json = new JSONArray(); for(ProgramLog pLog :..._json-rpc.jar
angular-cli下使用bootstrap_angular bootstrap-程序员宅基地
1.只使用bootstrap.css在angular-cli.json中配置： "styles": [ "styles.scss", "../node_modules/bootstrap/dist/css/bootstrap.min.css" ],2.使用bootstrap.js首先需要安装ng-bootstrap与bootstrap模块npm_angular bootstrap