Què és la taula hash?

Una taula hash es defineix com una estructura de dades que s'utilitza per inserir, buscar i eliminar ràpidament parells clau-valor. Funciona a la concepte hashing , on cada clau es tradueix mitjançant una funció hash a un índex diferent en una matriu. L'índex funciona com a ubicació d'emmagatzematge del valor coincident. En paraules senzilles, mapeja les claus amb el valor.

dormir javascript

Què és el factor de càrrega?

El factor de càrrega d'una taula hash està determinat pel nombre d'elements que s'hi guardan en relació amb la mida de la taula. La taula pot estar desordenada i tenir temps de cerca i col·lisions més llargs si el factor de càrrega és alt. Es pot mantenir un factor de càrrega ideal amb l'ús d'una bona funció hash i un redimensionament adequat de la taula.

Què és una funció Hash?

Una funció que tradueix claus en índexs de matriu es coneix com a funció hash. Les claus s'han de distribuir uniformement per la matriu mitjançant una funció hash decent per reduir les col·lisions i garantir velocitats de cerca ràpides.

• Hipòtesi de l'univers enter: Se suposa que les claus són nombres enters dins d'un determinat interval d'acord amb el supòsit de l'univers enter. Això permet l'ús d'operacions bàsiques de resum com ara la divisió o la multiplicació.
• Hashing per divisió: Aquesta tècnica de hash senzilla utilitza el valor restant de la clau després de dividir-la per la mida de la matriu com a índex. Quan la mida d'una matriu és un nombre primer i les tecles estan espaciades uniformement, funciona bé.
• Hashing per multiplicació: Aquesta operació hash senzilla multiplica la clau per una constant entre 0 i 1 abans de prendre la part fraccionària del resultat. Després d'això, l'índex es determina multiplicant el component fraccionari per la mida de la matriu. A més, funciona amb eficàcia quan les tecles estan repartides per igual.

Escollir una funció hash :

La selecció d'una funció hash decent es basa en les propietats de les claus i la funcionalitat prevista de la taula hash. És crucial utilitzar una funció que distribueixi uniformement les tecles i redueixi les col·lisions.

Criteris en funció dels quals s'escull una funció hash:

• Per garantir que el nombre de col·lisions es mantingui al mínim, una bona funció hash hauria de distribuir les claus per tota la taula hash de manera uniforme. Això implica que, per a tots els aparellaments de claus, la probabilitat que dues claus es trobin a la mateixa posició a la taula hauria de ser força constant.
• Per permetre un hash ràpid i una recuperació de claus, la funció hash hauria de ser computacionalment eficient.
• Hauria de ser difícil deduir la clau del seu valor hash. Com a resultat, els intents d'endevinar la clau utilitzant el valor hash tenen menys probabilitats de tenir èxit.
• Una funció hash ha de ser prou flexible per ajustar-se a mesura que canvien les dades que s'estan calculant. Per exemple, la funció hash ha de continuar funcionant correctament si les claus que s'estan modificant canvien de mida o format.

Tècniques de resolució de col·lisions :

Les col·lisions es produeixen quan dues o més tecles apunten al mateix índex de matriu. L'encadenament, l'adreçament obert i el doble hashing són algunes de les tècniques per resoldre col·lisions.

• Adreçament obert : Les col·lisions es gestionen cercant l'espai buit següent a la taula. Si ja s'ha ocupat la primera ranura, la funció hash s'aplica a les ranures posteriors fins que n'hi quedi una buida. Hi ha diverses maneres d'utilitzar aquest enfocament, com ara el doble hashing, el sondeig lineal i el sondeig quadràtic.
• Encadenament separat : En un encadenament separat, hi ha una llista enllaçada d'objectes que hash a cada ranura de la taula hash. S'inclouen dues claus a la llista enllaçada si tenen un hash a la mateixa ranura. Aquest mètode és bastant senzill d'utilitzar i pot gestionar diverses col·lisions.
• Hashing de Robin Hood: Per reduir la longitud de la cadena, les col·lisions en el hashing de Robin Hood s'aborden desactivant les tecles. L'algoritme compara la distància entre la ranura i la ranura ocupada de les dues claus si una nova clau fa hash a una ranura ja ocupada. La clau existent s'intercanvia amb la nova si està més a prop de la seva ranura ideal. Això apropa la clau existent a la seva ranura ideal. Aquest mètode té una tendència a reduir les col·lisions i la longitud mitjana de la cadena.

Redimensionament dinàmic:

Aquesta característica permet que la taula hash s'ampliï o es contrau en resposta als canvis en el nombre d'elements continguts a la taula. Això promou un factor de càrrega que és ideal i temps de cerca ràpids.

np punt

Implementacions de la Taula Hash

Python, Java, C++ i Ruby són només alguns dels llenguatges de programació que admeten taules hash. Es poden utilitzar com a estructura de dades personalitzada a més d'incloure's sovint a la biblioteca estàndard.

Exemple: comptar caràcters a la cadena geeksforgeeks.

En aquest exemple, utilitzem una tècnica hashing per emmagatzemar el recompte de la cadena.

#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)]}`);>

Sortida:

tutorial d'espurna

The count of e is 4>

Anàlisi de complexitat d'una taula hash:

Per a les operacions de cerca, inserció i supressió, les taules hash tenen una complexitat de temps mitjana de cas de O(1). No obstant això, aquestes operacions poden, en el pitjor dels casos, requerir temps O(n), on n és el nombre d'elements de la taula.

Aplicacions de la taula hash:

• Les taules hash s'utilitzen sovint per indexar i cercar volums massius de dades. Un motor de cerca pot utilitzar una taula hash per emmagatzemar les pàgines web que ha indexat.
• Les dades generalment s'emmagatzemen a la memòria cau mitjançant taules hash, la qual cosa permet un accés ràpid a la informació que s'utilitza amb freqüència.
• Les funcions hash s'utilitzen sovint en criptografia per crear signatures digitals, validar dades i garantir la integritat de les dades.
• Les taules hash es poden utilitzar per implementar índexs de bases de dades, que permeten un accés ràpid a les dades basades en valors clau.