Wat ass den Ënnerscheed tëscht engem Array an engem Hashtabell an enger Programméierungssprooch?


beäntweren 1:

Hash Dëscher benotzen Arrays. Arrays hunn eng wichteg Eegeschafte fir Hashing: Dir kënnt op all Element a konstanter Zäit zougräifen wann Dir säin Index wësst.

Dir kënnt Arrays fir Eimer benotzen. Ugeholl Dir wëllt zielen wéivill Buschtawen an Text sinn, zum Beispill fir eppes wéi Morse Code ze designen. Dir erstellt en Array mat 26 Entréen (fir dat einfach réimescht Alfabet ouni Akzent). Wann Dir e Bréif gesitt, berechent den Index a gitt op dës Entrée an der Array.

Hash Dëscher verlängeren dëst fir d'Schlësselen vun all Längt. Dir berechent en Hash vun de Schlëssel a gitt op deen Index. De Problem ass wann verschidde Schlësselen dee selwechte Hash hunn. Et gi verschidde Weeër fir et ze këmmeren, e puer vun deenen den Zweck vum Hash Hash ongëlteg sinn (awer si sinn einfach ze implementéieren). E puer vun hinnen erhalen net de konstante Zäiteigendom, op d'mannst am Duerchschnëtt.

Déi bescht Saach déi ech gesinn hunn ass den add-the-hash rehash, an deem Gonnet a Munroe bewisen hunn eng Moyenne vu méi wéi 4 Hits mat engem 50% Lastfaktor, onofhängeg vun der Gréisst vum Hashtabell. Dëst erfuerdert awer d'Benotzung vu Primeuren, an dëst mécht d'Ëmsetzung schwéier. Dir musst d'Primernummeren iergendwéi fannen. Glécklecherweis, Hashtabele ginn net sou grouss datt dëst lächerlech gëtt.