Szükséges előismeret: Függvények aszimptotikus viselkedése, Jelölések, Egyirányú láncolt listák, Hasító tábla és a hasító függvény
Algoritmusok és adatszerkezetek 1. > Hasító táblák > Láncolt hashelés
Láncolt hashelés (Collision resolution by chaining)
Ez az oldal egy gyakorlati jegyzet, amelynek anyagára a saját gyakorlati óráimat is építem. Fontos azonban, hogy vizsgára ne kizárólag ebből készülj!
Az elmúlt időszakban többször előfordult, hogy hallgatók az oldalon található anyagból készültek a vizsgára, és emiatt bizonyos feladatokra nem kaptak pontot. Ennek oka, hogy az itt szereplő anyagokat a tantárgyfelelősök nem ellenőrizték és nem lektorálták, így előfordulhatnak benne pontatlanságok, illetve olyan megfogalmazások vagy megközelítések, amelyek nem feltétlenül egyeznek a vizsgán elvárttal.
Az oldalt szabadidőmben készítettem azzal a céllal, hogy segítsem a hallgatók tanulását. A tartalom összeállítását hosszas anyaggyűjtés, könyvek és egyéb szakmai források áttekintése előzte meg, ennek ellenére hibák természetesen előfordulhatnak.
Folyamatosan igyekszem javítani a hibákat és pontosítani az anyagot.
Ha a direkt címzés nem alkalmazható, vagy nem gazdaságos, hasító függvényt alkalmazunk. Ez esetben az elem a $h(k)$ helyre kerül, vagyis egy $h$ hasító függvényt használunk arra, hogy a rést a $k$ kulcsból meghatározzuk.
A láncolásnál az ugyanarra a résre leképződő elemeket összefogjuk egy láncolt listába. $m$ darab S1L listában tároljuk az adatrekordokat. Az $i$-edik rés egy pointert tartalmaz, mely az $i$ címre leképződő elemek listájának fejére mutat. Ha nincs ilyen elem, akkor a $i$-edik rés nullpointert tartalmaz.
Beszúráskor a megfelelő lista elejére szúrjuk be az új elemet azért, hogy a beszúrás minél egyszerűbb legyen. A beszúrás előtt ellenőrizzük a megfelelő listát, a duplikált kulcsok elkerülése céljából.
$T:E1^*[m]$, ahol a $T$ egy $m$ méretű tömb (hasítótábla), amely $E1$ típusú pointereket tárol.
| $E1^*$ |
| $+ \space key : U$ $+ \space next : E1^*$ $+ \space ...$ |
| $+ \space E1() \{ next := \emptyset \}$ |
| $init(T : E1^*[m])$ |
| $i := 0 \space to \space m-1$ | ||||
| $T[i] := \emptyset$ | ||||
| $insert(T : E1^*[]; p : E1^*) : \mathbb{B}$ |
| $k := p \rightarrow key$ | ||||
| $s := h(k)$ | ||||
|
$searchS1L(T[s], k) = \emptyset$
|
||||
| $p \rightarrow next := T[s]$ | $\text{return} \space false$ | |||
| $T[s] := p$ | ||||
| $\text{return} \space true$ | ||||
| $search(T : E1^*[]; k : U) : E1^*$ |
| $\text{return} \space searchS1L(T[h(k)], k)$ |
| $searchS1L(q : E1^*; k : U) : E1^*$ |
| $q \neq \emptyset \land q \rightarrow key \neq k$ | ||||
| $q := q \rightarrow next$ | ||||
| $\text{return} \space q$ | ||||
| $remove(T : E1^*[]; k : U) : E1^*$ |
| $s := h(k)$ | |||||
| $p := \emptyset$ | |||||
| $q := T[s]$ | |||||
| $q \neq \emptyset \land q \rightarrow key \neq k$ | |||||
| $p := q$ | |||||
| $q := q \rightarrow next$ | |||||
|
$q \neq \emptyset$
|
|||||
|
$p = \emptyset$
|
$\text{SKIP}$ | ||||
| $T[s] := q \rightarrow next$ | $p \rightarrow next := q \rightarrow next$ | ||||
| $q \rightarrow next := \emptyset$ | |||||
| $\text{return} \space q$ | |||||
Műveletigény:
- $T_{init}(m) \in \Theta(m)$
- A másik három művelet futási ideje $mT(n) \in \Theta (1)$, $MT(n) \in \Theta (n)$, $AT(n, m) \in \Theta (1 + \alpha)$