3.8.3. Tabulka s rozptýlenými položkami

Ideální vyhledávací tabulkou je tabulka s přímým adresováním, ve které jsou hledané položky umístěny v poli na indexu, který se přímo rovná hodnotě klíče. Taková tabulka má z hlediska času přístupu vynikající vlastnosti, neboť doba vyhledání i doba vkládání položky je pro ni konstantní. Rozsah velikosti klíčů může ovšem vést k velkým paměťovým nárokům, které však můžeme redukovat pomocí mapovací funkce (hash function). Tato funkce zobrazuje klíče do určitého intervalu hodnot {0, 1, ..., m-1}, kde m je velikost tabulky. Je-li mapovací funkce zároveň prostým zobrazením, tj. mapují-li se každé dva různé klíče na různé indexy, zůstávají vlastnosti tabulky s přímým adresováním zachovány.

Není-li však mapovací funkce prostá, může docházet ke kolizím, kdy se dva nebo více klíčů (synonym) zobrazují na tutéž pozici v tabulce. Tuto situaci můžeme řešit několika možnými způsoby:

Minimalizovat počet kolizí můžeme například použitím pseudonáhodné mapovací funkce, která všechny klíče rozloží pokud možno rovnoměrně do dostatečně velkého prostoru. Je asi zřejmé, že čím je obsazení tabulky nižší, tím je menší pravděpodobnost vzniku kolize a tedy i doba potřebná k vyhledávání (jak jsme si již uvedli, v ideálním případě nenastávají žádné kolize a doba vyhledávání je konstantní).

Pokud již ke kolizi dojde, pak pro jejich řešení se běžně používají následující dvě metody:

Je zřejmé, že pro kvalitní implementaci tabulky s rozptýlenými položkami je v prvé řadě důležitá kvalita mapovací funkce. Ta musí v rámci daného rozsahu indexů pokud možno rovnoměrně využívat všech pozic. Pokud bychom například pro tabulku identifikátorů v programu použili jako mapovací funkci ASCII hodnotu prvního znaku jména, využili bychom pouze 26 pozic v tabulce. Navíc v případě, že programátor používá pro názvy tříd identifikátory začínající vždy písmenem C, by vznikalo velké množství synonym právě na pozici odpovídající tomuto písmenu.

Jazyk Java předpokládá, že každý objekt implementuje metodu

public int hashCode()
která pro něj vypočte reprezentativní celočíselnou hodnotu, která se dá použít např. jako vstupní hodnota pro výpočet mapovací funkce. Tato metoda musí dodržet dvě podstatná pravidla:

Hodnota hashCode() však nemusí být jednoznačná, jestliže pro dva objekty vrátí totéž číslo, pak to nemusí znamenat, že jsou si z hlediska volání equals() rovné. Třída Object, která je předchůdcem všech dalších tříd, implementuje metodu hashCode() obvykle tak, že vrátí interní adresu objektu převedenou na celé číslo. Vzhledem k tomu, že implementace metody equals() ve třídě Object porovnává adresy objektů, je toto chování v souladu s uvedenými podmínkami.

V konkrétních aplikacích však budeme chtít zajistit, aby se i různé objekty mohly považovat za shodné, například pokud jde o dvě instance typu String obsahující tentýž řetězec znaků. Pak je třeba předefinovat současně metodu hashCode() i equals(). Nesmíme také zapomenout na třídy implementující rozhraní Comparable, jehož metoda compareTo() by měla být rovněž konzistentní s metodou equals() v tom smyslu, že pro každé dva objekty vrátí nulu právě tehdy, jestliže pro ně equals() vrátí true.

Příklad 3.19.
Vytvořte třídu User reprezentující uživatele v operačním systému s přihlašovacím jménem, heslem a skutečným jménem. Zajistěte vhodnou definici metod equals() a hashCode().

Budeme považovat dvě instance třídy User za totožné, pokud obsahují totéž přihlašovací jméno. To znamená, že jako hodnotu hashCode() můžeme použít výsledek volání hashCode() na přihlašovací jméno uživatele.

class User { 
   public User(String login, String password, String name) 
   { 
      this.login    = login; 
      this.password = password; 
      this.name     = name; 
   } 
 
   public String getLogin() { return login; } 
   public String getPassword() { return password; } 
   public String getName() { return name; } 
 
   public boolean equals(Object obj)  
   { 
      if( obj == null ) return false; 
      if( !(obj instanceof User) ) 
         return false; 
      User other = (User)obj; 
      return login.equals(other.getLogin()); 
   } 
 
   public int hashCode() 
   { 
      return login.hashCode(); 
   } 
 
   private String login; 
   private String password; 
   private String name; 
}

A teď již máme vše připraveno k tomu, abychom se mohli věnovat některým technikám používaným pro implementaci tabulek s rozptýlenými položkami.