Kako radi hash tablica?

Tražim objašnjenje kako radi heš tablica - na običnom engleskom jeziku za glupača poput mene!

Na primjer, znam da uzima ključ, izračunava hash (tražim objašnjenje kako), a zatim izvršava neki modul da radi gdje je u nizu, gdje je vrijednost pohranjena, ali gdje se moje znanje zaustavlja.

Može li netko pojasniti taj proces?

Uredi: Ne pitam konkretno kako se izračunavaju hasheve, već opći pregled funkcioniranja hash-tablice.

457
08 апр. Arec Barrwin postavljen 8. travnja 2009-04-08 18:48 '09 u 18:48 2009-04-08 18:48
@ 15 odgovora

Evo objašnjenja u laičkim terminima.

Pretpostavimo da želite popuniti knjižnicu knjigama, a ne samo da ih tamo gurate, ali želite da ih lako pronađete ponovo kada ih trebate.

Dakle, odlučite da ako osoba koja želi pročitati knjigu zna ime knjige i točan naziv za preuzimanje, to je sve što je potrebno. S ovim naslovom, osoba koja uz pomoć knjižničara treba brzo i jednostavno pronaći knjigu.

Pa kako to možete učiniti? Pa, očito, možete zadržati neki popis mjesta na koje stavljate svaku knjigu, ali onda imate isti problem kao i kod pretraživanja u knjižnici, morate izvršiti pretraživanje na popisu. Naravno, popis će biti manji i lakši za pretraživanje, ali ipak ne želite izvesti sekvencijalno pretraživanje s jednog kraja knjižnice (ili popisa) na drugi.

Želite nešto što će vam, s imenom knjige, odmah dati pravo mjesto, tako da sve što trebate učiniti je samo prošetati do desne police i pokupiti knjigu.

Ali kako se to može učiniti? Pa, s nekim promišljanjem kada popunite knjižnicu, i puno posla kad popunite knjižnicu.

Umjesto da počnete puniti knjižnicu s jednog kraja na drugi, razvit ćete malu pametnu metodu. Uzmete ime knjige, pokrenite je kroz mali računalni program koji izbacuje broj police i broj mjesta na ovoj polici. Ovdje stavite knjigu.

Ljepota ovog programa je da se kasnije, kada se osoba vrati da pročita knjigu, ponovno unesete naziv programa i vratite isti broj police i broj mjesta koji su vam izvorno dostavljeni, a to je mjesto gdje je knjiga

Program, kako ga drugi spominju, naziva se hash algoritam ili izračun hašiša i obično radi uzimanjem podataka koji su uneseni u njega (u ovom slučaju ime knjige) i izračunava broj iz njega.

Radi jednostavnosti, recimo da jednostavno pretvara svako slovo i znak u broj i sve ih sažima. Zapravo, sve je mnogo složenije, ali za sada ostavimo ga na miru.

Ljepota ovog algoritma je da, ako unosite isti ulaz iznova i iznova, svaki put će ispljunuti isti broj.

Ok, u osnovi, kako radi hash tablica?

Slijede tehničke stvari.

Prvo, postoji veličina sobe. Tipično, izlaz takvog hash algoritma je unutar određenog velikog broja, obično mnogo većeg od prostora koji imate u tablici. Na primjer, pretpostavimo da knjižnica ima mjesta za milijun knjiga. Rezultat izračuna hash-a može biti u rasponu od 0 do jedne milijarde, što je mnogo više.

Što ćemo onda? Mi koristimo takozvano modularno računanje, koje u osnovi kaže da ako računate na broj koji vam je potreban (tj. Na jednu milijardu), ali želite ostati u mnogo manjem opsegu, svaki put kada dostignete granicu ovog manji raspon iz kojeg ste započeli. 0, ali morate pratiti koliko ste daleko otišli.

