Jak funguje vyhledávání v hash tabulce?

[Franc]

ahoj,

mel bych dotaz, princip hash tabulky chapu, jedna se o par klic - hodnota, cilem je relativne dlouho hodnotu popsat co nejkratsim klicem a idealne nekoliznim coz nam zajisti kvalitni hash funkce.

OK, takze mame cosi jako asocitivni pole klic - hodnota, jde mi o dotaz jak to fakticky ten pocitac udela, kdyz po nem chci data s hashem napr. 0e35fd (rekneme, ze mam pole o 1000 klicich), hash tabulky jsou rychle, takze to urcite nebude tak, ze by pocitac projel cele pole dokud by nenarazil na muj klic pozadovany klic.

Jinak receno jak dokaze tak rychle vyhledat muj klic, funguje klic jako index v poli? nebo je to pole nejakych struktur?

Snad jsem se vymacknul srozumitelne. Francek

[Reklama]

[tt]

klic je ve finale vypocitan jako cislo a to slouzi jako index do nejakeho interniho pole, takze je to rychle jak blesk

[tt]

viz. treba
http://www.perl.com/pub/2002/10/01/hashes.html

Here's the hashing function used in Perl 5.005:

Kód: [Vybrat]

  # Return the hashed value of a string: $hash = perlhash("key")
  # (Defined by the PERL_HASH macro in hv.h)
  sub perlhash
  {
      $hash = 0;
      foreach (split //, shift) {
          $hash = $hash*33 + ord($_);
      }
      return $hash;
  }


[D S]

Kdysi jsem to studoval, pro speciální úlohu se dá hash tabulka navrhnout třeba i rychlejší, koukni se na java zrojáky k HashMap, je to celkem jednoduchý, řekne ti to všechno.

[Franc]

Diky, tusil jsem to, ze to bude jako klice, coz znamena v nejhosim pripade kdyz to clovek udela uplne tupe, ze
staticke pole napr. v C o 1000 prvcich ma indexy 0 .. 999, takze clovek musi zajistit aby hash vracel cisla v mantinelech pole, coz lze snadno zajistit, horsi je to s faktem, ze musim dopredu vedet jak velke pole potrebuji, ale to lze zase obejit nejakym dynamickym a aritmetikou pointru si spocitat kam presne sahnout podle hashe.

Dikt Francek

[Reklama]

[vyvojar]

Můžeš mít pole např. jenom o 500 prvních a používat operátor modulu. Pak v každým prvku pole budeš mít pointer na nějaký zřetězený seznam, kde budeš procházet ty prvky, co tam jsou a strcmpovat je s hledaným.

[Kit]

Dělá se to dynamicky. Vždy, když množství dat překročí určitou mez, alokuje se pole dvojnásobné velikosti, data se přelijí a původní pole se uvolní.

[Waseihou]

Hashovací tabulka funguje v nejjednodušší variantě takto:

Máme velké pole které z velké části bude nezaplněné, velikost toho pole by ideálně měla být prvočíslo. Pro hodnotu kterou lze uložit do pole lze vypočítat hash, pokud by to bylo pole intů tak třeba by to bylo x%n kde x je hodnota a n prvočíslo, často se to ale počítá z řetězce, třeba se furt přičítá ten znak a dělá se z toho modulo.

Pak se výsledek toho hashe vezme jako pozice v poli, tam se začne hledat první prázdné místo, a do něj se to uloží. Při prohledávání se opět najde pozice v poli a pak se normálně prohledává jako při sekvenčním hledání. Někdy se pro pozici dalšího prvku používá sekundární hashovací funkce, sice je to výpočet navíc, ale občas to zabrání degeneraci tabulky.

Není dobré aby tabulka byla příliš zaplněná, pokud se pole zaplní z 1/2, tak se velikost zdvojnásobí a všechny hodnoty se přehashují (to je časově náročné). Při poklesu velikosti pod 1/4 se může pole zmenšit na polovinu, pokud je užitečné získat pamět.

[Waseihou]

Jinak pokud jde hash použít, dá se tím efektivně zrychlit hledání, například ta tabulka může být pole ukazatelů na kořeny binárních vyhledávacích stromů, skiplistů či jen obyčejných polý, ty mohou být třeba seřazené, a nebo vždy poslední nalezenou hodnotu dát na začátek (často hledané hodnoty se tak časem dostanou na první pozice v poli a jsou nalezeny rychleji), atp.