Hash tablica - Povijest promjena

WikiSysop: brisanje nepotrebnog teksta

2022-03-07T00:59:32Z

brisanje nepotrebnog teksta

←Starija inačica		Inačica od 00:59, 7. ožujka 2022.
Redak 1:		Redak 1:
	~~<!--'''Hash tablica'''-->~~[[Image:Hash table 3 1 1 0 1 0 0 SP.svg\|thumb\|315px\|right\|Mali telefonski imenik kao hash tablica]]		[[Image:Hash table 3 1 1 0 1 0 0 SP.svg\|thumb\|315px\|right\|Mali telefonski imenik kao hash tablica]]

	U [[računarstvo\|računalstvu]], '''''hash'' tablica''' ([[Engleski jezik\|eng]]. ''hash table'') ili ''hash'' mapa ([[Engleski jezik\|eng]]. ''Hash map'') je [[podatkovna struktura]] koja rabi ''hash'' funkciju za učinkovito preslikavanje određenih ključeva (na primjer imena ljudi) u njima pridružene vrijednosti (na primjer telefonske brojeve). [[Hash funkcija]] se koristi za transformiranje ključa u indeks (''hash'') to jest mjesto u nizu elemenata gde treba tražiti odgovarajuću vrijednost.		U [[računarstvo\|računalstvu]], '''''hash'' tablica''' ([[Engleski jezik\|eng]]. ''hash table'') ili ''hash'' mapa ([[Engleski jezik\|eng]]. ''Hash map'') je [[podatkovna struktura]] koja rabi ''hash'' funkciju za učinkovito preslikavanje određenih ključeva (na primjer imena ljudi) u njima pridružene vrijednosti (na primjer telefonske brojeve). [[Hash funkcija]] se koristi za transformiranje ključa u indeks (''hash'') to jest mjesto u nizu elemenata gde treba tražiti odgovarajuću vrijednost.
Redak 20:		Redak 20:

	U mnogim okolnostima, hash tablice se pokazuju učinkovitijim od stabala pretrage ili drugih tabličnih struktura. Zato su hash tablice u širokoj upotrebi u svim vrstama računskog softvera.		U mnogim okolnostima, hash tablice se pokazuju učinkovitijim od stabala pretrage ili drugih tabličnih struktura. Zato su hash tablice u širokoj upotrebi u svim vrstama računskog softvera.
	~~<!-- Hash tables should not be confused with the hash lists and hash trees used in cryptography and data transmission. -->~~

	== Uporaba ==		== Uporaba ==