Recimo da je izlaz hash algoritma u rasponu od 0 do 20, i dobivate vrijednost 17 iz određenog zaglavlja. Ako je veličina knjižnice samo 7 knjiga, brojite 1, 2, 3, 4, 5, 6, a kada dođete do broja 7, počinjete od nule. Budući da moramo brojati 17 puta, imamo 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, a konačni broj je 3. ,

Naravno, izračun modula se ne radi, već se vrši s podjelom i ostatkom. Ostatak dijeljenja 17 sa 7 je 3 (7 ide 2 puta do 17 do 14, a razlika između 17 i 14 je 3).

Dakle, stavite knjigu u broj 3.

To dovodi do sljedećeg problema. U sukobima. Budući da algoritam nema mogućnost postavljanja knjiga tako da točno popune knjižnicu (ili, ako želite, hash-tablicu), uvijek će izračunati broj koji je prethodno korišten. U knjižničkom smislu, kada dođete do police i sa brojem utora u koji želite staviti knjigu, već postoji knjiga.

Postoje različite metode za rukovanje sudarima, uključujući unos podataka u drugi izračun kako bi se dobilo drugo mjesto u tablici ( dvostruko heširanje ) ili samo kako bi se pronašlo mjesto u blizini onoga koji ste dobili (tj., Odmah pored prethodne knjige, uzimanje utora bilo je također dostupno kao linearno sondiranje ). To će značiti da ćete morati pretraživati ​​kada pokušate pronaći knjigu kasnije, ali još je bolje nego početi na jednom kraju knjižnice.

Konačno, u nekom trenutku možete staviti više knjiga u knjižnicu nego što knjižnica dopušta. Drugim riječima, trebate izgraditi veliku knjižnicu. Budući da je točno mjesto u knjižnici izračunato na temelju točne i trenutne veličine knjižnice, slijedi da ako promijenite veličinu knjižnice, možda ćete morati pronaći nova mjesta za sve knjige, budući da je izračun izvršen kako bi se pronašlo njihovo mjesto

Nadam se da je ovo objašnjenje bilo malo više zemaljsko nego kante i funkcije :)

874
08 апр. Odgovor dao Lasse Vågsæther Karlsen 08. travnja. 2009-04-08 19:33 '09 u 19:33 2009-04-08 19:33

Upotreba i žargon:

  1. Hash tablice se koriste za brzo pohranjivanje i dohvaćanje podataka (ili zapisa).
  2. Zapisi se pohranjuju u košare pomoću hash tipki
  3. Ključevi heširanja izračunavaju se primjenom hash algoritma na odabranu vrijednost (vrijednost ključa ) sadržanu u zapisu. Ova odabrana vrijednost treba biti zajednička svim zapisima.
  4. Svaka grupa može imati nekoliko zapisa koji su organizirani u određenom redoslijedu.

Primjer u stvarnom svijetu:

Hash Co. , osnovan 1803. godine, a ne posjeduje nikakvu računalnu tehnologiju, imao je ukupno 300 kartona za pohranjivanje detaljnih informacija (zapisa) za oko 30.000 svojih klijenata. Svaka mapa datoteka jasno je označena brojem klijenta, jedinstvenim brojem od 0 do 29 999.

Službenici za registraciju tog vremena morali su brzo pribaviti i zadržati evidenciju klijenata za radno osoblje. Osoblje je odlučilo da bi bilo učinkovitije koristiti metodu raspršivanja za pohranjivanje i dohvaćanje njihovih zapisa.

Za slanje zapisa klijenta, registratori moraju koristiti jedinstveni broj klijenta naveden u mapi. Pomoću ovog korisničkog broja, oni će modulirati hash-ključ do 300 kako bi identificirali ormar za pohranu u kojem se nalazi. Kada otvore ormar za pohranu, otkrit će da sadrži mnogo mapa, poredanih prema broju klijenta. Nakon što odredite ispravnu lokaciju, oni će je jednostavno umetnuti.

