Jednφm z kritΘriφ hodnocenφ dob°e fungujφcφho databßzovΘho systΘmu je rychlost p°φstupu k po₧adovan²m dat∙m podle hodnoty klφΦe K, tj. vybranΘho atributu (nebo skupiny atribut∙). Tento problΘm se nejΦast∞ji °eÜφ indexovßnφm. Indexovß struktura zalo₧enß na B-stromech nabφzφ takov² rychl² p°φstup. Pro nalezenφ prvnφho zßznamu s hodnotou klφΦe K staΦφ p°eΦφst n∞kolik strßnek z disku, v zßvislosti na hloubce B-stromu.

NejlepÜφ by ovÜem bylo p°eΦφst strßnku pouze jednu, tj. mφt k dispozici tzv. p°φm² p°φstup. Mo₧nß, ₧e by staΦilo vzφt hodnotu klφΦe tabulky (zßznamu) a chßpat ji p°φmo jako adresu na disku. Tato mo₧nost je ovÜem v praxi t∞₧ko uskuteΦnitelnß. Nap°. je-li klφΦem RODN╔_╚═SLO, pak pro relaci ZAM╠STNANEC obsahujφcφ data o 1000 zam∞stnancφch bychom pot°ebovali obrovsk² diskov² prostor (pro nositele potencionßln∞ vÜech rodn²ch Φφsel), kter² by ale byl zapln∞n pouze na 1000 mφstech.

Mnohem lepÜφ ideou je nalΘzt funkci, kterß transformuje hodnotu klφΦe na adresu. Ji₧ ze st°ednφ Ükoly znßme, ₧e jeden ze zp∙sob∙, jak zadat funkci, je tabulka. Tak toto nenφ ten p°φpad. Tφm bychom se vlastn∞ zase dostali k indexovßnφ (prvnφ ·rove≥ indexu je prßv∞ takovou tabulkou). Tak₧e spφÜe p∙jde o funkci vyjßd°enou n∞jak²m p°edpisem, algoritmem.

Ji₧ dßvno p°ed databßzemi pou₧φvali tuto techniku tv∙rci operaΦnφch systΘm∙, p°ekladaΦ∙ apod. Jde o tzv. haÜovßnφ. ProΦ zrovna haÜovßnφ? HaÜovßnφ jako haÜe. Jde o poΦeÜt∞nφ angl. slova hashing. SkuteΦn∞, haÜovßnφ je na mφst∞, nebo¥ funkce realizujφcφ haÜovßnφ obΦas p°ipomφnajφ kuchy≥skou techniku ôrozsekßnφö n∞Φeho na haÜi. Pro mladÜφ informatiky p°ipomφnßm, ₧e podle dßvnΘ normy pojm∙ v²poΦetnφ techniky se mφsto haÜovßnφ °φkalo metoda rozpt²len²ch tabulek. NejstarÜφ Φlßnek o haÜovßnφ znßm z roku 1968 (J. Morris, Scatter Storage Techniques, CACM, 11, 1), pro zßjemce lze doporuΦit nahlΘdnout do dφla D. Knutha ôArt of Computer Programmingö z r. 1973.

O co vÜak jde. P°edstavme si adresov² prostor velikosti {0,1,...,M-1}. Ka₧dΘ (relativnφ) adrese odpovφdß mφsto v pam∞ti, do kterΘho lze ulo₧it hodnotu n∞jakΘho klφΦe K (nap°. RODN╔_╚═SLO). TΘto datovΘ struktu°e se tradiΦn∞ °φkß haÜovacφ tabulka. P°edpoklßdan² poΦet hodnot klφΦe je N, kde M³ N. Obvykle N = 0,8M, tj. poΦet mφst haÜovacφ tabulky je o n∞co v∞tÜφ ne₧ mno₧ina hodnot klφΦe K, kterΘ do n∞j chceme vlo₧it.

HaÜovacφ funkce je v²poΦetn∞ jednoduch² p°edpis, kter²m transformujeme hodnoty klφΦe do relativnφch adres adresovΘho prostoru (absolutnφ adresy se spoΦtou snadno pouhou lineßrnφ transformacφ). Jin²mi slovy °eΦeno pomocφ haÜovacφ funkce se ôstrefujemeö do haÜovacφ tabulky a umis¥ujeme hodnoty klφΦ∙ na odpovφdajφcφ mφsta. Bylo by iluzornφ se domnφvat, ₧e funkci lze nalΘzt tak, ₧e dv∞ma r∙zn²m hodnotßm klφΦe odpovφdajφ dv∞ r∙znΘ adresy, tj. ₧e funkce bude prostß. Vznikajφ kolize, tj. n∞kolik hodnot klφΦ∙ mß b²t umφst∞no na jednom mφst∞. Kolize se °eÜφ obvykle tzv. otev°en²m adresovßnφm, tj. kolidujφcφ hodnota klφΦe se umφstφ na nejbli₧Üφ volnΘ mφsto s vyÜÜφ adresou, p°φpadn∞ se zaΦne od zaΦßtku haÜovacφ tabulky. Toto tzv. rehaÜovßnφ lze provßd∞t i jin²m, rafinovan∞jÜφm zp∙sobem, nap°. dalÜφ haÜovacφ funkcφ (dvojitΘ haÜovßnφ) nebo, podobn∞ jako u indexsekvenΦnφ organizace, pomocφ oblasti p°eteΦenφ, p°iΦem₧ kolidujφcφ zßznamy jsou z°et∞zeny pomocφ ukazatel∙.

