关键字 |
| 哈希，算法，访问方法，数据结构。 |
介绍 |
| 地址计算可以在哈希表中以多种方式实现，本文讨论了哈希表的基本操作和典型哈希函数操作，以及哪些哈希表适合，哪些哈希表不适合的问题。重点介绍了哈希在不同应用中常用的哈希方法、折叠法和其他哈希方法中平方法、数字加法法、分析法。描述了必要的数据结构和算法，对预期性能进行了数学分析，并获得了实际执行时间，并与替代技术进行了比较。 |
| 哈希将“哈希”定义为“切碎，比如土豆”。这正是哈希函数通常做的事情。一个好的哈希函数会产生混乱，这样就避免了冲突。 |
目标 |
| 从哈希表中找到元素的地址是任何算法性能的重要任务之一。这个函数可以通过哈希虚构来实现。 |
| 现有的一些算法实现复杂，空间界常数大。我们还研究了动态环境下的机会数据结构，并设计了一种能够实现有效搜索和更新时间边界的变体。本研究的重点目标是减少哈希函数的计算时间。在这里，我们提出了新的算法作为NKRSQR哈希函数，目标如下。 |
| NKRSQR算法应该易于实现和理解。 |
| NKRSQR算法必须返回时间复杂度最小的结果。 |
相关工作 |
| Schmidt and Siegel[1]提出了第一个构造具有恒定计算时间和描述大小为O(n + log log u)比特的MPHF的算法，从实用角度来看，Schmidt and Siegel的算法并不具有吸引力。 |
| 该方案实现复杂，空间界常数大。Ji, Jianqiu;Li, Jianmin等[2]介绍了一种有效的方法，即min-max哈希方法，该方法显著减少了一半的哈希时间，但在估计对Jaccard相似性时可证明方差略小。此外，最小哈希估计器只包含对的相等性检查，因此它特别适合于近似最近邻搜索。实验表明，在相同哈希码长度的情况下，min-max算法的哈希时间比min-wise hash算法缩短了一半。分接技术不能加快软件实现的速度，只能提高超出处理器架构所提供的碰撞概率。这是因为，如果处理器支持在一个或两个周期内进行w位加法和乘法，那么w/2位操作也将消耗与w位操作相同的周期数。阿布塔哈，m .哈默雷，R.[3]介绍了一种新的单向哈希算法，该算法分两步设计。首先，将输入数据转换为矩阵系统，使用所有必要的转换生成初始哈希值。其次，利用第一步的输出对这些数据进行摘要，最后生成安全哈希值。Joseph Gil和Yossi Matias通过遗忘执行实现了简单的快速并行哈希。 This algorithm was design with bucket approach in data structures . Experimental result presents a simple fast and efficient parallel algorithm for the hashing problem Using n processors and the running time of the algorithm is O(lg lg n). More recently, Hagerup and Tholey [4] have come up with the best theoretical result we know of. The MPHF obtained can be evaluated in O(1) time and stored in n log e + log log u + O(n(log log n)2/ log n + log log log u) bits. The construction time is O(n+log log u) using O(n) words of space. Again, the terms involving u are negligible. In spite of its theoretical importance, the Hagerup and Tholey [4] algorithm is also not practical, as it emphasizes asymptotic space complexity only. (It is also very complicated to implement. Hashingbased approximate nearest neighbor (ANN) search in huge databases has become popular due to its computational and memory efficiency[5]. |
算法 |
| 从文献综述中我们可以得出结论，深入了解不同的数据结构可以使我们实现和设计新的算法，这些算法可以考虑根数据结构的基本原理。在选择哈希函数时使用的两个主要标准; |
| -它应该是非常容易和快速计算。 |
| 函数应该以最小的碰撞次数返回值。 |
| 下一节还将介绍如何使用哈希函数从键计算address。提出并分析了基本主题的几种变体;重点是哈希是非常有效和实用的技术。问题是，设计一个哈希函数有多简单?这很简单，用一点数论就能证明。 |
| A.工作负责人: |
| NKRSQR基于分割和合并技术。该技术由实例分解和合并为单个元素来解决问题。 |
| 人们很容易想到的两个问题是: |
| 1.为什么会有人想这么做? |
| 2.我们应该如何解决? |
| 首先，我们将数字“n”划分为“两个”槽，取“n”的余数。第一步是计算为- |
| V1(n)= n mod 10--------------------eq(1) |
| V2(n)= n / 10--------------------------eq(2) |
| 第二步应用二次方程求数的平方。下一步可以通过从键的平方的中间提取k位来完成。 |
| H (n) = (v1+ v2）2> > (w-n )---------------- eq (3) |
| NKRSQR遵循递归算法的性质。当整数值键是等概率的情况下，该算法比中平方法的效果要好。 |
| B.结果号地址空间: |
| 平方的中间(或简称为Mid- square)函数，fm是通过对标识符进行平方，然后从平方的中间使用适当数量的比特来计算得到桶地址。由于正方形的中间位通常取决于标识符中的所有字符，因此即使标识符中的某些字符相同，不同的标识符也很可能产生不同的哈希地址。 |
| 用于获取桶地址的比特数取决于表的大小。如果用n位来计算哈希地址，取值范围为2n，因此在使用这种方案时，哈希表的大小选择为2的幂。 |
| MSHA(A)= (A2)中位数的n个数 |
| 在那里, |
| MSHA=中平方哈希地址 |
NKRSQR的优缺点 |
| 前面我们提到了宇宙的说法，现在我们将讨论NKRSQR哈希函数的一些优点和缺点，该算法比现有的算法运行得更快。然而，这仅限于第99个。 |
NKRSQR结果 |
| 利用算法的基本编程实现了所提出的节能算法。我们测试了从1到99的数字在不同大小和所需时间下的输出结果。将该算法与基本的传统中平方哈希函数进行了比较。我们考虑了时间和内存空间，处理器执行时间是通过程序的CPUTIME函数来计算的。该算法具有较好的时间和空间复杂度，是计算机时代加快运算速度和最大存储容量的需要。 |
| 结果图1显示了最小时间的传统Vs新(NKRSQR)方法。以同样的方式，图2显示了最大时间的传统Vs新(NKRSQR)方法。表1。表2显示了使用传统时间方法的结果和内存使用情况，而表2显示了使用结果(NKRSQR)方法，它定义了更好的执行时间。 |
| 结果表明，在最小时间下的传统Vs新(NKRSQR)方法的图1中，本文算法的性能更好，该实现的最小运行时间远小于传统的Midsquare哈希函数。 |
| 结果显示，在Max time的传统Vs新(NKRSQR)方法的图2中，本文算法性能更好，该实现的最大运行时间远小于传统的Midsquare哈希函数。 |
| 表1显示了传统哈希平方方法所需的最小时间和最大时间。 |
| 表2显示了哈希平方法NKRSQR方法所需的最小时间和最大时间。 |
结论及未来工作 |
| 结果表明，该算法性能较好，运行时间远小于传统的中平方哈希函数。该算法具有较好的时间和空间复杂度，是计算机时代加快运算速度和最大存储容量的需要。由于本算法今后只采用传统的中平方法对哈希函数进行性能分析，并在设计上作了一些改进，因此本算法的性能可以与其他有效算法进行比较。NKRSQR是最简单的哈希函数，由除法哈希函数和平方哈希函数两种不同方法的组合得到。 |
表格一览 |
 |
|
| 表1 |
表2 |
|
|
数字一览 |
 |
 |
| 图1 |
图2 |
|
|
参考文献 |
- 辛格,m;Garg, D，“选择最佳哈希策略和哈希函数”，高级计算会议，2009。2009年国际。IEEEInternational，卷，no。，pp.50,55, 6-7 March 2009 doi: 10.1109/IADCC.2009.4808979
- 博阳;红桉,r;McGrew, D.A，“分割和连接:通用哈希函数的架构级优化技术”，集成电路和系统的计算机辅助设计，IEEE汇刊，vol.24, no. 1。11, pp.1740,1747, 2005年11月doi: 10.1109/TCAD.2005.852455
- Abutaha m;“基于非可逆矩阵的新单向哈希算法”，计算机医学应用，2013年国际学术会议，卷，no. 1。， pp. 1,5,2013年1月20-22日doi: 10.1109/ICCMA.2013.6506174
- 哈格鲁普和托利。高效的最小完美哈希在几乎最小的空间。第18届计算机科学理论研讨会论文集(STACS ' 01)，第317-326页。施普林格LNCS卷，2010,2001。
- 小君王;库马尔,美国;张世富，“半监督哈希算法在大规模搜索中的应用”，《计算机工程学报》，vol.34, no. 1。12, pp.2393,2406, 2012年12月doi: 10.1109/TPAMI.2012.48。
- Kollios g;Tsotras, V.J，“时间数据的哈希方法”，知识与数据工程，IEEE汇刊，第14卷，第4期，页。902919, 2002年7月/ 8月doi: 10.1109/TKDE.2002.1019221
- Jae-PilHeo;Youngwoon李;Junfeng他;Shih-Fu张;尹成义，“球面哈希”，计算机视觉与模式识别(CVPR)， 2012年IEEE会议，卷，no. 1。， pp.2957,2964, 2012年6月16-21日doi: 10.1109/ cpr .2012.6248024
- FengYue;李箱;明于;王佳强，“基于哈希的大规模数据库掌纹快速识别”，计算机工程学报，vol.8, no. 1。5, pp. 79,778, 2013年5月doi: 10.1109/TIFS.2013.2253321
- 13张;Chien-I李;万贝长利，“可扩展文件的线性螺旋哈希”，计算机工程，vol.11, no. 1。6, pp.969,984, 1999年11月/ 12月doi: 10.1109/69.824617。
- 米金;Yoo, c.d.，“多媒体的量子哈希”，信息取证和安全，IEEE汇刊，第4卷，第4期，第4页。982994, 2009年12月doi: 10.1109/TIFS.2009.2033221
- Yuenan李;Zheming陆;Ce朱;夏慕牛，“基于随机Gabor滤波和抖动点阵矢量量化的鲁棒图像哈希”，《图像处理》，vol.21, no. 1。4, pp. 1996,1980, 2012年4月doi: 10.1109/TIP.2011.2171698
- Lamberger m;Pramstaller:;Rechberger c;李志明，“基于Hash函数设计策略的SMASH分析”，《信息理论》，电子工程学报，vol.54, no. 1。8, pp.3647,3655, 2008年8月doi: 10.1109/ ti .2008.926420
- 戈登,D.M.;米勒,来对比;Ostapenko, P.，“-立方体上近似匹配的最优哈希函数”，信息理论，IEEETransactions on, vol.56, no. 1。3, pp. 94,991, 2010年3月doi: 10.1109/TIT.2009.2039037。
- 金,z;李,c;林,y;蔡，D.，“密度敏感哈希”，控制论，IEEE汇刊，vol.PP, no. 1。99, pp.1, 0doi: 10.1109/TCYB.2013.2283497。
|
菜单
