3.8.5. Tabulka s otevřeným adresováním

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.