Zgoščevanje je priljubljena tehnika, ki se uporablja za čim hitrejše shranjevanje in pridobivanje podatkov. Glavni razlog za uporabo zgoščevanja je, da izvaja vstavljanje, brisanje, iskanje in druge operacije

Zakaj uporabljati zgoščevanje?

Pri zgoščevanju se lahko vse operacije, kot so vstavljanje, iskanje in brisanje, izvedejo v O(1), tj. v konstantnem času. Časovna zapletenost najslabšega primera za zgoščevanje ostaja O(n), vendar je povprečna časovna zapletenost primera O(1).

HashTable

Uporablja se za ustvarjanje nove zgoščene tabele.

Sintaksa:

// function to delete a key from the hashtable  delete (key) {  const index = this._setKey(key);  if (this.table[index]) {  this.table[index] = [];  this.size--;  return true;  } else {  return false;  } }>

Osnovne operacije s sintakso

Pridobite:

Uporablja se za iskanje ključa znotraj zgoščene tabele in vrnitev vrednosti, ki je povezana s tem ključem.

Sintaksa:

// function inside hashtable class to  // access a value using its key get(key) {  const target = this._setKey(key);  return this.table[target]; }>

Vstavi:

Uporablja se za vstavljanje novega para ključ-vrednost znotraj zgoščene tabele.

Sintaksa:

// function to insert a value in the  // hash table using setKey function insert(value) {  const index = this._setKey(value);  this.table[index] = value;  this.size++; }>

Iskanje:

Uporablja se za iskanje vrednosti.

Sintaksa:

// search a value (by getting its  // key using setKey function) search(value){  const index = this._setKey(value);  if(this.table[index]==value)  console.log('The value is found at index : ',index);  else  console.log('Not found'); }>

Izbriši:

Uporablja se za brisanje določenega para ključ-vrednost iz zgoščene tabele.

Sintaksa:

// function to delete a key from the hashtable  delete (key) {  const index = this._setKey(key);  if (this.table[index]) {  this.table[index] = [];  this.size--;  return true;  } else {  return false;  } }>

Komponente zgoščevanja v Javascriptu

1. Zgoščena tabela: Zgoščevalna tabela je posplošitev matrike. Zagotavlja funkcionalnost, v kateri je zbirka podatkov shranjena na tak način, da je te elemente pozneje enostavno najti, če je to potrebno. Zaradi tega je iskanje elementa zelo učinkovito.

kako najti skrite stvari na androidu

2. Funkcija zgoščevanja: Zgoščevalna funkcija se uporablja za pretvorbo danega ključa v določen indeks reže. uporablja se za preslikavo vsakega možnega ključa v edinstven indeks reže. Če je vsak ključ preslikan v edinstveni indeks reže, je zgoščevalna funkcija znana kot popolna zgoščevalna funkcija. Zelo težko je ustvariti popolno zgoščevalno funkcijo, a naša naloga programerja je ustvariti takšno zgoščevalno funkcijo, s pomočjo katere bo število kolizij čim manjše.

Dobra zgoščevalna funkcija mora imeti naslednje lastnosti:

koliko ničel v 1 milijardi

• Učinkovito izračunljiv.
• Ključe je treba enakomerno porazdeliti (vsak položaj na mizi je za vsakega enako verjeten).
• Treba je čim bolj zmanjšati trke.
• Imeti mora nizek faktor obremenitve (število elementov v tabeli, deljeno z velikostjo tabele).

3. Ravnanje ob trku: Ker nam zgoščevalna funkcija za velik ključ zagotovi majhno število, obstaja možnost, da dva ključa povzročita isto vrednost. Situacija, ko se na novo vstavljeni ključ preslika v že zasedeno režo v zgoščevalni tabeli, se imenuje trk in ga je treba obravnavati z uporabo neke tehnike obravnavanja trkov. Sledijo načini reševanja trkov:

• Veriženje: Ideja je, da vsaka celica zgoščevalne tabele kaže na povezan seznam zapisov, ki imajo enako vrednost zgoščevalne funkcije. Veriženje je preprosto, vendar zahteva dodaten pomnilnik zunaj tabele.
• Odpri naslavljanje: Pri odprtem naslavljanju so vsi elementi shranjeni v sami zgoščeni tabeli. Vsak vnos v tabeli vsebuje zapis ali NIL. Pri iskanju elementa pregledamo mesta tabele eno za drugo, dokler ne najdemo želenega elementa ali pa je jasno, da elementa ni v tabeli.

Izvedba s primerom:

Korak 1: Ustvarite razred HashTable z začetnimi lastnostmi tabele in velikosti.

2. korak: Dodajte zasebno funkcijo setKey(key) za pretvorbo ključev v indekse.

3. korak: Dodajte funkciji insert() in get() za dodajanje in dostop do parov ključ-vrednost iz tabele.

4. korak: Dodajte funkcijo remove(), da odstranite ključ iz zgoščene tabele.

Primer 1: Recimo, da moramo v zgoščevalno tabelo shraniti 5 števil 100,87,86,12,25 in 9. V tem primeru bomo ustvarili funkcijo setKey, v kateri bomo vrednost vzeli kot argument in jo pretvorili v indeks zgoščene tabele. Spodaj je izvedba.

Javascript

pozdravljen svet java

>

>

Izhod:

[ 100,  ,  12,  ,  86,  87,  ,  9 ] The value is found at index : 7 Not found [ 100,  ,  [],  ,  86,  87,  ,  9 ]>

V izhodu ali kaže, da ima tabela 1 ali 3 zaporedne prazne prostore/indekse.

Primer 2: Recimo, da želimo kontaktne številke družine s 5 člani shraniti v zgoščevalno tabelo. Za to bomo ustvarili zgoščeno tabelo velikosti 10 in shranili kontaktne podatke. Indeks bo nastavljen z zasebno funkcijo setKey, ki bo zadnjo številko kontaktne številke pretvorila v indeks razpršilne tabele.

Javascript

seznam na Javi

spremenljivke nginx

>

>

Izhod:

[ ,  92752521,  98747512,  94755523,  ,  98754525,  ,  98556529 ] The contact number is found at index : 1 Contact Number not found [ ,  [],  98747512,  94755523,  ,  98754525,  ,  98556529 ]>

V izhodu ali kaže, da ima tabela 1 ali 3 zaporedne prazne prostore/indekse.