出口外贸网站,邯郸网站设计培训机构,项目建设网站,幼儿做爰网站一
了解一些散列的基本概念#xff0c;仅从文字角度#xff0c;整理了最基础的定义。
发现一本书#xff0c;《算法图解》#xff0c;微信读书APP可读#xff0c;有图#xff0c;并且是科普性质的读物#xff0c;用的比喻很生活化#xff0c;可以与《算法导论》合并起…一
了解一些散列的基本概念仅从文字角度整理了最基础的定义。
发现一本书《算法图解》微信读书APP可读有图并且是科普性质的读物用的比喻很生活化可以与《算法导论》合并起来看会轻松很多。 P142散列数 hash table 槽 slot 对应全域中一个关键字 两个关键字映射到同一个槽里冲突 散列本质就是把任意长度的输入通过散列算法变成固定长度的输入你可以理解为它是一种压缩性的映射所以散列值的空间会小于输入空间便于储存。 又因为它很难找到逆向规律的特性所以也可以用作数字签名来保障数据传递的安全性散列也称为哈希Hashhash算法也因此被广泛应用在互联网应用中。 散列表的基本概念 假设某应用要用到一个动态集合其中每个元素都有一个属于[0…p]的关键字此处p是一个不太大的数且没有两个元素具有相同的关键字则可以用一个数组[p1]存储该动态集合并且使用关键字作为数组下标进行直接寻址。这一直接寻址思想在前面的非比较排序中就有所应用。然而当p很大并且实际要存储的动态集合大小np时这样一个数组将浪费大部分空间。 p“”/p时这样一个数组将浪费大部分空间。 散列表(Hash table)使用具有m个槽位的数组来存储大小为n的动态集合。αn/m被定义为散列表的装载因子。在散列表中具有关键字k的元素的下标为h(k)即利用散列函数h根据关键字k计算出槽的位置。散列函数h将关键字域[0…p]映射到散列表[0…m-1]的槽位上这里m可以远小于p从而缩小了需要处理的下标范围并相应地降低了空间开销。散列表带来的问题是两个关键字可能映射到同一个槽上这种情形称为碰撞。因此散列函数h应当将每个关键字等可能地散列到m个槽位的任何一个中去并与其它关键字已被散列到哪一个槽位中无关从而避免或者至少最小化碰撞 二 散列冲突解决方案
开放寻址法 开放寻址法的核心思想是如果出现了散列冲突我们就重新探测一个空闲的位置。 开放寻址法解决方案有线性探测法、二次探测、双重散列等方案 线性探测法Linear Probing1插入数据当我们往散列表中插入数据时如果某个数据经过散列函数之后存储的位置已经被占用了我们就从当前位置开始依次往后查找到底后从头开始看是否有空闲位置直到找到为止。
2查找数据我们通过散列函数求出要查找元素的键值对应的散列值然后比较数组中下标为散列值的元素和要查找的元素是否相等若相等则说明就是我们要查找的元素否则就顺序往后依次查找。如果遍历到数组的空闲位置还未找到就说明要查找的元素并没有在散列表中。 当然这里存在一个问题就是存数据那块位置往前的某个数据被删除了那么线性探索查到那块位置的时候就会判断元素不在散列表查找就会失效面对这个问题我们在删除的时候用下面删除的方法
P156完全散列 perfect hashing 关键字集合是静态 像CD-ROM一样存入不可变 马尔可夫不等式 摊还期望时间 全域散列它在任意输入的情况下都能达到比较好的平均情况性能。但值得注意的是“平均情况性能”这六个字就像BFPRT——Top k问题的终极解法一文中介绍的随机快速选择算法一样虽然很难遇到导致最坏情况发生的输入但这种可能性仍然是存在的没有完全消除。我们需要继续追寻找到像BFPRT一样能在确定情况下提供出色的最坏情况性能的散列算法。 完全散列算法给出了关键字集合为静态时的解决方案。我们来看看它如何在最坏情况下达到 O(1) 的时间复杂度。最直接的想法让散列数组的长度 m 尽量大因为对于固定的关键字集合 m 越大冲突的可能性就越低。但是无论 m 取多大的数冲突的可能性都不会降到0只会越来越接近0。此时静态关键字集合的好处就出来了当冲突的可能性较低时我们可以多试几个散列函数找到不发生冲突的那个确定为最终使用的散列函数。 三 FPGA与散列数相关的应用举例 安全散列算法SHA(Secure Hash Algorithm,SHA是美国国家标准和技术局发布的国家标准FIPS PUB 180-1,般称为SHA-1。其可对长度不超过264位的消息产生160位的消息摘要输出可在NIST的网站上获得该算法的数学原理。IFF(Identification Friend or Foe, IFF用于确定输入密钥是否正确。
其工作方式如下
①在FPGA内部构造随机数生成模块用于产生消息Q并通过1-Wire总线发送DS2432芯片
②DS2432内部拥有一个由设计者设定的密钥。由该密钥并结合
③与此同时FPGA内部产生一个期望的响应E判断该期望响应是否与DS2432的真实响应A一致
④如果E与A吻合则判断该设计为正版设计否则判定为盗版设计
⑤最终FPGA程序可以对盗版设计做出程序锁止或减少功能。
