Kas ir hašings? Kā darbojas hash kodi - ar piemēriem

Ievads jaukšanā

Jaukšana ir paredzēta, lai efektīvi atrastu vai uzglabātu priekšmetu kolekcijā.

Piemēram, ja mums ir saraksts ar 10 000 angļu valodas vārdiem un mēs vēlamies pārbaudīt, vai dots vārds ir sarakstā, būtu neefektīvi secīgi salīdzināt vārdu ar visiem 10 000 vienumiem, līdz atrodam atbilstību. Pat ja vārdu saraksts ir sakārtots leksikogrāfiski, piemēram, vārdnīcā, jums tomēr būs vajadzīgs zināms laiks, lai atrastu meklēto vārdu.

Jaukšana ir paņēmiens, kā padarīt lietas efektīvākas, jau pašā sākumā efektīvi sašaurinot meklēšanu.

Kas ir jaukšana?

Jaukšana nozīmē izmantot kādu funkciju vai algoritmu, lai objekta datus piesaistītu kādai reprezentatīvai veselā skaitļa vērtībai.

Šo tā saukto hash kodu (vai vienkārši hash) pēc tam var izmantot kā veidu, kā sašaurināt mūsu meklēšanu, meklējot vienumu kartē.

Parasti šos jaukšanas kodus izmanto, lai izveidotu indeksu, kurā tiek saglabāta vērtība.

Kā notiek jaukšana

Jaukšanas tabulās dati tiek glabāti atslēgu un vērtību pāru formās. Atslēga, ko izmanto datu identificēšanai, tiek ievadīta kā jaukšanas funkcijas ievade. Pēc tam hash kods, kas ir vesels skaitlis, tiek piesaistīts fiksētajam izmēram.

Hash tabulām ir jāatbalsta 3 funkcijas.

  • ievietot (atslēga, vērtība)
  • iegūt (atslēga)
  • dzēst (atslēga)

Pieņemsim, ka tikai kā piemēru, lai palīdzētu mums izprast jēdzienu, mēs vēlamies virkņu atslēgu sarakstu sasaistīt ar virkņu vērtībām (piemēram, kartēt valstu sarakstu ar to galvaspilsētām).

Pieņemsim, ka mēs vēlamies saglabāt datus tabulas tabulā.

Pieņemsim, ka mūsu hash funkcija ir vienkārši ņemt virknes garumu.

Vienkāršības labad mums būs divi masīvi: viens mūsu atslēgām un viens vērtībām.

Tātad, lai ievietotu vienumu jaukšanas tabulā, mēs aprēķinām tā hash kodu (šajā gadījumā vienkārši jāuzskaita rakstzīmju skaits), pēc tam atslēgu un vērtību ievietojam masīvos attiecīgajā indeksā.

Piemēram, Kubai ir hash kods (garums) 4. Tāpēc mēs Kubu glabājam 4. pozīcijā atslēgu masīvā un Havanna vērtību masīva 4. indeksā utt. Un mēs nonākam pie sekojošā:

Šajā konkrētajā piemērā lietas darbojas diezgan labi. Mūsu masīvam jābūt pietiekami lielam, lai tajā ietilptu garākā virkne, taču šajā gadījumā tas ir tikai 11 sloti.

Mēs patiešām izniekojam mazliet vietas, jo, piemēram, mūsu datos nav 1 burta atslēgu, kā arī taustiņu no 8 līdz 10 burtiem.

Bet šajā gadījumā arī izšķērdētā telpa nav tik slikta. Virknes garuma noteikšana ir jauka un ātra, tāpat kā ar konkrēto atslēgu saistītās vērtības atrašanas process (protams, ātrāk nekā līdz piecu virkņu salīdzinājumiem).

Bet ko mēs darām, ja mūsu datu kopai ir virkne, kurā ir vairāk nekā 11 rakstzīmes?

Ko darīt, ja mums ir viens cits vārds ar 5 rakstzīmēm “Indija” un mēģinām to piešķirt indeksam, izmantojot mūsu hash funkciju. Tā kā indekss 5 jau ir aizņemts, mums ir jāzvana, ko ar to darīt. To sauc par sadursmi.

Ja mūsu datu kopai būtu virkne ar tūkstoš rakstzīmēm, un datu glabāšanai izveidojat tūkstošiem indeksu masīvu, tas novestu pie vietas izšķērdēšanas. Ja mūsu atslēgas būtu nejauši vārdi no angļu valodas, kur ir tik daudz vārdu ar vienādu garumu, garuma izmantošana kā jaukšanas funkcija būtu diezgan bezjēdzīga.

Sadursmju apstrāde

Sadursmju gadījumos tiek izmantotas divas pamatmetodes.

  1. Atsevišķa ķēde
  2. Atveriet adresēšanu

Atsevišķa ķēde

Hash sadursmju apstrāde, izmantojot atsevišķu ķēdi, segmentos izmanto papildu datu struktūru, vēlams dinamiski sadalīt vēlamo sarakstu. Mūsu piemērā, pievienojot Indiju datu kopai, tā tiek pievienota saistītajam sarakstam, kas tiek glabāts indeksā 5, tad mūsu tabula izskatīsies šādi.

Lai atrastu vienumu, vispirms ejam pie spaiņa un pēc tam salīdzinām atslēgas. Šī ir populāra metode, un, ja tiek izmantots saišu saraksts, hash nekad netiek aizpildīts. Izmaksas get(k)vidēji ir, O(n)kur n ir atslēgu skaits spainī, kopējais atslēgu skaits ir N.

Atsevišķas ķēdes problēma ir tā, ka datu struktūra var pieaugt, nepārsniedzot robežas.

Atveriet adresēšanu

Atvērtā adresēšana neievieš jaunu datu struktūru. Ja notiek sadursme, mēs meklējam pieejamību nākamajā algoritma ģenerētajā vietā. Atvērto adresēšanu parasti izmanto gadījumos, kad uzglabāšanas vieta ir ierobežota, ti, iegulti procesori. Atvērtā adresēšana ne vienmēr ir ātrāka nekā atsevišķa ķēdēšana.

Metodes atvērtai adresēšanai

  • [Lineārā zondēšana
  • Kvadrātiskā zondēšana
  • Dubultā jaukšana

Kā kodā izmantot jaukšanu.

Python

 # Few languages like Python, Ruby come with an in-built hashing support. # Declaration my_hash_table = {} my_hash_table = dict() # Insertion my_hash_table[key] = value # Look up value = my_hash_table.get(key) # returns None if the key is not present || Deferred in python 3, available in python 2 value = my_hash_table[key] # throws a ValueError exception if the key is not present # Deletion del my_hash_table[key] # throws a ValueError exception if the key is not present # Getting all keys and values stored in the dictionary keys = my_hash_table.keys() values = my_hash_table.values()
: raķete:

Palaist kodu

Java

 // Java doesn't include hashing by default, you have to import it from java.util library // Importing hashmaps import java.util.HashMap; // Declaration HashMap myHashTable = new HashMap(); // declares an empty map. // Insertion myHashTable.put(key, value); // Deletion myHashtable.remove(key); // Look up myHashTable.get(key); // returns null if the key K is not present myHashTable.containsKey(key); // returns a boolean value, indicating the presence of a key // Number of key, value pairs in the hash table myHashTable.size();
: raķete:

Palaist kodu

Plašāka informācija par jaukšanu

  • Bezkoda rokasgrāmata par jaukšanas un jaukšanas tabulām
  • Kā ieviest vienkāršu hash tabulu JavaScript
  • Hash tabulas paskaidrotas