Diskusia – Haš tabuľka

K tomuto tématu jsem se již při psaní zdejších algoritmů nedostal, jsem moc rád, že jsi to zde tak hezky vysvětlil

Díky, snad to někomu bude k užitku

Navazující lineární seznam je jen jednou z několika možností, jak se vypořádat s kolizemi. Často se podle druhé hashovací funkce vyhledává náhradní volná pozice v původním poli. Někdy dokonce i tak, že se původní klíč přesune na novou pozici.

Díky za připomínku, kdyžtak tam o téhle možnosti něco dopíšu

Možná by toho bylo na další díl

Zvládl bys i AVL a B-stromy? Nejsou sice tak výkonné, ale zato jsou udržovány seřazené.

Dopsal jsem tam pár odstavců o těch dalších technikách řešení kolizí, už se to publikuje. No dívám se, že o AVL stromech už tady nějaký článek je, a B-stromy bych napsat mohl, ale musel bych si je trošku zopakovat ^^

Já jsem tenkrát skončil u binárních stromů, ty by měly být dobře popsané. Co se týče AVL, mám dojem, že je to jen informační článek, není tam popis rotací atd.

Proč jsi použil stejný key a value? Následně se článek tváří (hlavně ilustrace), jako že seznamy jsou obyčejná pole obsahující pouze hodnoty value a jediný způsob, jak se dostat ke správné hodnotě v případě kolize, je používat stejný key a value. V takovém případě by ztrácela celá hash tabulka smysl. Věřím, že pokud už člověk něco o hash tabulkách ví, článek mu bude dávat smysl, ale třeba já jako neznalec jsem málem celé hash tabulky zavrhnul. To by byla škoda

Možná bych měl příspěvek k tématu i když je staršího data. Co takhle používat pro klíčování princip Bergrových tabulek? Můžete si něco málo přečíst o této problematice zde : Bergrovy tabulky - je to zaměřeno na obecné užítí spíš v rámci kryptografie, ale pro účely vyhledávání - respektive hashování ve všech podobách je to myslím perspektivní.

Bergrovy tabulky nemají problém s jakkoliv velkým číslem které zvládne stroj (hovořím o algoritmu). Proto je vhodná indexace zejména na první dva až tři znaky - bez problémů 256 znaků, ale prakticky stačí méně a lepší je lichý počet.

Tabulky pracují s variacemi dvojic znaků kterým přidělí index (1 znak, respektive číslo). To by mohl být základní index pro řádek seznamu kde by už mohla (měla) být druhým indexem vlastní dvojice (2. rozměr tabulky). Třetím rozměrem by mohl být LEN(výraz). Další dva rozměry získáme jako INT(součin hodnot charů/-příklad 32) a také jako modulo stejného znaku 32 (mezera). Teprve potom by musel nastoupit klasický seznam.

Chtěl jsem o podobných věcech psát ale nějak s toho sešlo. Týká se to mnoha témat - tedy prakticky asi všech. Je to do jisté míry know-how a tak bych chtěl jen zavdat námět k přemýšlení. Použil jsem bergrovy tabulky [BT] v šabloně pro Open Office a Libre Office - jinde fungovat nebude odkaz Odstavcová šifra