Mikä on hash-taulukko?

Hash-taulukko määritellään tietorakenteeksi, jota käytetään avainarvo-parien nopeaan lisäämiseen, etsimiseen ja poistamiseen. Se toimii hajautuskonsepti , jossa jokainen avain muunnetaan hash-funktiolla erilliseksi indeksiksi taulukossa. Indeksi toimii vastaavan arvon tallennuspaikkana. Yksinkertaisesti sanottuna se kartoittaa avaimet arvon kanssa.

kovakantinen vs pokkari

Mikä on kuormituskerroin?

Hajautustaulukon kuormituskerroin määräytyy sen mukaan, kuinka monta elementtiä siinä säilytetään suhteessa taulukon kokoon. Pöytä voi olla sekainen ja sillä voi olla pidemmät hakuajat ja törmäykset, jos kuormituskerroin on korkea. Ihanteellinen kuormituskerroin voidaan ylläpitää käyttämällä hyvää hash-toimintoa ja oikeaa taulukon koon muuttamista.

Mikä on hash-funktio?

Funktio, joka kääntää avaimet taulukon indekseiksi, tunnetaan hash-funktiona. Avaimet tulee jakaa tasaisesti taulukkoon kunnollisen hash-toiminnon avulla törmäysten vähentämiseksi ja nopean hakunopeuden varmistamiseksi.

• Kokonaisluku universumin oletus: Avainten oletetaan olevan kokonaislukuja tietyllä alueella universumin kokonaislukuoletuksen mukaan. Tämä mahdollistaa perustiivistystoimintojen, kuten jako- tai kertolaskutiivistyksen, käytön.
• Hajautus jaon mukaan: Tämä yksinkertainen hajautustekniikka käyttää avaimen jäljellä olevaa arvoa sen jälkeen, kun se on jaettu taulukon koolla indeksinä. Kun taulukon koko on alkuluku ja avaimet ovat tasaisin välein, se toimii hyvin.
• Hashing kertomalla: Tämä yksinkertainen hajautustoiminto kertoo avaimen vakiolla välillä 0–1, ennen kuin ottaa tuloksen murto-osan. Tämän jälkeen indeksi määritetään kertomalla murto-osa taulukon koolla. Se toimii myös tehokkaasti, kun näppäimet ovat tasaisesti hajallaan.

Hajautusfunktion valinta :

Kunnollisen hash-funktion valinta perustuu avainten ominaisuuksiin ja hajautustaulukon suunniteltuun toiminnallisuuteen. On erittäin tärkeää käyttää toimintoa, joka jakaa näppäimet tasaisesti ja vähentää törmäyksiä.

Kriteerit, joiden perusteella hash-funktio valitaan:

• Jotta törmäysten määrä pysyy mahdollisimman pienenä, hyvän hajautustoiminnon tulisi jakaa avaimet koko tiivistetaulukossa yhtenäisellä tavalla. Tämä tarkoittaa, että kaikissa avainpareissa todennäköisyyden, että kaksi avainta tiivistyy samaan paikkaan taulukossa, tulisi olla melko vakio.
• Nopean hajautustoiminnon ja avainten haun mahdollistamiseksi hajautustoiminnon tulee olla laskennallisesti tehokas.
• Avaimen päättäminen sen hash-arvosta pitäisi olla haastavaa. Tämän seurauksena yritykset arvata avainta hash-arvon avulla eivät todennäköisesti onnistu.
• Hajautusfunktion tulee olla riittävän joustava, jotta sitä voidaan säätää tiivistettävän tiedon muuttuessa. Esimerkiksi hajautustoiminnon on jatkettava toimintaansa oikein, jos tiivistettävien avainten koko tai muoto muuttuvat.

Törmäyksenratkaisutekniikat :

Törmäyksiä tapahtuu, kun vähintään kaksi avainta osoittaa samaan taulukkoindeksiin. Ketjutus, avoin osoitus ja kaksoishajautus ovat muutamia tekniikoita törmäysten ratkaisemiseen.

• Avoin osoitus : törmäykset käsitellään etsimällä seuraavaa tyhjää tilaa taulukosta. Jos ensimmäinen paikka on jo varattu, hajautustoimintoa sovelletaan seuraaviin paikkoihin, kunnes yksi jätetään tyhjäksi. On olemassa useita tapoja käyttää tätä lähestymistapaa, mukaan lukien kaksoishajautus, lineaarinen luotaus ja neliöllinen luotaus.
• Erillinen ketjutus : Erillisessä ketjutuksessa on linkitetty luettelo objekteista, jotka tiivistävät tiivistetaulukon kuhunkin paikkaan. Kaksi avainta sisältyy linkitettyyn luetteloon, jos ne hajautuvat samaan paikkaan. Tämä menetelmä on melko yksinkertainen käyttää ja voi hallita useita törmäyksiä.
• Robin Hoodin hajautus: Ketjun pituuden lyhentämiseksi Robin Hood -hajautusjärjestelmän törmäykset käsitellään kytkemällä näppäimet pois päältä. Algoritmi vertaa paikan ja kahden avaimen varatun paikan välistä etäisyyttä, jos uusi avain tiivistyy jo varattuun paikkaan. Nykyinen avain vaihdetaan uuteen, jos se on lähempänä ihanteellinen paikkaansa. Tämä tuo olemassa olevan avaimen lähemmäksi ihanteellista paikkaa. Tällä menetelmällä on taipumus vähentää törmäyksiä ja keskimääräistä ketjun pituutta.