WikiSysop: Bot: Automatska zamjena teksta (-{{cite book +{{Citiranje knjige)

2021-11-17T02:11:10Z

Bot: Automatska zamjena teksta (-{{cite book +{{Citiranje knjige)

←Starija inačica		Inačica od 02:11, 17. studenoga 2021.
Redak 6:		Redak 6:

	U dobro dimenzioniranoj hash tablici, prosječna cijena (broj računalnih naredbi) svakog pronalaženja ne ovisi o broju elemenata uskladištenih u tablici. Mnoge implementacije hash tablica također omogućuju proizvoljna unošenja i brisanja parova ključeva i vrijednosti uz konstantnu prosječnu (amortiziranu) cijenu po operaciji.<ref name="knuth">		U dobro dimenzioniranoj hash tablici, prosječna cijena (broj računalnih naredbi) svakog pronalaženja ne ovisi o broju elemenata uskladištenih u tablici. Mnoge implementacije hash tablica također omogućuju proizvoljna unošenja i brisanja parova ključeva i vrijednosti uz konstantnu prosječnu (amortiziranu) cijenu po operaciji.<ref name="knuth">
	{{~~cite book~~		{{Citiranje knjige
	\| author = [[Donald Knuth]]		\| author = [[Donald Knuth]]
	\| title = The Art of Computer Programming'		\| title = The Art of Computer Programming'

WikiSysop: Bot: Automatski unos stranica

2021-09-07T23:48:20Z

Bot: Automatski unos stranica

Nova stranica

[[Image:Hash table 3 1 1 0 1 0 0 SP.svg|thumb|315px|right|Mali telefonski imenik kao hash tablica]]

U [[računarstvo|računalstvu]], '''''hash'' tablica''' ([[Engleski jezik|eng]]. ''hash table'') ili ''hash'' mapa ([[Engleski jezik|eng]]. ''Hash map'') je [[podatkovna struktura]] koja rabi ''hash'' funkciju za učinkovito preslikavanje određenih ključeva (na primjer imena ljudi) u njima pridružene vrijednosti (na primjer telefonske brojeve). [[Hash funkcija]] se koristi za transformiranje ključa u indeks (''hash'') to jest mjesto u nizu elemenata gde treba tražiti odgovarajuću vrijednost.

U najboljem slučaju, hash funkcija preslikava svaki mogući ključ u zaseban indeks, ali je to u praksi gotovo nemoguće. Većina implementacija hash tablica podrazumijeva da su hash kolizije — parovi različitih ključeva s istim hash vrijednostima — obična pojava, i na neki način se brine da se ovaj problem svlada.

U dobro dimenzioniranoj hash tablici, prosječna cijena (broj računalnih naredbi) svakog pronalaženja ne ovisi o broju elemenata uskladištenih u tablici. Mnoge implementacije hash tablica također omogućuju proizvoljna unošenja i brisanja parova ključeva i vrijednosti uz konstantnu prosječnu (amortiziranu) cijenu po operaciji.<ref name="knuth">
{{cite book
| author = [[Donald Knuth]]
| title = The Art of Computer Programming'
| volume = 3: ''Sorting and Searching''
| edition = 2. izd.
| publisher = Addison-Wesley
| year = 1998.
| isbn = 0-201-89685-0
| note = Section 6.4: Hashing,
| pages = 513.–558.
}}
</ref>

U mnogim okolnostima, hash tablice se pokazuju učinkovitijim od stabala pretrage ili drugih tabličnih struktura. Zato su hash tablice u širokoj upotrebi u svim vrstama računskog softvera.


== Uporaba ==

=== Asocijativne tablice ===
Hash tablice se obično upotrebljavaju za implementaciju svih vrsta tablica koje se čuvaju u memoriji. Koriste se za implementaciju [[asocijativni nizovi|asocijativnih nizova]] (nizova čiji su indeksi proizvoljne nizove ili drugi kompliciraniji objekti), posebno u [[interpretirani programski jezik|interpretiranim programskim jezicima]] kao što su [[gawk]] i [[perl]].

=== Indeksi u bazama podataka ===
Hash tablice mogu se koristiti i za perzistentne strukture podataka koje su smještene na disku, i za [[indeks|indekse]] baza podataka, iako su [[balansirana stabla]] popularnija za ove primjene.

=== Skupovi ===
Osim vraćanja vrijednosti koja odgovara danom ključu, mnoge implementacije hash tablica mogu također odgovoriti i na pitanje postoji li takav unos ili ne.

Zbog toga se ove strukture mogu rabiti i za implementaciju skupa, koji odgovara na pitanje postoji li dani ključ u nekom skupu ključeva. U ovom se slučaju struktura može pojednostaviti eliminiranjem svih dijelova koji se tiču vrijednosti koje odgovaraju ključevima. ''[[Hashiranje]]'' se može koristiti za implementaciju bilo statičkih, bilo dinamičkih skupova.

=== Hashiranje ===
Hashiranje predstavlja koji omogućuje generiranje jedne ili više vrijednosti iz niza teksta pomoću matematičke formule, čime se dobije kriptirana vrijednost koja podatke čini sigurnima.<ref>[https://support.google.com/google-ads/answer/9004449?hl=hr Google Ads pomoć] ''Hashiranje: definicija'' / pristupljeno 26. srpnja 2020.</ref>

Hashiranje je jednosmjerna funkcija enkripcije koja uzima podatke bilo koje veličine i izlazi vrijednost fiksne veličine.
<ref name=heritage>[https://heritage-offshore.com/sigurnost-informacija/to-je-kontrolni-zbroj-i-kako-ga-koristiti-upute-za/ Heritage Offshore] Brayan Jackson: ''Što je kontrolni zbroj i kako ga koristiti? (Upute za Windows i Mac)'' / pristupljeno 26. srpnja 2020. </ref> Hashiranje je slično [[enkripcija|enkripciji]] i ''[[soljenje (računarstvo)|soljenju]]''.<ref>[https://heritage-offshore.com/sigurnost-informacija/ifriranje-hashing-soljenje-u-emu-je-razlika/ Heritage Offshore] Brayan Jackson / ''Šifriranje, hashing, soljenje – u čemu je razlika?'' / pristupljeno 26. srpnja 2020. </ref>

== Prednosti ==

Glavna prednost hash tablice nad drugim tabličnim strukturama podataka je njena brzina. Ova je prednost uočljivija kada je broj podataka u tablici velik (tisuće ili više). Hash tablice su posebno učinkovite kada se maksimalna količina podataka može predvidjeti unaprijed, tako da se veličina strukture može unaprijed alocirati tako da bude optimalna, i ne mora se kasnije mijenjati.

Ako su svi parovi ključeva-vrijednosti fiksirani i poznati unaprijed (pa dodavanja i brisanja nisu dopuštena), prosječna cijena pretrage može se smanjiti pažljivim izborom hash funkcije, veličine tablice i unutrašnjih struktura podataka. Štoviše, tada je moguće napraviti hash funkciju koja ne stvara kolizije. U ovom slučaju ključeve nije potrebno čuvati u tablici.

== Vidi ==
*[[hashiranje]]

== Izvori ==

{{izvori}}

[[Kategorija:Računarstvo]]