Pro ukládání synonym nemusíme vytvářet samostatnou datovou strukturu, ale můžeme k tomu využít přímo základní pole. Pokud chceme do tabulky vložit nový prvek, vypočteme nejprve jeho index v poli. Je-li položka na vypočteném indexu volná, můžeme do ní uložit nová data a jsme u konce. Je-li položka obsazená, najdeme v tabulce další možnou pozici a takto pokračujeme dále, až se podaří najít volné místo. Pozice, které budeme testovat jako náhradní v případě, že je index vypočtený mapovací funkcí již obsazen, jsou vypočteny druhou, tzv. rozptylovací funkcí.
Nejjednodušší lineární rozptylovací funkce vrátí k indexu k hodnotu (k+q) mod m, kde m je velikost tabulky a q vhodná konstanta z intervalu <1, m-1>, což znamená, že vyzkoušíme položku o q indexů dále s případným cyklickým přesunem na začátek seznamu. Je zřejmé, že hodnota q by měla být nesoudělná s velikostí tabulky m, jinak bychom rozptylovací funkcí pokryli jen část tabulky.
Důležité je také zajistit, abychom vždy s vyhledáváním skončili a nehledali v nekonečném cyklu volné místo ve zcela zaplněné tabulce.
Při vyhledávání postupujeme stejně, procházíme jednotlivé indexy v posloupnosti dané mapovací a rozptylovací funkcí až do okamžiku, kdy najdeme hledanou položku nebo volné místo v tabulce.
Operace rušení položky v tabulce je poněkud problematičtější, protože nemůžeme jednoduše uvolněnou položku označit za prázdnou a narušit tím seznamy synonym. Jednou z možností je „zaslepení“ položky buď nastavením speciálního příznaku nebo klíče. Taková položka se však může obsadit v případě, že na ni při vkládání narazíme, ovšem až poté, co si ověříme, že vkládaný klíč již v tabulce není.
 | Příklad 3.21. |
Vytvořte implementaci tabulky s rozptýlenými položkami využívající otevřené adresování s lineární rozptylovací funkcí. „Zaslepení“ položky po jejím zrušení provedeme jednoduše nastavením klíče na hodnotu null. Poznamenejme, že metoda equals() vrací při porovnání s null vždy false, proto v metodách get() a remove() tuto hodnotu nemusíme speciálně ošetřovat. Při vkládání nové položky si pamatujeme index první „zaslepené“ položky, na který nově vkládanou položku uložíme v případě, že se v tabulce nenajde. Kontrola, zda nedošlo k zacyklení při vyhledávání v plné tabulce, se provede tak, že si pamatujeme počáteční index získaný mapovací funkcí a pokud na něj narazíme podruhé, s vyhledáváním končíme.
public class OpenHashMap implements Map
{
public OpenHashMap(int capacity, int delta)
{
table = new HashMapEntry[capacity];
this.delta = delta;
}
public Object put(Object key, Object value)
{
int index0 = key.hashCode() % table.length;
int index = index0;
int firstFree = -1;
HashMapEntry entry;
while( (entry = table[index]) != null ) {
if( entry.key == null ) {
if( firstFree < 0 ) firstFree = index;
} else if( key.equals(entry.key) ) {
Object oldValue = entry.value;
entry.value = value;
return oldValue;
}
index = (index + delta) % table.length;
if( index == index0 ) {
// došlo k zacyklení hledání
if( firstFree >= 0 ) break;
assert false: "Tabulka je plna";
}
}
if( firstFree < 0 ) firstFree = index;
entry = new HashMapEntry();
entry.key = key;
entry.value = value;
table[firstFree] = entry;
return null;
}
public Object get(Object key)
{
int index0 = key.hashCode() % table.length;
int index = index0;
HashMapEntry entry;
while( (entry = table[index]) != null ) {
if( key.equals(entry.key) )
return entry.value;
index = (index + delta) % table.length;
if( index == index0 ) return null;
}
return null;
}
public Object remove(Object key)
{
int index0 = key.hashCode() % table.length;
int index = index0;
HashMapEntry entry;
while( (entry = table[index]) != null ) {
if( key.equals(entry.key) ) {
entry.key = null;
return entry.value;
}
index = (index + delta) % table.length;
if( index == index0 ) return null;
}
return null;
}
private static class HashMapEntry {
Object key;
Object value;
}
HashMapEntry[] table;
int delta;
}
|
Uvedené algoritmy implementace tabulek s rozptýlenými položkami určitě nejsou jediné možné, existuje mnoho jejich vylepšení spočívajících například v přeorganizování seznamu synonym po vložení nového prvku. Jednou z nevýhod tabulky s otevřeným adresováním je nutnost stanovit předem dostatečnou velikost tabulky, ale existují i modifikace uvedeného postupu, umožňující po vyčerpání prostoru v tabulce její rozměr upravit. Podrobnosti se opět dočtete ve specializované odborné literatuře.