本文主要是介绍高级算法设计与分析 学习笔记3 哈希表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
首先我们要讨论一个把n个数据放到列表S里面的问题:
但很显然,这些数据的范围有多大这个T就得有多大,而实际上要放的数字可能就几个(比如就放一个1和一个10000000,那我还是要准备一个巨大的T),不好。
为了解决这个问题,哈希表登场了。
哈希表
哈希表的思想
性能分析
n/m就是“装载率”,一个位置平均有几个数字
要找到底,加上一开始调用hash函数的时间。
经典哈希函数
除了除法法以外还有:
这招叫乘法法,m代表有几个位置。
就是说,先让A乘以K,让其后面几位发生变化,然后在用老方法取余。为什么要多此一举?其实就是要让A变大,然后用简单的移位法取余,这样就不用做除法运算了,效率更好。
冲突怎么解决?
位置被占了,那就往下(+i)放。这就叫线性法
更复杂一点的方法,但是性能更好一点。记得这两种方法都要mod m,不要爆了。
这篇关于高级算法设计与分析 学习笔记3 哈希表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!