Hashtabell

Inom datavetenskap är hashtabell en datastruktur där data sparas tillsammans med en nyckel. Positionen i strukturen beräknas med en hashfunktion. Ofta behöver man en datastruktur som kan hantera både insättningar och sökningar effektivt. Då fungerar varken vektorer eller länkade listor, detta eftersom:

• Sökning i en osorterad vektor tar linjär tid;
• i en sorterad vektor kan man använda binärsökning som är mycket effektiv, men då tar istället insättningarna linjär tid;
• i en länkad lista kan man göra insättningar på konstant tid, men sökningen blir linjär.

Hashning

Hashning används för att man lätt ska kunna få tillgång till ett element i en lista. Vid insättning av ett element i den här listan utför man något som kallas för hashning. Följande exempel illustrerar detta:

Illustration av hur data kan lagras i en hashtabell

Ett stort företag vill organisera sina anställda på ett smart sätt så att deras namn kopplas till respektive telefonnummer. Telefonnumren är inom intervallet 0 till 10⁷ – 1. Om man skulle lagra dessa nummer i en vanlig lista så skulle denna listan bli onödigt stor och därför väldigt tidskrävande att leta igenom. Därför använder vi hashtabeller för att effektivisera detta. En lista skapas nu för att placera de olika namnen på personerna. Säg till exempel att vi vill lagra (8637639, Robert) i en lista med 100 platser. För att erhålla vilket index datan ska lagras på tar vi nyckeln (som i det här fallet är personens telefonnummer) modulo listans storlek, vilket blir:

  hash = 8637639 % 100;

Indexet vi får fram blir då 39 och datan kan nu lagras i listan. Metoden för att utföra denna beräkning kan skrivas:

  public int hash()
  {
      return(PhoneNum % SIZE);
  }

Där PhoneNum är personens telefonnummer och SIZE är storleken på den aktuella listan. Vi använder metoden hash både för att lägga till ett element i tabellen och för att söka efter ett visst element.

Kollision och kollisionshantering

Problemet man ofta får då man skapar en hashtabell är hur man ska hantera kollisioner. Ta till exempel de två hashkoderna 01234 och 91534, vid modulo 100 kommer båda elementen att vilja placeras på samma ställe i tabellen och detta medför därför en kollision. Det finns i princip två alternativ för att förhindra kollisioner; antingen letas en ledig plats inom tabellen upp eller så används ett separat minnesutrymme. Då det i hashtabellen sker kollisioner innebär detta också att klungbildning uppstår. ^[1]

I grunden innebär klungbildning att poster klumpar ihop sig på vissa ställen i tabellen, men en klunga kan också bestå av poster som ligger utspridda i tabellen men som ingår i en gemensam sökväg. När klungor har uppstått har de också ofta en tendens att växa till ytterligare. Klungor innebär ett sökarbete för att sätta in och återfinna poster, så det är önskvärt att försöka eliminera eller åtminstone försöka minska risken för klungbildning. Man brukar tala om två typer av klungbildning; primär klungbildning och sekundär klungbildning.

• Primär klungbildning innebär att då en kollision inträffar vid insättning, kommer den klunga som elementet hamnat i att utökas. Den nya posten kommer att sättas in i en ny sista post i slutet av klungan.
• Sekundär klungbildning avser klungor som består av poster med samma hemadress. Sådana klungor uppstår om kollisionshanteringsmetoden som används besöker samma adresser då en kollision uppstår.

Linjär sondering

Illustration av hur linjär sondering kan gå till väga i en hashtabell

Linjär sondering innebär att det element som orsakar en kollision flyttas till nästa plats som är tom i tabellen.^[2] Om tabellen har sökts igenom ända till slutet utan att hitta en tom plats går pekaren till början av tabellen och letar på nytt tills den når index vid kollisionen. Fördelen med den här metoden är att den ger en fullständig tabellbeteckning, nackdelen är att den kan vara tidskrävande jämfört med andra metoder för kollisionshantering. Linjär sondering är snabb då man lägger till ett element i tabellen, men inte speciellt bra för att söka efter eller ta bort ett visst element. Med denna typ av kollisionshantering är risken stor att en primär klungbildning bildas.

Följande kod visar hur man kan implementera en linjär sondering med java-kod i metoden add.

  public static void add(Hashable element)
  {
      int location = element.hash();
      while(list[location] != null)
          location = (location + 1) % SIZE;
      list[location] = element;
      numElements++;
  }

Kvadratisk sondering

För att angripa primär klungbildning är strategin att försöka hoppa ur en klunga om man hamnar i en. Detta är idén bakom kollisionshanteringsmetoden kvadratisk sondering.

Metoden innebär att alternativa platser i tabellen söks på ett avstånd från hemadressen som ökar med kvadraten på antalet försök. Första försöket görs en (1²) position fram i tabellen från hemadressen. Är inte den platsen ledig görs andra försöket fyra (2²) positioner fram i tabellen från hemadressen, tredje försöket görs nio (3²) steg framåt från hemadressen, osv. Sökningen sker i det här fallet snabbare än vid linjär sondering, däremot är det inte säkert att alla sökningar täcker igenom alla platser i tabellen. Idén med kvadratisk sondering är att när en ledig plats hittas innebär detta också att vi hoppar ur klungan, dvs inte hamnar i första lediga platsen efter den ursprungliga positionen.

Separat länkning

Ett annat sätt att hantera kollisioner på är att varje tabellingång utgörs av en länkad lista. En länkad lista vid en av dessa tabellingångar använder alltså samma hashkod för varje position i listan. Istället för att behöva omhasha tabellen (vilket innebär att tabellen utökas dynamiskt om fyllnadsgraden överskrider en viss nivå) utan här sker utökning av platser vid behov och på detta sätt blir implementation av koden enklare. Då ett element ska läggas till på en viss plats som redan är upptagen skapas en ny plats genom den länkade listan på det indexet. Skulle man vilja lägga till ett element på samma position igen är det bara att koppla på det element som lades dit innan med en ny plats och ett nytt index. När ett element ska tas bort från tabellen undersöks vilken nyckel elementet har och sedan undersöks den länkade listan i vilket elementet ligger. Idén med separat länkning är att även om sökning i de länkade listorna är en linjär operation kommer listorna att vara korta och sökningen tillräckligt effektiv.

Noter

1. ”Hashtabeller”. Christian Science Monitor. 13 november 2000. Arkiverad från originalet den 10 december 2013. https://web.archive.org/web/20131210215859/http://www.ida.liu.se/~TDDB32/kompletteringar/Hashtabeller.pdf. Läst 5 maj 2011.
2. Nell Dale m.f.: ”Object-Oriented Data Structures Using Java. Second edition”, Jones And Bartlett, 2006, sid. 708.