Da bi dobili zapis o kupcima, službenici su morali dobiti broj kupca na komadu papira. Koristeći ovaj jedinstveni broj klijenta ( hash ključ ), oni će ga modulirati na 300 da bi odredili koji indeks kartice sadrži mapu klijenata. Otvarajući kabinet, otkrivaju da u njemu ima mnogo mapa, poredanih po broju klijenta. Gledajući dokumente, brzo pronalaze mapu klijenta i izdvajaju je.

U našem stvarnom primjeru, naše kante su ormarići za dokumente, a naši zapisi su datoteke .


border=0

Važno je zapamtiti da računala (i njihovi algoritmi) rade s brojevima bolje nego s nizovima. Stoga je pristup velikom nizu pomoću indeksa mnogo brži od sekvencijalnog pristupa.

Kao što je Simon spomenuo, vjerujem da je vrlo važno da dio hasha pretvori veliki prostor (proizvoljne duljine, obično žice, itd.) I da ga prikaže u malom prostoru (poznate veličine, obično broj) za indeksiranje. Vrlo je važno zapamtiti!

Dakle, u gore navedenom primjeru, 30.000 mogućih kupaca može se usporediti s manjim prostorom.


border=0

Osnovna ideja ovoga je podijeliti cijeli skup podataka u segmente kako bi se ubrzalo stvarno pretraživanje, što obično traje dugo. U gornjem primjeru, svaka od 300 datoteka karata (statistički) sadržavat će oko 100 unosa. Pretraživanje (bez obzira na red) po 100 unosa je puno brže od pretraživanja za 30.000.

Možda ste primijetili da neki zapravo to čine. No, umjesto da razvijaju hash metodologiju za generiranje hash ključa, u većini slučajeva oni će jednostavno koristiti prvo slovo prezimena. Stoga, ako imate 26 ormarića za kartoteke, svaki sa slovima od A do Z, teoretski ste upravo segmentirali svoje podatke i poboljšali proces registracije i pretraživanja.

Nadam se da ovo pomaže,

Jeach!

94
08 апр. Odgovor dao Jeach dana 08. travnja 2009-04-08 20:20 '09 u 20:20 2009-04-08 20:20

Pokazalo se da je to prilično duboko polje teorije, ali je osnovni plan jednostavan.

U stvari, hash funkcija je jednostavno funkcija koja uzima stvari iz jednog prostora (na primjer, nizove proizvoljne duljine) i odgovara im s korisnim prostorom za indeksiranje (na primjer, nepotpisanim cijelim brojevima).

Ako imate samo mali broj stvari za hash, možete ih napustiti jednostavnim tumačenjem tih stvari kao cijelih brojeva, a završit ćete (na primjer, nizove od 4 bajta)

Međutim, obično imate mnogo više prostora. Ako je prostor stvari koje dopuštate kao ključeve veći od prostora stvari koje koristite za indeksiranje (vaš uint32 ili nešto drugo), ne možete imati jedinstvenu vrijednost za svaku od njih. Ako dva ili više hash hashes imaju isti rezultat, morat ćete u skladu s tim postupati s redundancijom (to se obično naziva sudar, i kako se s njime nosite, ili neće ovisiti o tome što koristite za hash).

To znači da ne želite imati isti rezultat, a vjerojatno ćete i jako voljeti da hash funkcija bude brza.

Balansiranje tih dviju svojstava (i nekoliko drugih) navelo je mnoge ljude da se pobrinu!

U praksi biste obično trebali moći pronaći funkciju za koju se zna da dobro funkcionira za vašu aplikaciju i koristiti je.

Sada da bi ovaj rad bio hash-tablica: Zamislite da vam nije stalo do korištenja memorije. Tada možete stvoriti niz dok god je indeksni skup (na primjer, uint32). Kada nešto dodate tablici, imate hash-ključ i pogledajte niz u tom indeksu. Ako tamo nema ničega, tamo stavite svoju vrijednost. Ako već postoji nešto, dodajte ovaj novi unos na popis stvari na toj adresi zajedno s dovoljno informacija (izvorni ključ ili nešto pametno) kako biste pronašli koji unos zaista pripada kojem ključu.

