![]() ![]() |
ARCHIV |
||||||||||||||||||||
![]() ![]() ![]() ![]() ![]() ![]() |
|
Index (Hashovací klíč) | Hodnota |
---|---|
0 | 16 |
1 | 9 |
2 | 42 |
3 | 11 |
4 | 12 |
5 | 61 |
6 | 6 |
Je jistě vidět, že vyhledávat v hashovací tabulce není nic složitého. Samozřejmě mnohem lepší by bylo si na vyhledávání napsat jednoduchou funkci, která by vracela true nebo false. V této ukázce však šlo pouze o pochopení, jak hashování funguje.
Vraťme se ješte na chvíli k předešlému příkladu. Naše hashovací funkce vracela zbytek po dělení osmi, což znamená, že hashovací klíč byl vždy v intervalu <0, 7>. To může být docela problém, neboť rozsah klíčů není velký a může proto velmi snadno dojít ke kolizi. Kolizí rozumíme to, jestliže dvě hodnoty získají stejný hashovací klíč - například čísla 27 a 11 mají obě hashovací klíč roven 3 (u naší hashovací funkce). To je problém, neboť v našem poli je u hashovacího klíče vždy jen jedno místo. Proto je snad již zcela zřejmé, že předchozí příklad neměl reálné využití. Jak tedy kolize řešit?
Asi nejlepším způsobem by bylo navrhnout hashovací funkci tak, aby každé hodnotě přiřadila různý klíč. Toho by šlo dosáhnout tak, že by se hashovací funkce chovala náhodně. V tom je však skryt další problém. Hashovací funkce musí být navržena tak, aby vždy pro danou hodnotu vypočítala stejný hashovací klíč - proto se hashovací funkce nemůže chovat náhodně. Kolize lze tedy řešit například separátním řetězením.
Princip separátního řetězení je takový, že každé hodnotě hashovacího klíče je přiřazena datová struktura seznam, do kterého se ukládají hodnoty. Jinak řečeno, hodnoty se stejným hashovacím klíčem se ukladájí do stejného seznamu. Tím se však zvyšuje časová složitost vyhledání hodnoty v hashovací tabulce. Časová složitost je úměrná délce seznamu, který je asociován s patřičným hashovacím klíčem. V absolutně nejhorším případě by se mohlo stát, že by se všechny hodnoty hashovaly na stejný hashovací klíč, tudíž by se ukládaly do stejného seznamu. V tomto případě by pak časová složitost na vyhledání hodnoty byla přímo děsivá. Je tedy nutné dobře navrhnout hashovací funkci, aby ke kolizím docházelo co možná nejméně často.
Ukázku, jakým způsobem je možno separátní řetězení naimplementovat, naleznete zde. Je to trochu delší kód, proto jsem ho zde dal ke stažení. Program slouží k uložení různě dlouhých řetězců do hashovací tabulky. Pokud si kód budete chtít vylepšit, můžete si několik řetězců uložit do textového souboru, ty pak v programu načíst a uložit do hashovací tabulky. Pak je můžete zkusit vyhledávat. Udělal jsem hashovací tabulku na 50 hashovacích klíčů, není však problém tuto tabulku zvětšit - stačí v kódu změnit hodnotu konstanty n. Každý prvek hashovací tabulky představuje datovou strukturu seznam, čili při výskytu stejných hashovacích klíčů se data ukládájí do stejného seznamu. Ještě podotýkám, že jsem implementoval pouze metody pro přidávání a hledaní prvků, metoda, která bude prvky mazat, není nikterak složitá.
Jistě jste se někdy setkali například s pojmem CRC (Cyclic Redundancy Check, cyklický redundantní součet). Není to nic jiného, než hashovací funkce, která se používá při přenosu nebo při ukládání dat, čili slouží k detekci chyb v datech. To, jak přesně CRC funguje, je myslím zbytečné psát, neboť o tom se určitě najde článků dost. Mezi další hashovací funkce patří například MD-5 nebo SHA-1.
Příspívat do diskuze mohou pouze registrovaní uživatelé. |
28.11.2018 23:56 /František Kučera
Prosincový sraz spolku OpenAlt se koná ve středu 5.12.2018 od 16:00 na adrese Zikova 1903/4, Praha 6. Tentokrát navštívíme organizaci CESNET. Na programu jsou dvě přednášky: Distribuované úložiště Ceph (Michal Strnad) a Plně šifrovaný disk na moderním systému (Ondřej Caletka). Následně se přesuneme do některé z nedalekých restaurací, kde budeme pokračovat v diskusi.
Komentářů: 1
12.11.2018 21:28 /Redakce Linuxsoft.cz
22. listopadu 2018 se koná v Praze na Karlově náměstí již pátý ročník konference s tématem Datová centra pro business, která nabídne odpovědi na aktuální a často řešené otázky: Jaké jsou aktuální trendy v oblasti datových center a jak je optimálně využít pro vlastní prospěch? Jak si zajistit odpovídající služby datových center? Podle jakých kritérií vybírat dodavatele služeb? Jak volit vhodné součásti infrastruktury při budování či rozšiřování vlastního datového centra? Jak efektivně datové centrum spravovat? Jak co nejlépe eliminovat možná rizika? apod. Příznivci LinuxSoftu mohou při registraci uplatnit kód LIN350, který jim přinese zvýhodněné vstupné s 50% slevou.
Přidat komentář
6.11.2018 2:04 /František Kučera
Říjnový pražský sraz spolku OpenAlt se koná v listopadu – již tento čtvrtek – 8. 11. 2018 od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Tentokrát bez oficiální přednášky, ale zato s dobrým jídlem a pivem – volná diskuse na téma umění a technologie, IoT, CNC, svobodný software, hardware a další hračky.
Přidat komentář
4.10.2018 21:30 /Ondřej Čečák
LinuxDays 2018 již tento víkend, registrace je otevřená.
Přidat komentář
18.9.2018 23:30 /František Kučera
Zářijový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 20. 9. 2018 od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Tentokrát bez oficiální přednášky, ale zato s dobrým jídlem a pivem – volná diskuse na téma IoT, CNC, svobodný software, hardware a další hračky.
Přidat komentář
9.9.2018 14:15 /Redakce Linuxsoft.cz
20.9.2018 proběhne v pražském Kongresovém centru Vavruška konference Mobilní řešení pro business.
Návštěvníci si vyslechnou mimo jiné přednášky na témata: Nejdůležitější aktuální trendy v oblasti mobilních technologií, správa a zabezpečení mobilních zařízení ve firmách, jak mobilně přistupovat k informačnímu systému firmy, kdy se vyplatí používat odolná mobilní zařízení nebo jak zabezpečit mobilní komunikaci.
Přidat komentář
12.8.2018 16:58 /František Kučera
Srpnový pražský sraz spolku OpenAlt se koná ve čtvrtek – 16. 8. 2018 od 19:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát jsou tématem srazu databáze prezentaci svého projektu si pro nás připravil Standa Dzik. Dále bude prostor, abychom probrali nápady na využití IoT a sítě The Things Network, případně další témata.
Přidat komentář
16.7.2018 1:05 /František Kučera
Červencový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 19. 7. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát bude přednáška na téma: automatizační nástroj Ansible, kterou si připravil Martin Vicián.
Přidat komentář
31.7.2023 14:13 /
Linda Graham
iPhone Services
30.11.2022 9:32 /
Kyle McDermott
Hosting download unavailable
13.12.2018 10:57 /
Jan Mareš
Re: zavináč
2.12.2018 23:56 /
František Kučera
Sraz
5.10.2018 17:12 /
Jakub Kuljovsky
Re: Jaký kurz a software by jste doporučili pro začínajcího kodéra?