大家可否知道,其实查找中有一种O(1)的查找,即所谓的秒杀。
哈希查找:
对的,他就是哈希查找,说到哈希,大家肯定要提到哈希函数,呵呵,这东西已经在我们脑子里面形成
固有思维了。大家一定要知道“哈希“中的对应关系。
比如说: ”5“是一个要保存的数,然后我丢给哈希函数,哈希函数给我返回一个”2",那么此时的”5“
和“2”就建立一种对应关系,这种关系就是所谓的“哈希关系”,在实际应用中也就形成了”2“是key,”5“是value。
那么有的朋友就会问如何做哈希,首先做哈希必须要遵守两点原则:
①: key尽可能的分散,也就是我丢一个“6”和“5”给你,你都返回一个“2”,那么这样的哈希函数不尽完美。
②: 哈希函数尽可能的简单,也就是说丢一个“6”给你,你哈希函数要搞1小时才能给我,这样也是不好的。
其实常用的做哈希的手法有“五种”:
第一种:”直接定址法“。
很容易理解,key=Value+C; 这个“C"是常量。Value+C其实就是一个简单的哈希函数。
第二种:“除法取余法”。
很容易理解, key=value%C;解释同上。
第三种:“数字分析法”。
这种蛮有意思,比如有一组value1=112233,value2=112633,value3=119033,
针对这样的数我们分析数中间两个数比较波动,其他数不变。那么我们取key的值就可以是
key1=22,key2=26,key3=90。
第四种:“平方取中法”。此处忽略,见名识意。
第五种:“折叠法”。
这种蛮有意思,比如value=135790,要求key是2位数的散列值。那么我们将value变为13+57+90=160,
然后去掉高位“1”,此时key=60,哈哈,这就是他们的哈希关系,这样做的目的就是key与每一位value都相
关,来做到“散列地址”尽可能分散的目地。
正所谓常在河边走,哪有不湿鞋。哈希也一样,你哈希函数设计的再好,搞不好哪一次就撞楼了,那么抛给我们的问题
就是如果来解决“散列地址“的冲突。
其实解决冲突常用的手法也就2种:
第一种: “开放地址法“。
所谓”开放地址“,其实就是数组中未使用的地址。也就是说,在发生冲突的地方,后到的那个元素(可采用两种方式
:①线性探测,②函数探测)向数组后寻找"开放地址“然后把自己插进入。
第二种:”链接法“。
这个大家暂时不懂也没关系,我就先介绍一下原理,就是在每个元素上放一个”指针域“,在发生冲突的地方,后到的那
个元素将自己的数据域抛给冲突中的元素,此时冲突的地方就形成了一个链表。
上面啰嗦了那么多,也就是想让大家在”设计哈希“和”解决冲突“这两个方面提一点参考和手段。
那么下面就上代码了,
设计函数采用:”除法取余法“。
冲突方面采用:”开放地址线性探测法"。
结果:
索引查找:
一提到“索引”,估计大家第一反应就是“数据库索引”,对的,其实主键建立“索引”,就是方便我们在海量数据中查找。
关于“索引”的知识,估计大家都比我清楚,我就简单介绍下。
我们自己写算法来实现索引查找时常使用的三个术语:
第一:主表, 这个很简单,要查找的对象。
第二:索引项, 一般我们会用函数将一个主表划分成几个子表,每个子表建立一个索引,这个索引叫做索引项。
第三:索引表, 索引项的集合也就是索引表。
一般“索引项”包含三种内容:index,start,length
第一: index,也就是索引指向主表的关键字。
第二:start, 也就是index在主表中的位置。
第三:length, 也就是子表的区间长度。
结果:
ps: 哈希查找时间复杂度O(1)。
索引查找时间复杂度:就拿上面的Demo来说是等于O(n/3)+O(length)
分享到:
相关推荐
算法系列15天速成——第六天-五大经典查找【下】,算法数据结构 五大常用算法
算法系列15天速成——第五天-五大经典查找【中】,算法数据结构 五大常用算法
算法系列15天速成——第四天-五大经典查找【上】 五大常用算法
五大经典查找【下】 算法系列15天速成——第五天 五大经典查找【中】 算法系列15天速成——第四天 五大经典查找【上】 算法系列15天速成——第三天 七大经典排序【下】 算法系列15天速成——第二天 七大经典排序【中...
算法系列15天速成 数据结构 算法 树、图、堆栈、队列
今天是大结局,说下“图”的最后一点东西,“最小生成树“和”最短路径
计算机系的教材,算法导论————————————————————————————————
今天说下最后一种树,大家可否知道,文件压缩程序里面的核心结构,核心算法是什么?或许你知道,他就运用了赫夫曼树
五大常用算法——回溯算法详解及经典例题,算法数据结构 五大常用算法
五大常用算法——分支限界算法详解及经典例题,算法数据结构 五大常用算法
五大常用算法——动态规划算法详解及经典例题,算法数据结构 五大常用算法
代码 基于遗传算法的优化计算——建模自变量降维代码代码 基于遗传算法的优化计算——建模自变量降维代码代码 基于遗传算法的优化计算——建模自变量降维代码代码 基于遗传算法的优化计算——建模自变量降维代码代码...
深大算法实验五——查找所有的桥
思维进化算法优化BP神经网络——非线性函数拟合.zip
垃圾回收GC经典算法(csdn)————程序
算法模板.doc————电子版_doc版
算法之NlogN排序算法(csdn)————程序
简单的算法举例(csdn)————程序
《算法竞赛入门经典——训练指南》中例题和习题的参考代码,由刘汝佳编写
算法竞赛入门经典——算法实现.docx