Hashing és una estructura de dades fonamental que emmagatzema i recupera de manera eficient les dades d'una manera que permet un accés ràpid. Implica mapar dades a un índex específic en una taula hash mitjançant a funció hash que permet una ràpida recuperació d'informació basada en la seva clau. Aquest mètode s'utilitza habitualment en bases de dades, c sistemes dolorosos i diverses aplicacions de programació per optimitzar les operacions de cerca i recuperació.

Estructures de dades – Hashing

Taula de contingut

• Funció hash
• Què és una col·lisió hash?
• Tècniques de resolució de col·lisions
• Aplicacions de Hashing
• Problema fàcil en hashing
• Problema mitjà en hashing
• Problema difícil en hashing

taula hash .

Com funciona:

1. Funció hash: Proporcioneu els vostres elements de dades a la funció hash.
2. Codi hash: La funció hash analitza les dades i dóna un codi hash únic.
3. Taula hash: Aleshores, el codi hash us indica una ubicació específica dins de la taula hash.

Funció hash

El funció hash és una funció que pren a clau i torna un índex al taula hash . L'objectiu d'una funció hash és distribuir les claus de manera uniforme a través de la taula hash, minimitzant les col·lisions (quan dues claus s'assignen al mateix índex).

Les funcions hash comunes inclouen:

• Mètode de divisió: Clau % Mida de la taula hash
• Mètode de multiplicació: (Clau * Constant) % Mida de la taula hash
• Hashing universal: Una família de funcions hash dissenyades per minimitzar les col·lisions

Què és una col·lisió hash?

Una col·lisió hash es produeix quan dues claus diferents es mapen al mateix índex en una taula hash. Això pot passar fins i tot amb una bona funció hash, especialment si la taula hash està plena o les tecles són similars.

Causes de col·lisions de hash:

• Funció hash deficient: Una funció hash que no distribueix les claus de manera uniforme a la taula hash pot provocar més col·lisions.
• Factor de càrrega elevat: Un factor de càrrega elevat (proporció de claus a la mida de la taula hash) augmenta la probabilitat de col·lisions.
• Tecles semblants: És més probable que les claus que tinguin un valor o una estructura similars xoquin.

Tècniques de resolució de col·lisions

Hi ha dos tipus de tècniques de resolució de col·lisions:

1. Adreça oberta:
   • Sondeig lineal: Cerqueu una ranura buida seqüencialment
   • Sonda quadràtica: Cerqueu una ranura buida mitjançant una funció quadràtica
2. Adreçament tancat:
   • Encadenat: Emmagatzema les claus en col·lisió en una llista enllaçada o en un arbre de cerca binari a cada índex
   • Hashing de cucut: Utilitzeu diverses funcions hash per distribuir les claus

Aplicacions de Hashing

Les taules hash s'utilitzen en una gran varietat d'aplicacions, com ara:

• Bases de dades: Emmagatzematge i recuperació de dades basades en claus úniques
• Emmagatzematge a la memòria cau: Emmagatzemar les dades a les quals s'accedeix amb freqüència per a una recuperació més ràpida
• Taules de símbols: Mapeig d'identificadors amb els seus valors en llenguatges de programació
• Enrutament de xarxa: Determinació de la millor ruta per als paquets de dades

Què és Hashing?

Mapeig d'índex (o hashing trivial)

Encadenament separat per a la gestió de col·lisions

Obriu l'adreçament per a la gestió de col·lisions

Doble hashing

Factor de càrrega i repetició

Problema fàcil en hashing

• Esbrineu si una matriu és un subconjunt d'una altra matriu
• Unió i intersecció de dues llistes enllaçades
• Donada una matriu A[] i un nombre x, comproveu la parella a A[] amb la suma com a x
• Distància màxima entre dues ocurrències del mateix element a la matriu
• Compta el màxim de punts a la mateixa línia
• Element més freqüent en una matriu
• Troba l'únic element repetitiu entre 1 a n-1
• Com comprovar si dos conjunts donats són inconjunts?
• Suma no solapada de dos conjunts
• Comproveu si dues matrius són iguals o no
• Cerca els elements que falten d'un rang
• Nombre mínim de subconjunts amb elements diferents
• Elimina el nombre mínim d'elements de manera que no existeix cap element comú a les dues matrius
• Trobeu parells amb una suma determinada de manera que els elements de la parella estiguin en files diferents
• Comptar les parelles amb una suma donada
• Compteu quàdruples de quatre matrius ordenades la suma dels quals és igual a un valor donat x
• Ordena els elements per freqüència
• Trobeu tots els parells (a, b) en una matriu tal que a % b = k
• Agrupa paraules amb el mateix conjunt de caràcters
• k-èsimo element diferent (o no repetit) en una matriu.

Problema mitjà en hashing

• Trobeu l'itinerari a partir d'una llista determinada de bitllets
• Trobeu el nombre d'empleats per a cada empleat
• Subbarrat més llarg amb la suma divisible per k
• Trobeu el subarray més gran amb 0 suma
• Més llarga Subseqüència consecutiva creixent
• Compteu diferents elements en cada finestra de mida k
• Troba subbarray amb la suma donada | Set 2 (Maneja números negatius)
• Implementant la nostra pròpia taula hash amb encadenament separat a Java
• Implementació de la pròpia taula hash amb sondeig lineal d'adreçament obert en C++
• Insercions mínimes per formar un palíndrom amb permutacions permeses
• Diferència màxima possible de dos subconjunts d'una matriu
• Ordenació mitjançant la funció hash trivial
• Subarray més petit amb k nombres diferents

Problema difícil en hashing

• Clonar un arbre binari amb punters aleatoris
• Subbarrat més gran amb el mateix nombre de 0s i 1s
• Tots els triplets únics que sumen un valor determinat
• Consultes de subcadenes de palíndrom
• Interval de consultes per a freqüències d'elements de matriu
• Elements que s'han d'afegir perquè tots els elements d'un rang estiguin presents a la matriu
• Cuckoo Hashing: el pitjor dels casos O(1) Cerca!
• Compteu els subarrays amb elements diferents totals iguals que la matriu original
• Matriu màxim de dues matrius donades mantenint el mateix ordre
• Trobeu la suma de tota la suma única de submatrius per a una matriu determinada.
• Seqüència de Recaman
• Longitud de la subseqüència bitònica estricta més llarga
• Cerca tots els subarbres duplicats
• Esbrineu si hi ha un rectangle a la matriu binària amb les cantonades com 1

Links ràpids :

• 'Problemes de pràctica' en hashing
• Les 20 principals preguntes d'entrevista basades en la tècnica de hashing
• 'Vídeos' a Hashing