详解如何使用java实现Open Addressing
你好!我们这里总共向您提供三种openaddression的方法,分别为linearprobing、quadraticprobing和doublehashing。
LinearProbing
Linearprobing是计算机程序解决散列表冲突时所采取的一种策略。散列表这种数据结构用于保存键值对,并且能通过给出的键来查找表中对应的值。Linearprobing这种策略是在1954年由GeneAmdahl,ElaineM.McGraw,和ArthurSamuel所发明,并且最早于1963年由DonaldKnuth对其进行分析。
- 假设A是哈希表的一个容量N为15的数组;
- 将Keys(5、9、12、24、31、40、47、53、62、71)使用linearprobing按照顺序依次插入到数组中。
publicstaticvoidmain(String[]args){ intN=15; int[]A=newint[N]; int[]Keys={5,9,12,24,31,40,47,53,62,71}; for(inti=0;iQuadraticProbing
Quadraticprobing是计算机程序解决散列表冲突时所采取的另一种策略,用于解决散列表中的冲突。Quadraticprobing通过获取原始哈希索引并将任意二次多项式的连续值相加,直到找到一个空槽来进行操作。
- 假设A是哈希表的一个容量N为15的数组;
- 将Keys(5、9、12、24、31、40、47、53、62、71)使用quadraticprobing按照顺序依次插入到数组中。
publicstaticvoidmain(String[]args){ intN=15; int[]A=newint[N]; int[]Keys={5,9,12,24,31,40,47,53,62,71}; for(inti=0;iDoubleHashing
Doublehashing是计算机程序解决散列表冲突时所采取的另一种策略,与散列表中的开放寻址结合使用,通过使用密钥的辅助哈希作为冲突发生时的偏移来解决哈希冲突。具有openaddressing的doublehashing是表上的经典数据结构。
- 假设A是哈希表的一个容量N为15的数组;
- 将Keys(5、9、12、24、31、40、47、53、62、71)使用doublehashing(我们假设h'(k)为13-(kmod13))按照顺序依次插入到数组中。
publicstaticvoidmain(String[]args){ intN=15; int[]A=newint[N]; int[]Keys={5,9,12,24,31,40,47,53,62,71}; for(inti=0;i到此这篇关于详解如何使用java实现OpenAddressing的文章就介绍到这了,更多相关java实现OpenAddressing内容请搜索毛票票以前的文章或继续浏览下面的相关文章希望大家以后多多支持毛票票!