Hledßnφ v takovΘto datovΘ struktu°e je podobnΘ vklßdßnφ prvk∙ do struktury. K hodnot∞ klφΦe k danΘ haÜovacφ funkci h spoΦteme hodnotu h(k) interpretovanou jako relativnφ adresu do haÜovacφ tabulky T. Je-li na mφst∞ h(k) v T klφΦ k, je vÜe v po°ßdku, nenφ-li, je nutno postupovat v souladu se strategiφ, jak byly °eÜeny kolize. Nap°. p°i otev°enΘm adresovßnφ se od danΘho mφsta prohledßvß T sekvenΦn∞. Co kdy₧ ale k v T nenφ? Pak se samoz°ejm∞ hledß do prvnφho volnΘ mφsta v T. Tφm je zaruΦeno, ₧e k se v T nenachßzφ.

Lze tuÜit, ₧e kvalita haÜovßnφ je siln∞ zßvislß na vlastnostech haÜovacφ funkce. KritΘriem vhodnosti je nap°. pr∙m∞rnß dΘlka °et∞zce kolidujφcφch prvk∙. HaÜovacφch funkcφ existuje mnoho, vΦetn∞ matematickΘ anal²zy jejich vlastnostφ. Jednou z nejefektivn∞jÜφch haÜovacφch funkcφ je h = k mod M' (zbytek po d∞lenφ M', kde M' je nejbli₧Üφ prvoΦφslo menÜφ ne₧ M a k je Φφseln² klφΦ). Z°ejm∞ platφ 0£ h(k) £ M'-1£ M.

Je-li h prostß funkce, hovo°φme o perfektnφm haÜovßnφ, je-li navφc M = N, jde o minimßlnφ perfektnφ haÜovßnφ (obojφ se v praxi vyskytuje pom∞rn∞ z°φdka). Perfektnφ haÜovßnφ se n∞kdy takΘ naz²vß p°φpad, kdy haÜovßnφ vede ke konstantnφmu poΦtu p°φstup∙ na disk, hledßme-li zßznam s dan²m klφΦem.

Jin²m problΘmem je, ₧e ne ka₧dß mno₧ina prvk∙ je okam₧it∞ p°ipravena k haÜovßnφ. Nap°. hodnoty atributu ADRESA jsou dlouhΘ °et∞zce znak∙, kterΘ je nutnΘ nejprve upravit. To se obvykle d∞lß metodou sklßdßnφ (folding). ╪et∞zec se rozd∞lφ na skupiny po 4 znacφch, ty se chßpou jako °et∞zec nul a jedniΦek. Ze vÜech takto vznikl²ch °et∞zc∙ se vytvo°φ pomocφ aplikace operßtoru XOR (v²luΦnΘ nebo) 32bitovΘ Φφslo. Sklßdßnφ takΘ zabezpeΦφ, ₧e p∙vodnφ, mo₧nß nerovnom∞rnΘ rozlo₧enφ hodnot klφΦe, se bude po transformaci blφ₧it rovnom∞rnΘmu. DalÜφ ônßhodnostö vnese do metody pou₧itφ funkce h, tj. cφlem je, aby se haÜovacφ tabulka zapl≥ovala co nejrovnom∞rn∞ji.

Tabulka samotn²ch hodnot klφΦ∙ nenφ p°φliÜ u₧iteΦnß. Metodu lze snadno vyu₧φt pro uklßdßnφ zßznam∙ s klφΦem K Φi °ßdk∙ tabulky relaΦnφ databßze. Pozor, zatφm vÜak Ülo u datovou strukturu ve vnit°nφ pam∞ti, tj. v danΘ podob∞ je metoda pro databßze nepou₧itelnß. I kdy₧ ... . Existujφ techniky pro zpracovßn spojenφ relacφ, kdy se jedna z nich celß haÜuje do vnit°nφ pam∞ti (viz p°φÜtφ pokraΦovßnφ DatabßzovΘ abecedy).

Implementace p°φmΘho p°φstupu v diskovΘm prost°edφ znamenß realizovat haÜovßnφ v adresovΘm prostoru strßnek. To lze chßpat bu∩ tak, ₧e interval <0,M-1> reprezentuje adresy strßnek a hodnoty haÜovacφ funkce jsou celß Φφsla z tohoto intervalu. Pak vlastn∞ vÜechny kolidujφcφ zßznamy padajφ do jednΘ strßnky a v p°φpad∞ p°eteΦenφ do nßsledujφcφch.

