En ciencias da computación, unha táboa hash é unha estrutura de datos que implementa unha táboa asociativa, tamén chamada dicionario ou simplemente mapa; unha táboa asociativa é un tipo de dato abstracto que asocia chaves a valores. Unha táboa hash usa unha función hash para calcular un índice, tamén chamado código hash, nun vector de cubos ou rañuras, a partir do cal se pode atopar o valor desexado. Durante a busca, a chave dispérsase e o resultado indica onde se almacena o valor correspondente. Un mapa implementado cunha táboa hash chámase mapa hash.
A maioría dos deseños de táboas hash empregan unha función hash imperfecta. As colisións, nas que a función xera o mesmo índice para máis dunha chave, hai que xestionalas dalgún xeito. As estratexias habituais son o encadeamento separado, que almacena varios elementos no mesmo cubo con listas ligadas, e o direccionamento aberto, que busca a seguinte rañura libre segundo unha secuencia de sondaxe.
Nunha táboa hash ben dimensionada, a complexidade temporal media de cada busca é independente do número de elementos almacenados. Moitos deseños tamén permiten insercións e borrados arbitrarios de pares chave-valor, cun custo medio amortizado constante por operación.
O hashing é un exemplo de compromiso espazo-tempo. Cun universo pequeno de chaves enteiras, unha táboa de direccionamento directo pode usar a propia chave como índice, a cambio de reservar espazo para todo o universo. Unha colección desordenada require normalmente busca linear; a busca binaria necesita unha disposición ordenada e acceso eficiente ás posicións intermedias.
En moitas situacións, as táboas hash resultan de media máis eficientes cás árbores de busca ou calquera outra estrutura de consulta. Por iso úsanse amplamente no software informático, en particular para táboas asociativas, indexación de bases de datos, cachés e conxuntos. Moitas linguaxes de programación fornecen táboas hash integradas, como os dicionarios de Python, o HashMap de Java, o unordered_map de C++ ou os mapas de Go, que abstraen a complexidade do hashing para o programador.
Historia A idea do hashing xurdiu de forma independente en varios lugares. En xaneiro de 1953, Hans Peter Luhn escribiu un memorando interno de IBM que usaba hashing con encadeamento. O primeiro exemplo de direccionamento aberto foi proposto por A. D. Linh, partindo do memorando de Luhn. Na mesma época, Gene Amdahl, Elaine M. McGraw, Nathaniel Rochester e Arthur Samuel, de IBM Research, implementaron hashing para o ensamblador do IBM 701. O direccionamento aberto con sondaxe linear atribúese a Amdahl, aínda que Andrey Ershov tivo a mesma idea de forma independente. O termo «direccionamento aberto» foi acuñado por W. Wesley Peterson no seu artigo sobre a busca en ficheiros grandes.
O primeiro traballo publicado sobre hashing con encadeamento atribúese a Arnold Dumey, que discutiu a idea de usar o resto módulo un primo como función hash. A palabra «hashing» publicouse por vez primeira nun artigo de Robert Morris. A análise teórica da sondaxe linear foi presentada por Konheim e Weiss.
Visión xeral Unha táboa asociativa almacena pares (chave, valor) con chaves únicas. Unha táboa hash dispón de cubos e garda elementos. A función calcula un índice , e a comparación da chave permite distinguir entradas en colisión. Con direccionamento aberto, cada rañura almacena como máximo un elemento e ; con encadeamento separado pode haber varios elementos por cubo e pode superar . As cotas medias dependen da distribución das chaves e do factor de carga.
Factor de carga A eficiencia dunha táboa hash depende do factor de carga (), definido como a razón entre o número de elementos almacenados e o número de rañuras dispoñibles; factores de carga baixos dan lugar a operacións máis rápidas. O factor de carga é unha estatística crítica dunha táboa hash e defínese así:
onde é o número de pares chave-valor da táboa hash. é o número de cubos.
O rendemento da táboa hash deteriórase en relación co factor de carga . No límite de e grandes, cada cubo ten estatisticamente unha distribución de Poisson de esperanza para unha función hash idealmente aleatoria.
A implementación dunha táboa hash adoita garantir que o factor de carga se manteña por baixo dunha constante , o que axuda a manter un bo rendemento. Por iso, un enfoque común é redimensionar ou facer rehash da táboa cando alcanza . Do mesmo xeito, a táboa tamén se pode redimensionar se o factor de carga baixa por debaixo de .
Factor de carga con direccionamento aberto Co direccionamento aberto, cada rañura contén como máximo un elemento. Por tanto, o factor de carga non pode superar 1.James S. Plank e Brad Vander Zanden, «CS140 Lecture notes -- Hashing».
O rendemento do direccionamento aberto vólvese moi malo cando o factor de carga se aproxima a 1. Por iso, unha táboa hash que usa direccionamento aberto debe redimensionarse ou facer rehash se o factor de carga se aproxima a 1.
Co direccionamento aberto, os valores aceptables do factor de carga máximo adoitan estar entre 0,6 e 0,75.
Factor de carga con encadeamento separado Nas táboas hash con encadeamento separado, cada rañura do vector de cubos garda un punteiro a unha lista ou vector de datos.
As táboas con encadeamento separado sofren unha degradación gradual do rendemento ao aumentar o factor de carga, a diferenza da degradación abrupta do direccionamento aberto arredor de . Non hai un punto fixo respecto do factor de carga a partir do cal o redimensionamento sexa absolutamente necesario.
Co encadeamento separado, o valor de que dá mellor rendemento adoita estar entre 1 e 3.
Función hash Unha función hash asigna o universo de chaves a índices ou rañuras da táboa, é dicir, para . As implementacións convencionais de funcións hash baséanse na hipótese do universo enteiro, segundo a cal todos os elementos da táboa proveñen do universo , onde a lonxitude de bits de está dentro do tamaño de palabra dunha arquitectura de ordenador.
Unha función hash é perfecta para un conxunto se é inxectiva en , é dicir, se cada elemento se asigna a un valor distinto en . Pódese crear unha función hash perfecta se se coñecen todas as chaves de antemán.
Hipótese do universo enteiro Os esquemas de hashing usados na hipótese do universo enteiro inclúen o hashing por división, o hashing por multiplicación, o hashing universal, o hashing perfecto dinámico e o hashing perfecto estático. Con todo, o máis usado é o hashing por división.
Hashing por división O esquema do hashing por división é o seguinte:
onde é o valor hash de e é o tamaño da táboa.
Hashing por multiplicación O esquema do hashing por multiplicación é o seguinte:
onde é unha constante real non enteira e é o tamaño da táboa. Unha vantaxe do hashing por multiplicación é que non é crítico. Aínda que calquera valor produce unha función hash, Donald Knuth suxire usar o número áureo.
Hashing de cadeas Habitualmente úsase unha cadea como chave da función hash. A terceira edición de The C++ Programming Language describe unha función hash simple na que un enteiro sen signo que comeza en cero se despraza á esquerda un bit repetidamente e se combina con XOR co valor enteiro do seguinte carácter; o resultado tómase despois módulo o tamaño da táboa. Se o desprazamento á esquerda non é circular, ao procesar unha cadea longa poden perderse as contribucións dos primeiros caracteres por desbordamento do enteiro. Outra forma común de converter unha cadea nun enteiro é cunha función hash polinómica continua.
Escoller unha función hash A distribución uniforme dos valores hash é un requisito fundamental. Unha distribución non uniforme aumenta o número de colisións e o custo de resolvelas. A uniformidade ás veces é difícil de garantir por deseño, pero pódese avaliar empiricamente con probas estatísticas, como a proba chi cadrado de Pearson para distribucións uniformes discretas.
A distribución só ten que ser uniforme para os tamaños de táboa que ocorren na aplicación. En particular, se se usa un redimensionamento dinámico con duplicación e división exactas, a función hash só ten que ser uniforme cando o tamaño é unha potencia de dous. Aquí o índice pódese calcular como un rango de bits da función hash. Pola contra, algúns algoritmos de hashing prefiren que o tamaño sexa un número primo.
Para os esquemas de direccionamento aberto, a función hash tamén debería evitar as secuencias, a asignación de dúas ou máis chaves a rañuras consecutivas. Tales secuencias poden disparar o custo da busca, mesmo cun factor de carga baixo e colisións pouco frecuentes. O popular hashing multiplicativo ten, segundo se afirma, un comportamento particularmente pobre en canto a secuencias.
O hashing K-independente describe familias de funcións das que se escolle unha ao azar: para calquera conxunto de chaves distintas, os seus valores hash teñen a independencia e uniformidade requiridas. Esta propiedade permite análises probabilísticas; non garante que cada función concreta da familia careza de conxuntos de chaves problemáticos.
Resolución de colisións Un algoritmo de busca que usa hashing consta de dúas partes: calcular unha función hash que transforma a chave de busca nun índice de vector, e a resolución de colisións. O ideal é que dúas chaves de busca non se dispersen ao mesmo índice, pero non sempre é así e é imposible de garantir para datos non vistos. Os dous métodos comúns de resolución de colisións son o encadeamento separado e o direccionamento aberto.
Encadeamento separado miniatura|450px|dereita|alt=Colisión hash resolta por encadeamento separado.|Colisión hash resolta por encadeamento separado. miniatura|dereita|500px|alt=Colisión resolta por encadeamento separado con rexistros de cabeza no vector de cubos.|Colisión por encadeamento separado con rexistros de cabeza no vector de cubos.
No encadeamento separado, o proceso consiste en construír unha lista ligada de pares chave-valor para cada índice do vector de busca. Os elementos en colisión encadéanse nunha única lista ligada, que se percorre durante a busca dunha chave concreta. Sexa a táboa hash, un elemento e a súa chave. As operacións son as seguintes:
Chained-Hash-Insert(T, x) inserir x na cabeza da lista ligada T[h(k)]
Chained-Hash-Search(T, k) buscar un elemento coa chave k na lista ligada T[h(k)]
Chained-Hash-Delete(T, x) borrar x da lista ligada T[h(k)]
Se o elemento é comparable numericamente ou lexicamente e se insire na lista mantendo a orde total, as buscas sen éxito rematan antes.
Outras estruturas de datos para o encadeamento separado Se as chaves están ordenadas, pode ser eficiente usar conceptos «autoorganizados», como usar unha árbore binaria de busca auto-equilibrada, coa que o peor caso teórico se pode baixar a , aínda que introduce complexidade adicional.
No hashing perfecto dinámico, úsanse táboas hash de dous niveis para reducir a complexidade da busca a un garantido no peor caso. Nesta técnica, os cubos de entradas organízanse como táboas hash perfectas con rañuras, o que dá un tempo de busca constante no peor caso e un tempo amortizado baixo para a inserción. Askitis e Zobel compararon o encadeamento con listas de nós con representacións máis compactas, como vectores contiguos de caracteres, e observaron menos memoria empregada e menores tempos de acceso nos seus experimentos con grandes conxuntos de cadeas.
Técnicas como usar unha árbore de fusión para cada cubo tamén dan tempo constante para todas as operacións con alta probabilidade..
Caché e localidade de referencia As listas ligadas no encadeamento separado poden ter unha localidade de referencia pobre cando os nós están espallados pola memoria, polo que o percorrido da lista durante a inserción e a busca pode implicar ineficiencias da caché da CPU.