Dynaaminen koon muuttaminen:

Tämä ominaisuus mahdollistaa hash-taulukon laajentumisen tai supistumisen vastauksena taulukon sisältämien elementtien lukumäärän muutoksiin. Tämä edistää kuormituskerrointa, joka on ihanteellinen ja nopeat hakuajat.

zip-komento linuxissa

Hash-taulukon toteutukset

Python, Java, C++ ja Ruby ovat vain muutamia ohjelmointikieliä, jotka tukevat hash-taulukoita. Niitä voidaan käyttää mukautettuna tietorakenteena sen lisäksi, että ne sisällytetään usein vakiokirjastoon.

Esimerkki – Laske merkit String geeksforgeeksissa.

Tässä esimerkissä käytämme hajautustekniikkaa merkkijonon määrän tallentamiseen.

#include  using namespace std; int main() {  //initialize a string  string s='geeksforgeeks';    // Using an array to store the count of each alphabet   // by mapping the character to an index value  int arr[26]={0};    //Storing the count  for(int i=0;i

public class CharacterCount {  public static void main(String[] args) {  // Initialize a string  String s = 'geeksforgeeks';  // Using an array to store the count of each alphabet  // by mapping the character to an index value  int[] arr = new int[26];  // Storing the count  for (int i = 0; i < s.length(); i++) {  arr[s.charAt(i) - 'a']++;  }  // Search the count of the character  char ch = 'e';  // Get count  System.out.println('The count of ' + ch + ' is ' + arr[ch - 'a']);  } }>

# Initialize a string s = 'geeksforgeeks' # Using a list to store the count of each alphabet # by mapping the character to an index value arr = [0] * 26 # Storing the count for i in range(len(s)): arr[ord(s[i]) - ord('a')] += 1 # Search the count of the character ch = 'e' # Get count print('The count of ', ch, ' is ', arr[ord(ch) - ord('a')])>

using System; class Program {  static void Main(string[] args) {  //initialize a string  string s = 'geeksforgeeks';  // Using an array to store the count of each alphabet   // by mapping the character to an index value  int[] arr = new int[26];  //Storing the count  for (int i = 0; i < s.Length; i++) {  arr[s[i] - 'a']++;  }  //Search the count of the character  char ch = 'e';  // get count  Console.WriteLine('The count of ' + ch + ' is ' + arr[ch - 'a']);  } }>

// Initialize a string const s = 'geeksforgeeks'; // Using an array to store the count of each alphabet // by mapping the character to an index value const arr = Array(26).fill(0); // Storing the count for (let i = 0; i < s.length; i++) {  arr[s.charCodeAt(i) - 'a'.charCodeAt(0)]++; } // Search the count of the character const ch = 'e'; // Get count console.log(`The count of ${ch} is ${arr[ch.charCodeAt(0) - 'a'.charCodeAt(0)]}`);>

Lähtö:

kuvien kohdistaminen css:ssä

The count of e is 4>

Hash-taulukon monimutkaisuusanalyysi:

Hajautus-, lisäys- ja poistotoimintoja varten hash-taulukoiden tapausten keskimääräinen aikamonimutkaisuus on O(1). Silti nämä operaatiot voivat pahimmassa tapauksessa vaatia O(n)-ajan, missä n on taulukon elementtien lukumäärä.

Hash-taulukon sovellukset:

• Hash-taulukoita käytetään usein suurten tietomäärien indeksoimiseen ja etsimiseen. Hakukone saattaa käyttää hash-taulukkoa indeksoimiensa verkkosivujen tallentamiseen.
• Tiedot tallennetaan yleensä välimuistiin hash-taulukoiden kautta, mikä mahdollistaa nopean pääsyn usein käytettyihin tietoihin.
• Hash-funktioita käytetään usein kryptografiassa digitaalisten allekirjoitusten luomiseen, tietojen validointiin ja tietojen eheyden takaamiseen.
• Hash-taulukoita voidaan käyttää tietokantaindeksien toteuttamiseen, mikä mahdollistaa nopean pääsyn tietoihin avainarvojen perusteella.