Gyakorlati alapok III.

Az adatszerkezetek - Tábla

A tábla egyetlen eleme 1 adatot + hozzá tartozó, egyedi kulcsot tartalmaz:

Forrás - Source: Gábor Dénes Főiskola

Az egyedi kulcs bármi lehet, ami képes hibamentesen beazonosítani az adatot. Például könyvtári nyilvántartás esetén az egyedi kulcs lehet:

• polcszám + könyvcím + egyedi azonosító (az utóbbi akkor fontos, amennyiben feltételezzük, hogy lehetséges 1 könyvnek több példánya, illetve több kiadása is).

Fajtái

• soros tábla - konkrét programozási implementációja a tömb, amelyben az elemek sorosan, növekvő sorrendben indexelve (de sokszor rendezetlenül) helyezkednek el. Kis elemszám esetén jó hatásfokú, de kulcsrendezetlenség esetén már nem optimális tárolási mód,

• önátrendező tábla - alapötlete, hogy a keresett kulcs kerüljön mindig a tábla elejére, ezáltal előbb-utóbb a sohasem keresett kulcs a tábla végére fog kerülni,

• rendezett tábla - a tábla kulcsok szerint rendezett,

• hash-tábla - az adatelem helye nem indexeléssel, sem kulcsrendezéssel van meghatározva, hanem egy köztes, úgynevezett hash-függvény jelöli ki. Ez szintén egyedi kulcs-, vele címazonosítást tesz lehetővé. Ennek ellenére vannak olyan hash-függvények, amelyek 1 címre több kulcsot is leképeznek, az ilyen kulcsokat szinonimáknak nevezzük, ám ezek adminisztrációja további terheket jelent az adatszerkezet fejlesztője számára. Tágabb értelemben a hash-függvények olyan eljárások, amelyekkel bármilyen hosszúságú adatot adott hosszúságra képezhetünk le, ezért kiválóan használhatók kriptográfiai és biztonságtechnikai célokra. Mivel rendkívül kicsi annak valószínűsége, miszerint 2 különböző fájl azonos hash-kimenetet produkáljon, alkalmazható fájlok eredetiségének vizsgálatára is. Ebből következően a fájlok esetleges megváltozása utólag megállapítható, tehát integritásuk ellenőrizhető, sőt, 2 eltérő nevű, de azonos tartalmú fájl egyezősége szintén megállapítható.