Dakle, kako dugo prolazite, svaki unos u hash-tablici (nizu) je ili prazan, ili sadrži jedan unos ili popis unosa. Ekstrakcija je jednostavno indeksiranje u niz i vraća vrijednost, ili slijedi popis vrijednosti i vraća ispravnu vrijednost.

Naravno, u praksi to obično ne možete učiniti, to je previše memorije. Dakle, radite sve na temelju oskudnog niza (gdje su jedini elementi oni koje zapravo koristite, sve ostalo je implicitno).

Postoje mnoge sheme i trikovi kako bi se ovaj posao učinio boljim, ali to su osnove.

64
08 апр. je odgovorio na simon 08. travnja. 2009-04-08 19:11 '09 u 19:11 2009-04-08 19:11

Postoji mnogo odgovora, ali nijedna od njih nije vrlo vizualna, a hash-tablice se mogu lako "kliknuti" prilikom prikazivanja.

Tablice su često implementirane kao nizovi povezanih popisa. Ako predstavimo tablicu u kojoj se pohranjuju imena ljudi, nakon nekoliko umetanja može se smjestiti u memoriju, kao što je prikazano u nastavku, gdje su () -zatvoreni brojevi hash vrijednosti teksta / imena.

 bucket# bucket content / linked list [0] --> "sue"(780) --> null [1] null [2] --> "fred"(42) --> "bill"(9282) --> "jane"(42) --> null [3] --> "mary"(73) --> null [4] null [5] --> "masayuki"(75) --> "sarwar"(105) --> null [6] --> "margaret"(2626) --> null [7] null [8] --> "bob"(308) --> null [9] null 

Nekoliko točaka:

  • svaki od niza unosa (indeksi [0] , [1] ...) naziva se kontejner i pokreće - eventualno prazan - povezani popis vrijednosti (drugim riječima, elementi, u ovom primjeru, imena ljudi)
  • svaka vrijednost (na primjer, "fred" s hash 42 ) povezana je s segmentom [hash % number_of_buckets] na primjer, 42 % 10 == [2] ; % je operator modula - ostatak kada je podijeljen s brojem segmenata
  • nekoliko vrijednosti podataka može se sudariti i povezati iz jednog segmenta, najčešće zato što se njihove heš vrijednosti sukobljavaju nakon operacije modula (na primjer, 42 % 10 == [2] i 9282 % 10 == [2] ), ali ponekad zbog da su hash vrijednosti jednake (na primjer, "fred" i "jane" prikazane gore s hash 42 )
    • većina hash-tablica rukuje sudarima - s nešto nižim performansama, ali bez funkcionalne konfuzije - uspoređujući punu vrijednost (ovdje tekst) ključa koji se pretražuje ili ubacuje sa svakim ključem koji se već nalazi u povezanom popisu u košari hash.

Kada povećavate veličinu hash-tablice, implementiranu kako je gore opisano, imaju tendenciju da sami mijenjaju svoju veličinu (tj. Stvaraju veći raspon segmenata, stvaraju nove / ažurirane povezane liste, brišu stari niz) kako bi sačuvali omjer elementa-segmenta (ili preuzimanje). faktor) negdje u rasponu od 0,5 do 1,0. Hans daje stvarnu formulu u komentarima ispod, ali za približne vrijednosti: s faktorom opterećenja 1 i hash funkcijom kriptografske snage 1 / e (~ 36,8%) spremnici će biti prazni, drugi 1 / e (~ 36,8%) ) imaju jedan element, 1 / (2e) ili ~ 18.4% dva elementa, 1 / (3! e) oko 6.1% od tri elementa, 1 / (4! e) ili ~ 1.5% od četiri elementa, 1 / (5! E) s oko ~ .3% ima pet, itd. - Prosječna duljina lanca ne-praznih segmenata iznosi ~ 1,58 bez obzira na to koliko je elemenata u tablici (tj. Ima li 100 elemenata i 100 segmenata ili 100 milijuna elemenata) i 100 milijuna blokova, pa kažemo da pretraživanje / insert / erase je O (1) operacija s konstantnim vremenom.

