Hash Table Algorithm

Hash map er gagna gagnagrunnur sem útfærir associative array abstract data type Uppbyggingin er gerð úr kortuðum keys og values Hash table notar hash function til að reikna index inn í array af buckets sem inniheldur index, sem svo er hægt að nota til að finna viðeigandi gildi.

Hash Table dæmi:

Hash Table árekstrur

Ef tveir keys hafa sama index inni í buckets eða slots verður árekstur, til að laga það eru tvær leiðir til að laga það.

Linear Probing: Með þessari leið þá ef það er árekstur þá mun vera fært þaða key um ein hærri index til að það mun finna tóman index, svo til að leita af uppýsingonum mun það nota key til að finna indexin en ef er ekki þar mun fara upp ein til að loksins finnur upplýsingarnar, gallin er að það gætti gerst að það mun þurfa að fara í gegnum allan Hash Table til að finna það.

Separate Chaining: Með því að nota seperate chaining þá í staðin að færra key upp ein index þá mun það búa til lista fyrir þann index sem mun svo hava allar upplýsíngar nokkra keys í einum index og svo þegar mun vera að finna upplýsingarnar þarf það ekki leingur að fara gégnum allan Hash Table bara allan index

Hash Table collision Separate Chaining mynda dæmi:

Fullkomin Hash function

Ef er vitað hvað allir keys eru er hægt að búa til Fullkomin hash function sem hefur einga árekstra. Sem endar með Hash Table sem uppýsingarnar finnast næstum strax því bara þarf að finna key. En líkunar á því eru svo láar að vanalega gerist það ekki.

Fullkomin Hash function mynda dæmi: