Create your own awesome maps

Even on the go

with our free apps for iPhone, iPad and Android

Get Started

Already have an account?
Log In

táblázat by Mind Map: táblázat
0.0 stars - reviews range from 0 to 5

táblázat

export modulja

műveletei (5+2)

üres (létrehozás)

beilleszt

töröl

keres

hibás?

+elemszám

+módosít (= töröl + beilleszt)

+ újraszervez*

*: csak bizonyos megvalósításoknál

Tulajdonságai (5)

1. Üres táblázat minden eleme nem definiált értékű, és nulla az elemszám

2. Ha van még hely, akkor az elem beszúrható, és az elemszám egyel nő, kivéve ha ugyanilyen kulcsút már tartalmaz a táblázat

3. Létező elem törölhető és az elemszám egyel csökken, nem létező törlése nem definiált

4. Létező elem módosítható (ekvivalens egy törlés és egy beszúrás művelettel) nem létező elem módosítása és a KULCS módosítása nem definiált

5. Ha van keresett kulcsú elem a táblázatban akkor az kereshető

kulcstranszformációs függvények

mit várunk tőlük (5)

1. a lehetséges kulcsok halmaza legyen része az értelmezési tartományának

2. értékkészlete a teljes {0..M-1} halmaz

3. "egyenletesen" (tehát ne "csomósan") szórja szét a közel azonos kulcsokat

4. kevés ütközést produkáljon

5. amennyire csak lehet egyszerűen kiszámolható legyen

konkrét példák

osztó módszer h(k)=k MOD M, a módszer jósága füg M-től, 2 hatványaira különösen rossz, érdemes prímszámra választani a méretet

szorzó módszer a kulcsot egy bazinagy prímmel szorozzuk, és a középső bitekből alkotjuk meg az indexet

négyzetközép módszer a szám négyzetéből vesszük a középső biteket