(Bilješke: ne sve hash tablice koriste povezane liste, ali većina ih se koristi za opću namjenu, budući da zatvoreno raspršivanje (drugim riječima, otvoreno adresiranje) - posebno s podržanim operacijama brisanja - ima manje stabilne karakteristike izvedbe s ključevima sklonim sudarima / hash funkcije).

Nekoliko riječi o hash funkcijama

Glavni zadatak, izveden u najgorem slučaju za minimiziranje sudara heš funkcije, je učinkovito nasumično dodijeliti ključeve oko blokova hash tablica, uvijek generirajući istu hash vrijednost za isti ključ. Čak i jedan bit, koji se mijenja bilo gdje u ključu, idealno - slučajno - okreće oko polovice bitova u dobivenoj hash vrijednosti.

Obično se organizira s matematikom koja je previše komplicirana za mene. Spomenut ću jedan lak za razumjeti način - ne skalabilan ili prikladan za predmemoriju, ali elegantan (npr. Šifriranje pomoću jednokratne tipkovnice!) - jer mislim da pomaže vratiti gore navedene željene kvalitete. Pretpostavimo da ste raspršili 64-bitni double - možete stvoriti 8 tablica, od kojih svaka sadrži 256 slučajnih brojeva (tj. size_t random[8][256] ), a zatim koristiti svaki 8-bitni / 1-bajtni fragment predstavljanja double memorija za indeksiranje u drugu tablicu, XOR slučajne brojeve koje tražite. Ovim pristupom lako je vidjeti da mijenjanje dijela double rezultata bilo gdje dovodi do traženja drugog slučajnog broja u jednoj od tablica i potpuno nekorelirane konačne vrijednosti.

Međutim, hash funkcije mnogih knjižnica preskaču cijele brojeve bez promjena, što je u najgorem slučaju iznimno sklono sudarima, ali se nadaju da će se u prilično uobičajenom slučaju cjelobrojnih ključeva koji imaju tendenciju povećanja, pretvoriti u uzastopne segmente, ostavljajući manje više praznih od 36,8% slučajnog heširanja, te stoga ima manje sudara i manje dugačkih povezanih lista sudarajućih elemenata nego što se postiže slučajnim mapiranjem. Također je sjajno uštedjeti vrijeme potrebno za stvaranje jakog hasha. Kada tipke ne rastu, nadaju se da će biti prilično slučajne, neće im trebati jaka hash funkcija kako bi potpuno rasporedili svoj položaj u segmentima.

Pa, bilo je manje zabavno i teže od objašnjavanja tablice, ali nadam se da će to pomoći nekome ...

37
01 июня '15 в 9:59 2015-06-01 09:59 odgovor je dao Tony Delroy 1. lipnja '15. u 9:59 2015-06-01 09:59

Vi dečki to vrlo detaljno objašnjavate u cijelosti, ali nedostaje nekoliko stvari. Hash-tablica je samo niz. Niz će sadržavati nešto u svakom utoru. Minimalno, spremite vrijednost hashvalue ili njezine vrijednosti u ovo mjesto. Osim toga, također možete spremiti povezani / ulančani popis vrijednosti na koje se naišlo u ovom utoru ili možete koristiti metodu otvorenog adresiranja. Također možete spremiti pokazivač ili pokazivače na druge podatke koje želite izvući iz ovog mjesta.

Važno je napomenuti da sama hashvalue obično ne označava mjesto u koje se vrijednost uklapa. Например, значение hashval может быть отрицательным целым значением. Очевидно, что отрицательное число не может указывать на местоположение массива. Кроме того, значения хеширования будут во много раз больше, чем доступные слоты. Таким образом, другой расчет должен выполняться самим хэш-таблицей, чтобы выяснить, в каком слоте должно идти значение. Это выполняется с помощью математической операции модуля, например:

 uint slotIndex = hashValue % hashTableSize;