Jinou mo₧nostφ je urΦit p°φmo i relativnφ pozici zßznamu ve strßnce. Samoz°ejm∞ zßznamy musφ b²t pevnΘ dΘlky. Pak haÜovacφ funkce h₁ m∙₧e pro danΘ klφΦe dßvat hodnoty z intervalu <0, 1) a v²slednß funkce h m∙₧e b²t definovßna jako

h(x) = ë M* b * h₁(x) û

kde b je blokovacφ faktor, tj. maximßlnφ poΦet zßznam∙, kterΘ se vejdou do strßnky, a ë x û dßvß celou Φßst x. ╪eÜenφ kolizφ je °φzeno strategiφ ôumφstit zßznam, kter² koliduje, pokud mo₧no na tΘ₧e strßnce, kam skuteΦn∞ pat°φö. Tφmto zp∙sobem obdr₧φme datovou strukturu zvanou obvykle soubor s p°φm²m p°φstupem. Obvykle u₧ nenφ na mφst∞ hovo°it o haÜovacφ tabulce. T je nynφ prostor na disku vybran² pro ulo₧enφ souboru Φi relace. Na obr. 1 je ukßzßna typickß situace s kolizφ, kdy hodnota klφΦe 45 koliduje s hodnotou 97 a rehaÜovßnφm se dostßvß na mφsto 73.

Definujme nynφ faktor napln∞nφ l prostoru T jako N/M. Intuice °φkß, ₧e bude-li nφzk² faktor l (celΘho prostoru), tj. prostor pro zßznamy bude dostateΦn∞ velik², obdr₧φme hledan² zßznam pravd∞podobn∞ na jeden p°φstup. Naopak, se vzr∙stajφcφm l by se m∞la prodlu₧ovat dΘlka °et∞zce zßznam∙, kterΘ kolidujφ v danΘm mφst∞.

h(45) = 70

str. 0 0-15

str. 1 16-31

str. 2 32-47

str. 3 48-63

str. 4 64-79

str. 6 80-95

Obr. 1 P°φklad kolize p°i vstupu hodnoty klφΦe 45

Budeme p°edpoklßdat, ₧e hodnoty klφΦe jsou nahodilΘ a vzßjemn∞ nezßvislΘ. Faktor napln∞nφ lze tΘ₧ interpretovat jako pravd∞podobnost, ₧e mφsto danΘ hodnotou h(k), kde k je klφΦ, je obsazenΘ. Lze dokßzat jednoduchΘ, ale u₧iteΦnΘ tvrzenφ.

• Je-li l je faktor napln∞nφ adresovΘho prostoru p°i haÜovßnφ s lineßrnφm prohledßvßnφm, pak pro p°edpoklßdanou dΘlka °et∞zce kolizφ L platφ

E(L) = 1/(1-l )

Nap°. pro l = 0,5, vychßzφ E(L) = 2, pro l = 0,9, pak E(L) = 10.

Pro soubor ulo₧en² ve strßnkßch je rozhodujφcφ spφÜe faktor napln∞nφ strßnky a poΦet zßznam∙ ve strßnce. D∙le₧itΘ je, jak jsou °etezce kolizφ rozlo₧eny do strßnek. M∞°enφ nap°. ukazujφ, ₧e p°i faktoru napln∞nφ strßnky 0,8 a b = 40 je pravd∞podobnost Φtenφ dalÜφ strßnky 0,01 a to je p°ijateln² v²sledek.

Proto₧e pou₧it² pam∞¥ov² prostor z∙stßvß u haÜovßnφ b∞hem aktualizacφ nem∞nn² (hovo°φ se tΘ₧ o statickΘm haÜovßnφ), zhorÜuje se pr∙m∞rn² Φas p°φstupu k jednomu zßznamu (vinou nap°. dΘlky °et∞zce v oblasti p°eteΦenφ nebo lineßrnφm prohledßvßnφm adresovΘho prostoru) na ekvivalent sekvenΦnφho prohledßvßnφ souboru. ProblΘm se °eÜφ reorganizacφ kompletnφ struktury, co₧ t∞₧ko obstojφ nap°. v databßzov²ch systΘmech Φi p°i vφcenßsobnΘm p°φstupu k soubor∙m. Zd∙razn∞me takΘ, ₧e haÜovßnφ je vhodnΘ, kdy₧ K je jednoznaΦn² klφΦ (v relaΦnφm modelu dat jde nap°. o primßrnφ klφΦ relace). Modifikace haÜovßnφ pro libovoln² klφΦ je vÜak mo₧nß.

Jinou nev²hodou statickΘho haÜovßnφ je, ₧e takto organizovan² soubor nemß ₧ßdnΘ uspo°ßdßnφ, co₧ sni₧uje je ho pou₧itelnost v n∞kter²ch typech dotaz∙.

Existujφ dynamickΘ metody, kterΘ °eÜφ problΘm p°φstupu tak, ₧e je v₧dy zachovßn konstantnφ poΦet p°φstup∙ p°i hledßnφ podle hodnoty klφΦe. Dßle existujφ i takovΘ metody, kterΘ haÜujφ zp∙sobem, kter² zachovßvß uspo°ßdßnφ.