Spiral hashing

Spiral hashing , även känd som Spiral Storage är en utökbar hashalgoritm. Som i alla hashscheman lagrar spiral hashing poster i ett varierande antal hinkar, med hjälp av en postnyckel för adressering. I en expanderande linjär hashfil delas hinkar i en fördefinierad ordning. Detta resulterar i att en ny hink läggs till i slutet av filen. Även om detta tillåter en gradvis omorganisation av filen, sjunker det förväntade antalet poster i den nyskapade bucket och bucket från vad den delar till hälften av det tidigare antalet. Flera försök gjordes för att lindra denna plötsliga nedgång i utrymmesutnyttjandet. Martins spirallagring använder ett annat tillvägagångssätt. Filen består av ett antal kontinuerligt numrerade hinkar. De lägre numrerade (vänster) hinkarna har ett högre förväntat antal poster. När filen expanderar ersätts hinken längst till vänster av två hinkar till höger. Vissa varianter av denna idé finns.

Spiralhashning kräver en enhetlig hashfunktion för postens tangenter till enhetsintervallet $[0,1]$ . Om hash-filen börjar vid hink ${\displaystyle S} ,$ mappas nyckeln ${\displaystyle k} till ett reellt tal$ $x=S +h(k)\i [S,S+1]$ . Den slutliga adressen beräknas sedan som $\lfloor d^{x}\rfloor$ där $d$ är "förlängningsfaktorn". När $S$ ökas skapas cirka $d$ nya hinkar till höger. Larson genomförde experiment som visade att linjär hashing fortfarande hade överlägsen prestanda jämfört med Spiral hashing.

Se även