hash表长度优化证明
2024-08-25 10:37:56
hash表冲突的解决方法一般有两个方向:
一个是倾向于空间换时间,使用向量加链表可以最大程度的在节省空间的前提下解决冲突。
另外一个倾向于时间换空间,下面是关于这种思路的一种合适表长度的证明过程:
这种思路的主要做法是当位置冲突时使用随后的位置保存数据,但是毫无策略的直接使用随后的位置会造成大量的冲突,于是产生了平方位递增的方法,同时使用双方向交替的递增冲突位。
大家都知道表长度一般选取素数会比较好,那什么样的素数会比较好呢
素数除了2之外,都可以表示为4k+1和4k+3,就是对素数取模,模余要么是1要么是3,为什么突然说这个呢,因为有一个定理叫双平方定理,是说任意一个素数如果可以表示为两个自然数的平方和,那它一定模4余1。
那和这个定理又有什么关系呢,是这样的,比如说有两个点冲突了,分别在0点的两边(因为单边冲突就找下一个位置了)比如说是a和b,如果这两个冲突,就是说a和b的平方和相对于表长的模余为0,那用上这个定理就是这种情况下表长是模4余1的,那么4k+3的素数作为表长,表的利用率就更高。
最后来个图片感受下,这个图片来至于学堂在线。
最新文章
- Mysql5.7.13主从同步(复制)配置
- 如何用Excel直接查询Oracle中的数据
- Swift基础语法学习总结(转)
- AJAX部分---对比js做日期的下拉选择 和 ajax做三级联动;
- 从零开始攻略PHP(6)——代码重用与函数编写的一些注意事项
- JavaScript继承学习笔记
- ecshop 更新首页flash样式
- win7远程桌面连接
- Js 对象二
- 如何保护 .NET 应用的安全?
- 【42】了解typename的双重意义
- ETL中的数据增量抽取机制
- 设计模式 -->; (17)状态模式
- TCP 的那些事儿(上)(转)
- shell32.dll 控制网络
- MyBatis配置:在控制台打印SQL语句
- Salesforce的Developer Console简介
- js图的数据结构处理---弗洛伊德算法
- cocos源码分析--ClippingNode绘图原理
- swift语言的特征:类型系统与函数式编程:swift是面向类型和面向函数编程的语言
热门文章
- 通过ProGet搭建一个内部的Nuget服务器
- POCO Controller 你这么厉害,ASP.NET vNext 知道吗?
- async &; await 的前世今生(Updated)
- Vue + Webpack + Vue-loader 系列教程(2)相关配置篇
- 【开源毕设】一款精美的家校互动APP分享——爱吖校推 [你关注的,我们才推](持续开源更新3)附高效动态压缩Bitmap
- C++ 事件驱动型银行排队模拟
- 如何用Java类配置Spring MVC(不通过web.xml和XML方式)
- 1 selenium3.0.1无法打开火狐浏览器
- 如何让spring mvc web应用启动时就执行特定处理
- UML类图(上):类、继承和实现