Mis on räsimine? Kuidas räsikoodid töötavad - koos näidetega

Sissejuhatus räsimisse

Räsimine on mõeldud kollektsiooni eseme tõhusaks leidmiseks või säilitamiseks vajaliku probleemi lahendamiseks.

Näiteks kui meil on 10 000 ingliskeelse sõna loetelu ja me tahame kontrollida, kas antud sõna on loendis, oleks ebaefektiivne sõna järjestikku kõigi 10 000 üksusega võrrelda, kuni leiame vaste. Isegi kui sõnade loend on leksikograafiliselt sorteeritud, nagu sõnastikus, vajate siiski otsitava sõna leidmiseks veidi aega.

Räsimine on tehnika asjade efektiivsemaks muutmiseks, vähendades otsinguid kohe alguses.

Mis on räsimine?

Räsimine tähendab objekti või algoritmi kasutamist objekti andmete kaardistamiseks mõne tüüpilise täisarvu väärtuseni.

Seda nn räsikoodi (või lihtsalt räsi) saab seejärel kasutada viisina meie otsingut kitsendada kaardilt üksuse otsimisel.

Üldiselt kasutatakse neid räsikoode indeksi loomiseks, kuhu väärtus on salvestatud.

Kuidas räsimine töötab

Räsi tabelites salvestate andmeid võtme- ja väärtuspaaride kujul. Andmete tuvastamiseks kasutatav võti antakse räsimisfunktsiooni sisendina. Seejärel vastendatakse räsikood, mis on täisarv, meie kindla suurusega.

Räsi tabelid peavad toetama kolme funktsiooni.

  • sisesta (võti, väärtus)
  • hankima (võti)
  • kustuta (võti)

Oletame, et puhtalt näitena, mis aitab meil mõistest aru saada, soovime kaardistada stringivõtmete loendi stringiväärtusteks (näiteks kaardistada riikide loetelu nende pealinnadesse).

Oletame, et tahame andmed tabelis tabelisse salvestada.

Oletame, et meie räsifunktsioon on lihtsalt võtta stringi pikkus.

Lihtsuse huvides on meil kaks massiivi: üks võtmete ja teine ​​väärtuste jaoks.

Nii et üksuse räsitabelisse lisamiseks arvutame selle räsikoodi (sel juhul loeme lihtsalt märkide arvu), seejärel paneme võtme ja väärtuse vastavasse indeksisse massiividesse.

Näiteks Kuubal on räsikood (pikkus) 4. Seega hoiame Kuuba võtmemassiivis 4. positsioonil ja Havanna väärtuste massiivi 4. indeksis. Ja lõpuks jõuame järgmisele:

Selles konkreetses näites toimivad asjad üsna hästi. Meie massiiv peab olema piisavalt pikk, et mahutada pikim string, kuid sel juhul on see ainult 11 pesa.

Me raiskame natuke ruumi, sest näiteks meie andmetes pole ühetähelisi võtmeid ega ka 8–10-tähelisi võtmeid.

Kuid ka sel juhul pole raisatud ruum nii hull. Stringi pikkuse võtmine on tore ja kiire ning sama on ka antud võtmega seotud väärtuse leidmise protsess (kindlasti kiirem kui kuni viie stringi võrdluse tegemine).

Mida aga teha, kui meie andmekogul on string, millel on rohkem kui 11 tähemärki?

Mis siis, kui meil on veel üks viie tähemärgiga sõna „India” ja proovime selle oma räsifunktsiooni abil indeksile määrata. Kuna indeks 5 on juba hõivatud, peame helistama, mida sellega teha. Seda nimetatakse kokkupõrkeks.

Kui meie andmestikul oleks tuhande tähemärgiga string ja teete andmete salvestamiseks tuhandete indeksite massiivi, tooks see kaasa ruumi raiskamise. Kui meie klahvid oleksid juhuslikud sõnad inglise keelest, kus on nii palju sama pikkusega sõnu, oleks pikkuse kasutamine räsimisfunktsioonina üsna kasutu.

Kokkupõrke käsitlemine

Kokkupõrgete käsitlemisel kasutatakse kahte põhimeetodit.

  1. Eraldi aheldamine
  2. Avage aadressimine

Eraldi aheldamine

Räsikokkupõrgete käsitlemine eraldi aheldamise abil kasutab ämbritesse täiendavat andmestruktuuri, eelistatavalt dünaamiliseks jaotamiseks lingitud loendit. Meie näites, kui lisame India andmekogumisse, lisatakse see indeksis 5 salvestatud lingitud loendile, siis näeks meie tabel välja selline.

Üksuse leidmiseks läheme kõigepealt ämbrisse ja seejärel võrdleme võtmeid. See on populaarne meetod ja kui linkide loendit kasutatakse, ei täida räsi kunagi. Maksumus get(k)on keskmiselt, O(n)kus n on võtmete arv ämbris, võtmete koguarv on N.

Eraldi aheldamise probleem on see, et andmestruktuur võib kasvada ilma piirideta.

Avage aadressimine

Avatud adresseerimine ei too kasutusele uut andmestruktuuri. Kokkupõrke korral otsime kättesaadavust järgmisest algoritmi genereeritud kohast. Avatud adresseerimist kasutatakse tavaliselt seal, kus salvestusruum on piiratud, st sisseehitatud protsessorid. Avatud adresseerimine ei pruugi tingimata olla kiirem kui eraldiseisev aheldamine.

Avatud adresseerimise meetodid

  • [Lineaarne sondeerimine
  • Teise astme sondeerimine
  • Topelt räsimine

Kuidas räsimist oma koodis kasutada.

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()
: rakett:

Käivituskood

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();
: rakett:

Käivituskood

Lisateave räsimise kohta

  • Koodita räsimis- ja räsimislaudade juhend
  • Kuidas rakendada JavaScripti lihtsat räsitabelit
  • Hash tabelid selgitatud