Základem tabulky s řetězením synonym bude pole ukazatelů na první prvek seznamu synonym. Každá operace začíná výpočtem indexu do tohoto pole - určíme hodnotu hashCode() klíče a pomocí operace modulo ji převedeme do intervalu indexů pole:
int index = key.hashCode() % table.length; HashMapEntry entry = table[index];
Dále již následuje v závislosti na konkrétní akci vyhledání položky v seznamu, případně její odstranění nebo vytvoření nové položky a zařazení na začátek seznamu. Zařazení nové položky na začátek seznamu je výhodné ze dvou důvodů - jednak je tato operace jednoduchá, nepotřebujeme si pamatovat ukazatel na předchůdce, jednak je v mnoha aplikacích pravděpodobné, že budeme dříve hledat ty položky, které jsme vložili naposledy. Výsledné řešení ukazuje následující příklad.
 | Příklad 3.20. |
Vytvořte implementaci tabulky s rozptýlenými položkami využívající řetězení synonym do jednosměrně vázaného lineárního seznamu. Konstruktor třídy ChainHashMap má jako parametr počet položek pole, do něhož se budou ukládat začátky seznamů synonym. Velikost tohoto parametru tedy určuje, jak rychle se tabulka zaplní a začne docházet k trvalým konfliktům, které zhorší rychlost vyhledávání i vkládání.
public class ChainHashMap implements Map
{
public ChainHashMap(int capacity)
{
table = new HashMapEntry[capacity];
}
public Object put(Object key, Object value)
{
int index = key.hashCode() % table.length;
HashMapEntry entry = table[index];
while( entry != null ) {
if( key.equals(entry.key) ) {
Object oldValue = entry.value;
entry.value = value;
return oldValue;
}
entry = entry.next;
}
entry = new HashMapEntry();
entry.key = key;
entry.value = value;
entry.next = table[index];
table[index] = entry;
return null;
}
public Object get(Object key)
{
int index = key.hashCode() % table.length;
HashMapEntry entry = table[index];
while( entry != null ) {
if( key.equals(entry.key) )
return entry.value;
entry = entry.next;
}
return null;
}
public Object remove(Object key)
{
int index = key.hashCode() % table.length;
HashMapEntry entry = table[index];
HashMapEntry last = null;
while( entry != null ) {
if( key.equals(entry.key) ) {
if( last == null )
table[index] = entry.next;
else
last.next = entry.next;
return entry.value;
}
last = entry;
entry = entry.next;
}
return null;
}
private static class HashMapEntry {
Object key;
Object value;
HashMapEntry next;
}
HashMapEntry[] table;
}
|
Dalšího vylepšení můžeme dosáhnout například tím, že místo seznamu budeme ze synonym vytvářet binární vyhledávací strom. Výhodou tabulky s řetězením synonym je zejména to, že její kapacita není principiálně nijak omezená, i když s přibývajícími položkami v tabulce se složitost vyhledávání stále více blíží lineární.