Táboa hash

	Instancia de estrutura de datos
	Subclase de vector asociativo
	Medio usado función hash criptográfica; collision resolution scheme (en)

Táboa hash
	Instancia de estrutura de datos
	Subclase de vector asociativo
	Medio usado función hash criptográfica; collision resolution scheme (en)
Datas
	Fundación / creación 1953
	Descuberta / invención 1953
Freebase
Fontes e ligazóns
Freebase
Freebase	/m/03llm
MathWorld	HashTable
OpenAlex	C67388219
	Wikidata C:Commons

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.^[1] 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.^[2]

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.^[3]^[2]^:513–558^[4]

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.^[5]

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.^[6] 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.^[7]

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.^[2]^:{{{1}}} Na mesma época, Gene Amdahl, Elaine M. McGraw, Nathaniel Rochester e Arthur Samuel, de IBM Research, implementaron hashing para o ensamblador do IBM 701.^[8] O direccionamento aberto con sondaxe linear atribúese a Amdahl, aínda que Andrey Ershov tivo a mesma idea de forma independente.^[8]^:124–125 O termo «direccionamento aberto» foi acuñado por W. Wesley Peterson no seu artigo sobre a busca en ficheiros grandes.^[9]^:{{{1}}}

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.^[9]^:15 A palabra «hashing» publicouse por vez primeira nun artigo de Robert Morris.^[8]^:126 A análise teórica da sondaxe linear foi presentada por Konheim e Weiss.^[9]^:15

Visión xeral

Unha táboa asociativa almacena pares (chave, valor) con chaves únicas. Unha táboa hash dispón de $m$ cubos e garda $n$ elementos. A función $h$ calcula un índice $0\leq h(x)<m$ , 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 $n\leq m$ ; con encadeamento separado pode haber varios elementos por cubo e $n$ pode superar $m$ . As cotas medias dependen da distribución das chaves e do factor de carga.^[9]^:1

Factor de carga

A eficiencia dunha táboa hash depende do factor de carga ( $\alpha$ ), 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.^[10] O factor de carga é unha estatística crítica dunha táboa hash e defínese así:^[11]

{\text{factor de carga}}\ (\alpha )={\frac {n}{m}},

onde

$n$ é o número de pares chave-valor da táboa hash.
$m$ é o número de cubos.

O rendemento da táboa hash deteriórase en relación co factor de carga $\alpha$ .^[9]^:2 No límite de $m$ e $n$ grandes, cada cubo ten estatisticamente unha distribución de Poisson de esperanza $\lambda =\alpha$ para unha función hash idealmente aleatoria.

A implementación dunha táboa hash adoita garantir que o factor de carga $\alpha$ se manteña por baixo dunha constante $\alpha _{\max }$ , o que axuda a manter un bo rendemento. Por iso, un enfoque común é redimensionar ou facer rehash da táboa cando $\alpha$ alcanza $\alpha _{\max }$ . Do mesmo xeito, a táboa tamén se pode redimensionar se o factor de carga baixa por debaixo de $\alpha _{\max }/4$ .^[12]

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.^[13]

O rendemento do direccionamento aberto vólvese moi malo cando o factor de carga se aproxima a 1.^[12] Por iso, unha táboa hash que usa direccionamento aberto debe redimensionarse ou facer rehash se o factor de carga $\alpha$ se aproxima a 1.^[12]

Co direccionamento aberto, os valores aceptables do factor de carga máximo $\alpha _{\max }$ adoitan estar entre 0,6 e 0,75.^[14]^[15]

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.^[13]

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 $\alpha =1$ . Non hai un punto fixo respecto do factor de carga a partir do cal o redimensionamento sexa absolutamente necesario.^[12]

Co encadeamento separado, o valor de $\alpha _{\max }$ que dá mellor rendemento adoita estar entre 1 e 3.^[12]

Función hash

Unha función hash $h:U\rightarrow \{0,...,m-1\}$ asigna o universo $U$ de chaves a índices ou rañuras da táboa, é dicir, $h(x)\in \{0,...,m-1\}$ para $x\in U$ . 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 $U=\{0,...,u-1\}$ , onde a lonxitude de bits de $u$ está dentro do tamaño de palabra dunha arquitectura de ordenador.^[9]^:2

Unha función hash $h$ é perfecta para un conxunto $S$ se é inxectiva en $S$ , é dicir, se cada elemento $x\in S$ se asigna a un valor distinto en $\{0,...,m-1\}$ .^[16]^[17] Pódese crear unha función hash perfecta se se coñecen todas as chaves de antemán.^[16]

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.^[9]^:2 Con todo, o máis usado é o hashing por división.^[18]^[15]^:{{{1}}}

Hashing por división

O esquema do hashing por división é o seguinte:^[9]^:2

h(x)\ =\ x\,{\bmod {\,}}m,

onde $h(x)$ é o valor hash de $x\in S$ e $m$ é o tamaño da táboa.

Hashing por multiplicación

O esquema do hashing por multiplicación é o seguinte:^[9]^:2-3

h(x)=\lfloor m((xA){\bmod {1}})\rfloor

onde $A$ é unha constante real non enteira e $m$ é o tamaño da táboa. Unha vantaxe do hashing por multiplicación é que $m$ non é crítico.^[9]^:2-3 Aínda que calquera valor $A$ produce unha función hash, Donald Knuth suxire usar o número áureo.^[9]^:3

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.^[19] 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.^[20]^[21]

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.^[22]

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.^[22]^[2]

O hashing K-independente describe familias de funcións das que se escolle unha ao azar: para calquera conxunto de $k$ 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.^[23]

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.^[2]^:{{{1}}} Os dous métodos comúns de resolución de colisións son o encadeamento separado e o direccionamento aberto.^[5]^:{{{1}}}

Encadeamento separado

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.^[5]^:464 Sexa $T$ a táboa hash, $x$ un elemento $(k,v)$ e $k$ a súa chave. As operacións son as seguintes:^[18]^:{{{1}}}

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.^[2]^:520-521

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 $O(\log {n})$ , aínda que introduce complexidade adicional.^[2]^:521

No hashing perfecto dinámico, úsanse táboas hash de dous niveis para reducir a complexidade da busca a un $O(1)$ garantido no peor caso. Nesta técnica, os cubos de $k$ entradas organízanse como táboas hash perfectas con $k^{2}$ rañuras, o que dá un tempo de busca constante no peor caso e un tempo amortizado baixo para a inserción.^[24] 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.^[25]

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.^[26]

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.^[25]^:{{{1}}}

Nas variantes sensibles á caché da resolución de colisións por encadeamento separado, emprégase un vector dinámico máis amigable coa caché da CPU no lugar onde adoita haber unha lista ligada ou unha árbore binaria de busca auto-equilibrada, xa que o patrón de asignación contigua pode ser aproveitado polos prebuscadores de caché de hardware, o que reduce o tempo de acceso e o consumo de memoria.^[27]^[25]^[28]

Direccionamento aberto

O direccionamento aberto é outra técnica de resolución de colisións na que cada rexistro se almacena no propio vector de cubos e a resolución faise mediante sondaxe. Cando hai que inserir unha nova entrada, examínanse os cubos comezando pola rañura calculada e avanzando segundo unha secuencia de sondaxe ata atopar unha posición dispoñible. Ao buscar unha entrada, examínanse os cubos na mesma orde. Unha rañura nunca ocupada permite concluír que a chave non existe; en cambio, se se usan marcas de borrado, hai que continuar a busca ao atopar unha delas.^[29]^[30]

As secuencias de sondaxe coñecidas inclúen:

Sondaxe linear, na que o intervalo entre sondaxes é fixo (normalmente 1).^[31]
Sondaxe cuadrática, na que a posición da sondaxe $i$ se calcula como $(h(k)+c_{1}i+c_{2}i^{2}){\bmod {m}}$ , con constantes axeitadas ao tamaño da táboa. O desprazamento respecto da posición inicial é cuadrático; non se suman sucesivamente desprazamentos cuadráticos.^[30]
Dobre hashing, no que o intervalo entre sondaxes se calcula cunha función hash secundaria.^[30]^:272-273

O rendemento do direccionamento aberto pode ser máis lento cá do encadeamento separado, porque a secuencia de sondaxe aumenta cando o factor de carga $\alpha$ se aproxima a 1.^[12]^[25]^:93 Nunha táboa completamente chea, unha inserción debe detectar o esgotamento das posicións da secuencia de sondaxe e fallar ou redimensionar a táboa; só unha implementación que espere indefinidamente unha rañura baleira entraría nun bucle infinito.^[30] O custo medio da sondaxe linear depende de que a función hash distribúa os elementos uniformemente para evitar secuencias longas, xa que a súa formación aumentaría o tempo de busca.^[5]^:472

Caché e localidade de referencia

Como as rañuras están en posicións sucesivas, a sondaxe linear pode levar a unha mellor utilización da caché da CPU pola localidade de referencia, o que reduce a latencia de memoria.^[31]

Outras técnicas de resolución de colisións baseadas no direccionamento aberto

Hashing coalescido

O hashing coalescido é un híbrido de encadeamento separado e direccionamento aberto.^[32]^:6–8 Cando un elemento que se insire se dispersa a un cubo ocupado, insírese na rañura libre de maior índice da táboa hash, e o cubo orixinal enlázase con esa rañura mediante un punteiro seguinte.^[32]^:8 O hashing coalescido é ideal para a asignación de memoria fixa.^[32]^:4

Hashing cuckoo

O hashing cuckoo é unha forma de resolución de colisións por direccionamento aberto que garante unha complexidade de busca $O(1)$ no peor caso. O custo constante das insercións é esperado e amortizado, baixo as hipóteses sobre a elección das funcións hash e a carga da táboa. A construción clásica mantén dúas táboas, cada unha coa súa función hash: unha inserción pode substituír un elemento ocupado e desprazalo á súa posición na outra táboa. Se se supera un límite de desprazamentos sen atopar unha posición libre, reconstrúense as táboas con novas funcións hash.^[31]^:124–125

Hashing hopscotch

O hashing hopscotch é un algoritmo baseado no direccionamento aberto que combina elementos do hashing cuckoo, a sondaxe linear e o encadeamento separado mediante a noción dunha veciñanza de cubos: os cubos sucesivos arredor dun cubo ocupado dado, tamén chamado cubo «virtual».^[33]^:351–352 O algoritmo está deseñado para dar mellor rendemento cando o factor de carga supera o 90 %; tamén ofrece alto rendemento en contornos concorrentes, polo que é axeitado para implementar táboas hash redimensionables.^[33]^:350 A característica de veciñanza do hashing hopscotch garante que o custo de atopar o elemento desexado desde calquera cubo dentro da veciñanza é moi próximo ao custo de atopalo no propio cubo.^[33]^:352

Cada cubo da táboa inclúe unha «información de salto» adicional: un vector de bits de H bits que indica a distancia relativa do elemento que se dispersou orixinalmente no cubo virtual actual dentro de H−1 entradas.^[33]^:352

Hashing de Robin Hood

O hashing de Robin Hood é un algoritmo de resolución de colisións baseado no direccionamento aberto. Ante unha colisión, o elemento cunha lonxitude de secuencia de sondaxe (PSL) maior ten preferencia para ocupar a rañura; o elemento coa PSL menor continúa a sondaxe. Así favorécese o que xa percorreu máis posicións.^[34]^:{{{1}}} Recibe o nome de Robin Hood, un foraxido heroico mítico que roubaba aos ricos para dar aos pobres.

A política Robin Hood reduce a varianza das lonxitudes de sondaxe,^[34]^:2 o que non equivale a eliminar os bloques contiguos de rañuras ocupadas na sondaxe linear. A implementación pode gardar a PSL de cada entrada para comparala coa do elemento que se está inserindo.^[35] Sexa $x$ a chave que se vai inserir, $x.{\text{psl}}$ a súa lonxitude PSL (incremental), $T$ a táboa hash e $j$ o índice; o procedemento de inserción é o seguinte:^[34]^:12-13

Se $T[j]$ está baleiro, gárdase nel $x$ e a inserción remata.
Se está ocupado e $x.{\text{psl}}\leq T[j].{\text{psl}}$ , avánzase ao seguinte cubo e increméntase a lonxitude de sondaxe de $x$ .
Se está ocupado e $x.{\text{psl}}>T[j].{\text{psl}}$ , intercámbiase $x$ co elemento de $T[j]$ . Continúase coa inserción do elemento desprazado no cubo seguinte, incrementando a súa lonxitude de sondaxe, ata atopar unha rañura baleira.

Redimensionamento dinámico

As insercións repetidas fan medrar o número de entradas dunha táboa hash, o que aumenta o factor de carga; para manter o rendemento amortizado $O(1)$ das operacións de busca e inserción, a táboa redimensiónase dinamicamente e os elementos reháshense nos cubos da nova táboa.^[12] Os elementos non se poden copiar simplemente aos mesmos índices, porque a función hash depende do tamaño da táboa. Se unha táboa queda «demasiado baleira» tras borrar algúns elementos, pódese redimensionar para evitar un consumo excesivo de memoria.^[36]

Redimensionamento movendo todas as entradas

Xeralmente resérvase unha nova táboa hash co dobre de tamaño e móvese a ela cada elemento da orixinal calculando os seus valores hash e inseríndoos. O rehashing é simple, pero custoso computacionalmente.^[37]^:478–479

Alternativas ao rehashing de golpe

Algunhas implementacións, en particular en sistemas de tempo real, non poden pagar o custo de ampliar a táboa de golpe, porque interrompería operacións críticas. Se non se pode evitar o redimensionamento dinámico, unha solución é facelo gradualmente para evitar un salto de almacenamento —normalmente ao 50 % do tamaño da nova táboa— e evitar a fragmentación que desencadea a compactación do heap.^[38]^:2–3 Nese caso, o rehashing faise de forma incremental estendendo o bloque de memoria reservado para a táboa antiga, de xeito que os cubos quedan inalterados. Un enfoque común para o rehashing amortizado consiste en manter dúas funcións hash, $h_{\text{old}}$ e $h_{\text{new}}$ . O proceso de rehashear os elementos dun cubo segundo a nova función chámase limpeza, que se implementa mediante o patrón de orde encapsulando as operacións $\mathrm {Add} (\mathrm {key} )$ , $\mathrm {Get} (\mathrm {key} )$ e $\mathrm {Delete} (\mathrm {key} )$ nun envoltorio $\mathrm {Lookup} (\mathrm {key} ,{\text{command}})$ , de xeito que cada elemento:

Limpa o cubo $\mathrm {Table} [h_{\text{old}}(\mathrm {key} )]$ .
Limpa o cubo $\mathrm {Table} [h_{\text{new}}(\mathrm {key} )]$ .
A orde execútase.

Hashing linear

O hashing linear é unha implementación da táboa hash que permite que esta medre ou diminúa un cubo á vez.^[39]

Rendemento

O rendemento depende da distribución das chaves entre os cubos, do factor de carga e do método de resolución de colisións. Un custo esperado $O(1)$ non require ausencia de colisións: no encadeamento separado, baixo hashing uniforme e cun factor de carga acoutado, a lonxitude esperada das cadeas permanece constante. O custo de calcular o hash e comparar chaves tamén debe terse en conta, especialmente para chaves de lonxitude variable.^[30]^[40]

O mellor rendemento obtense cando a función hash distribúe uniformemente os elementos do universo e os elementos almacenados se extraen ao azar do universo. Nese caso, no hashing con encadeamento, o tempo esperado dunha busca con éxito é $1+{\frac {\alpha }{2}}+\Theta \left({\frac {1}{m}}\right)$ , e o dunha busca sen éxito é $e^{-\alpha }+\alpha +\Theta \left({\frac {1}{m}}\right)$ .^[41]

Aplicacións

Táboas asociativas

As táboas hash úsanse habitualmente para implementar moitos tipos de táboas en memoria, incluídas as táboas asociativas.^[30]

Indexación de bases de datos

As táboas hash tamén se poden usar como estruturas de datos en disco e como índices de bases de datos (como en DBM), aínda que as árbores-B son máis populares nestas aplicacións.^[42]

Cachés

As táboas hash pódense usar para implementar cachés, táboas auxiliares que aceleran o acceso a datos almacenados en medios máis lentos. Nunha caché de correspondencia directa, se dúas chaves corresponden á mesma rañura, a nova entrada pode substituír a anterior; non permanecen ambas na rañura ao mesmo tempo, aínda que as chaves sigan tendo o mesmo índice hash.^[43]

Conxuntos

As táboas hash pódense empregar na implementación da estrutura de datos conxunto, que almacena valores únicos sen unha orde particular; os conxuntos empréganse tipicamente para comprobar a pertenza dun valor a unha colección, máis ca para recuperar elementos.^[44] As táboas hash empréganse como conxuntos omitindo o valor almacenado para cada chave e rexistrando só se a chave está presente.^[9]^:1

Táboa de transposición

As táboas de transposición, que almacenan posicións xa vistas e as súas avaliacións nunha árbore de busca, como unha árbore de xogo, adóitanse implementar como táboas hash.

Implementacións

Moitas linguaxes de programación fornecen funcionalidade de táboa hash, ben como táboas asociativas integradas, ben como módulos da biblioteca estándar.

En JavaScript, un «obxecto» é unha colección mutable de pares chave-valor (chamados «propiedades»), onde cada chave é unha cadea ou un «símbolo» único garantido.^[45] ECMAScript 2015 engadiu a estrutura Map, que acepta valores arbitrarios como chaves.^[46]
C++11 inclúe unordered_map na súa biblioteca estándar para almacenar chaves e valores de tipos arbitrarios.^[47]
O map integrado de Go implementa un tipo mapa, que a miúdo (pero non garantidamente) é unha táboa hash.^[48]
A linguaxe de programación Java inclúe as coleccións xenéricas HashSet, HashMap, LinkedHashSet e LinkedHashMap.^[49]
O dict integrado de Python impleméntase como táboa hash redimensionable en CPython.^[50]
O Hash integrado de Ruby usa o modelo de direccionamento aberto desde Ruby 2.4.^[51]
A linguaxe Rust inclúe HashMap e HashSet como parte da súa biblioteca estándar.^[52]
A biblioteca estándar de .NET inclúe HashSet e Dictionary,^[53]^[54] polo que se poden usar desde linguaxes como C# e VB.NET.^[55]

Notas

Nota: existen enfoques cunha complexidade temporal esperada no peor caso de O(log² (1 − α)⁻¹), onde α é o factor de carga.^[56]

↑ Mehlhorn, Kurt; Sanders, Peter (2008). "Hash Tables and Associative Arrays" (PDF). Algorithms and Data Structures (en inglés). Springer. pp. 81–98. ISBN 978-3-540-77977-3. doi:10.1007/978-3-540-77978-0_4.
1 2 3 4 5 6 7 Knuth, Donald E. (24 de abril de 1998). The Art of Computer Programming: Volume 3: Sorting and Searching (en inglés) (2.ª ed.). Addison-Wesley Professional. ISBN 978-0-201-89685-5.
↑ Leiserson, Charles E. (outono de 2005). "Lecture 13: Amortized Algorithms, Table Doubling, Potential Method". curso MIT 6.046J/18.410J Introduction to Algorithms (en inglés).
↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Chapter 11: Hash Tables". Introduction to Algorithms (en inglés) (2.ª ed.). MIT Press and McGraw-Hill. pp. 221–252. ISBN 978-0-262-53196-2.
1 2 3 4 Sedgewick, Robert; Wayne, Kevin (2011). Algorithms (en inglés) 1 (4.ª ed.). Addison-Wesley Professional.
↑ Silberschatz, A.; Korth, H. F.; Sudarshan, S. (2020). Database System Concepts (en inglés) (7.ª ed.). McGraw-Hill.
↑ Goodrich, M. T.; Tamassia, R.; Goldwasser, M. H. (2014). Data Structures and Algorithms in Java (en inglés) (6.ª ed.). Wiley.
1 2 3 Konheim, Alan G. (2010). Hashing in Computer Science (en inglés). ISBN 978-0-470-34473-6. doi:10.1002/9780470630617.
1 2 3 4 5 6 7 8 9 10 11 12 Mehta, Dinesh P.; Sahni, Sartaj, eds. (2004). Handbook of Data Structures and Applications (en inglés). ISBN 978-0-429-14701-2. doi:10.1201/9781420035179.
↑ Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C. (2009). Introduction to Algorithms (en inglés) (3.ª ed.). MIT Press.
↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms (en inglés) (3.ª ed.). MIT Press. pp. 253–280. ISBN 978-0-262-03384-8.
1 2 3 4 5 6 7 Mayers, Andrew (2008). "CS 312: Hash tables and amortized analysis" (en inglés). Cornell University, Department of Computer Science.
1 2 James S. Plank e Brad Vander Zanden, «CS140 Lecture notes -- Hashing».
↑ Maurer, W. D.; Lewis, T. G. (marzo de 1975). "Hash Table Methods". ACM Computing Surveys (en inglés) 7 (1): 5–19. doi:10.1145/356643.356645.
1 2 Owolabi, Olumide (febreiro de 2003). "Empirical studies of some hashing functions". Information and Software Technology (en inglés) 45 (2): 109–112. doi:10.1016/S0950-5849(02)00174-X.
1 2 Lu, Yi; Prabhakar, Balaji; Bonomi, Flavio (2006). Perfect Hashing for Network Applications. 2006 IEEE International Symposium on Information Theory (en inglés). pp. 2774–2778. ISBN 1-4244-0505-X. doi:10.1109/ISIT.2006.261567.
↑ Belazzougui, Djamal; Botelho, Fabiano C.; Dietzfelbinger, Martin (2009). "Hash, displace, and compress" (PDF). Algorithms—ESA 2009: 17th Annual European Symposium, Copenhagen, Denmark, September 7–9, 2009, Proceedings. Lecture Notes in Computer Science (en inglés). Berlín: Springer. pp. 682–693. doi:10.1007/978-3-642-04128-0_61.
1 2 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). "11: Hash Tables". Introduction to Algorithms (en inglés) (3.ª ed.). MIT Press. ISBN 978-0-262-03384-8.
↑ Stroustrup, Bjarne (1997). The C++ Programming Language Third Edition (en inglés). Reading Massachusetts: Addison-Wesley. p. 503. ISBN 0-201-88954-4.
↑ Pearson, Karl (1900). "On the criterion that a given system of deviations from the probable in the case of a correlated system of variables is such that it can be reasonably supposed to have arisen from random sampling". Philosophical Magazine. Series 5 (en inglés) 50 (302): 157–175. doi:10.1080/14786440009463897.
↑ Plackett, Robin (1983). "Karl Pearson and the Chi-Squared Test". International Statistical Review (en inglés) 51 (1): 59–72. doi:10.2307/1402731.
1 2 Wang, Thomas (marzo de 1997). "Prime Double Hash Table" (en inglés). Arquivado dende o orixinal o 03 de setembro de 1999. Consultado o 20 de setembro de 2026.
↑ Wegman, Mark N.; Carter, J. Lawrence (xuño de 1981). "New hash functions and their use in authentication and set equality". Journal of Computer and System Sciences (en inglés) 22 (3): 265–279. doi:10.1016/0022-0000(81)90033-7.
↑ Demaine, Erik; Lind, Jeff (primavera de 2003). "Lecture 2" (PDF). 6.897: Advanced Data Structures. MIT Computer Science and Artificial Intelligence Laboratory (en inglés).
1 2 3 4 Askitis, Nikolas; Zobel, Justin (outubro de 2005). "Cache-Conscious Collision Resolution in String Hash Tables". String Processing and Information Retrieval (SPIRE 2005). Lecture Notes in Computer Science (en inglés). pp. 91–102. ISBN 978-3-540-29740-6. doi:10.1007/11575832_11.
↑ Willard, Dan E. (2000). "Examining computational geometry, van Emde Boas trees, and hashing from the perspective of the fusion tree". SIAM Journal on Computing (en inglés) 29 (3): 1030–1049. doi:10.1137/S0097539797322425. .
↑ Askitis, Nikolas; Sinha, Ranjan (outubro de 2010). "Engineering scalable, cache and space efficient tries for strings". The VLDB Journal (en inglés) 19 (5): 633–660. doi:10.1007/s00778-010-0183-9.
↑ Askitis, Nikolas (2009). "Fast and Compact Hash Tables for Integer Keys" (PDF). Proceedings of the 32nd Australasian Computer Science Conference (ACSC 2009) (en inglés). pp. 113–122. ISBN 978-1-920682-72-9.
↑ Tenenbaum, Aaron M.; Langsam, Yedidyah; Augenstein, Moshe J. (1990). Data Structures Using C (en inglés). Prentice Hall. pp. 456–461, p. 472. ISBN 978-0-13-199746-2.
1 2 3 4 5 6 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). "11: Hash Tables". Introduction to Algorithms (en inglés) (3.ª ed.). MIT Press. pp. 253–285. ISBN 978-0-262-03384-8.
1 2 3 Pagh, Rasmus; Rodler, Flemming Friche (2001). "Cuckoo Hashing". Algorithms — ESA 2001. Lecture Notes in Computer Science (en inglés) 2161. pp. 121–133. ISBN 978-3-540-42493-2. doi:10.1007/3-540-44676-1_10.
1 2 3 Vitter, Jeffery S.; Chen, Wen-Chin (1987). The design and analysis of coalesced hashing (en inglés). Nova York: Oxford University Press. ISBN 978-0-19-504182-8.
1 2 3 4 Herlihy, Maurice; Shavit, Nir; Tzafrir, Moran (2008). "Hopscotch Hashing". Distributed Computing. Lecture Notes in Computer Science (en inglés) 5218. pp. 350–364. ISBN 978-3-540-87778-3. doi:10.1007/978-3-540-87779-0_24.
1 2 3 Celis, Pedro (1986). Robin Hood Hashing (PDF) (en inglés). Ontario, Canadá: University of Waterloo, Dept. of Computer Science. ISBN 978-0-315-29700-5.
↑ Gries, David (2017). "JavaHyperText and Data Structure: Robin Hood Hashing" (PDF) (en inglés). Cornell University, Department of Computer Science.
↑ Devadas, Srini; Demaine, Erik (25 de febreiro de 2011). "Intro to Algorithms: Resizing Hash Tables" (PDF) (en inglés). Massachusetts Institute of Technology.
↑ Thareja, Reema (2014). "Hashing and Collision". Data Structures Using C (en inglés). Oxford University Press. pp. 464–488. ISBN 978-0-19-809930-7.
↑ Friedman, Scott; Krishnan, Anand; Leidefrost, Nicholas (18 de marzo de 2003). "Hash Tables for Embedded and Real-time systems" (PDF). All Computer Science and Engineering Research (en inglés) (Washington University in St. Louis). doi:10.7936/K7WD3XXV.
↑ Litwin, Witold (1980). "Linear hashing: A new tool for file and table addressing" (PDF). Proc. 6th Conference on Very Large Databases (en inglés). Carnegie Mellon University. pp. 212–223.
↑ Dijk, Tom Van (2010). "Analysing and Improving Hash Table Performance" (PDF) (en inglés). Países Baixos: University of Twente.
↑ Baeza-Yates, Ricardo; Poblete, Patricio V. (1999). "Chapter 2: Searching". En Atallah. Algorithms and Theory of Computation Handbook (en inglés). CRC Press. pp. 2–6. ISBN 0849326494.
↑ Banachowski, Lech. "Indexes and external sorting" (en inglés). Polsko-Japońska Akademia Technik Komputerowych. ^{[Ligazón morta]}
↑ Bottomley, James (1 de xaneiro de 2004). "Understanding Caching" (en inglés). Linux Journal.
↑ Seaman, Jill (2014). "Set & Hash Tables" (PDF) (en inglés). Texas State University.
↑ "JavaScript data types and data structures - JavaScript | MDN". developer.mozilla.org (en inglés).
↑ "Map - JavaScript | MDN". developer.mozilla.org (en inglés). 20 de xuño de 2023.
↑ "Programming language C++ - Technical Specification" (PDF) (en inglés). International Organization for Standardization. pp. 812–813.
↑ "The Go Programming Language Specification". go.dev (en inglés).
↑ "Lesson: Implementations (The Java Tutorials > Collections)". docs.oracle.com (en inglés).
↑ "Design and History FAQ: How are dictionaries implemented in CPython?". Python Documentation (en inglés). Python Software Foundation.
↑ Scheffler, Jonan (25 de decembro de 2016). "Ruby 2.4 Released: Faster Hashes, Unified Integers and Better Rounding". heroku.com (en inglés).
↑ "doc.rust-lang.org" (en inglés).
↑ "HashSet Class (System.Collections.Generic)". learn.microsoft.com (en inglés).
↑ "Dictionary Class (System.Collections.Generic)". learn.microsoft.com (en inglés).
↑ "VB.NET HashSet Example". Dot Net Perls (en inglés).
↑ Farach-Colton, Martin; Krapivin, Andrew; Kuszmaul, William (2024). "Optimal Bounds for Open Addressing Without Reordering". 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) (en inglés). IEEE. pp. 594–605. arXiv:2501.02305. doi:10.1109/FOCS61266.2024.00045.

Véxase tamén

Bibliografía

Tamassia, Roberto; Goodrich, Michael T. (2006). "Chapter Nine: Maps and Dictionaries". Data structures and algorithms in Java: [updated for Java 5.0] (en inglés) (4.ª ed.). Hoboken, NJ: Wiley. pp. 369–418. ISBN 978-0-471-73884-8.
McKenzie, B. J.; Harries, R.; Bell, T. (febreiro de 1990). "Selecting a hashing algorithm". Software: Practice and Experience (en inglés) 20 (2): 209–224. doi:10.1002/spe.4380200207.

Outros artigos

Filtro de Bloom

Ligazóns externas

Táboas hash en Wikimedia Commons (en inglés)
Entrada sobre táboas hash do NIST (en inglés)
Open Data Structures – Capítulo 5 – Hash Tables, Pat Morin (en inglés)

[ms-1] Mehlhorn, Kurt; Sanders, Peter (2008). "Hash Tables and Associative Arrays" (PDF). Algorithms and Data Structures (en inglés). Springer. pp. 81–98. ISBN 978-3-540-77977-3. doi:10.1007/978-3-540-77978-0_4.

[knuth-2] 1 2 3 4 5 6 7 Knuth, Donald E. (24 de abril de 1998). The Art of Computer Programming: Volume 3: Sorting and Searching (en inglés) (2.ª ed.). Addison-Wesley Professional. ISBN 978-0-201-89685-5.

[leiser-3] Leiserson, Charles E. (outono de 2005). "Lecture 13: Amortized Algorithms, Table Doubling, Potential Method". curso MIT 6.046J/18.410J Introduction to Algorithms (en inglés).

[cormen-4] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Chapter 11: Hash Tables". Introduction to Algorithms (en inglés) (2.ª ed.). MIT Press and McGraw-Hill. pp. 221–252. ISBN 978-0-262-53196-2.

[algo1rob-5] 1 2 3 4 Sedgewick, Robert; Wayne, Kevin (2011). Algorithms (en inglés) 1 (4.ª ed.). Addison-Wesley Professional.

[6] Silberschatz, A.; Korth, H. F.; Sudarshan, S. (2020). Database System Concepts (en inglés) (7.ª ed.). McGraw-Hill.

[7] Goodrich, M. T.; Tamassia, R.; Goldwasser, M. H. (2014). Data Structures and Algorithms in Java (en inglés) (6.ª ed.). Wiley.

[Konheim-8] 1 2 3 Konheim, Alan G. (2010). Hashing in Computer Science (en inglés). ISBN 978-0-470-34473-6. doi:10.1002/9780470630617.

[hashhist-9] 1 2 3 4 5 6 7 8 9 10 11 12 Mehta, Dinesh P.; Sahni, Sartaj, eds. (2004). Handbook of Data Structures and Applications (en inglés). ISBN 978-0-429-14701-2. doi:10.1201/9781420035179.

[10] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C. (2009). Introduction to Algorithms (en inglés) (3.ª ed.). MIT Press.

[Cormen_et_al-11] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms (en inglés) (3.ª ed.). MIT Press. pp. 253–280. ISBN 978-0-262-03384-8.

[cornell08-12] 1 2 3 4 5 6 7 Mayers, Andrew (2008). "CS 312: Hash tables and amortized analysis" (en inglés). Cornell University, Department of Computer Science.

[plank-13] 1 2 James S. Plank e Brad Vander Zanden, «CS140 Lecture notes -- Hashing».

[14] Maurer, W. D.; Lewis, T. G. (marzo de 1975). "Hash Table Methods". ACM Computing Surveys (en inglés) 7 (1): 5–19. doi:10.1145/356643.356645.

[owo03-15] 1 2 Owolabi, Olumide (febreiro de 2003). "Empirical studies of some hashing functions". Information and Software Technology (en inglés) 45 (2): 109–112. doi:10.1016/S0950-5849(02)00174-X.

[Yi06-16] 1 2 Lu, Yi; Prabhakar, Balaji; Bonomi, Flavio (2006). Perfect Hashing for Network Applications. 2006 IEEE International Symposium on Information Theory (en inglés). pp. 2774–2778. ISBN 1-4244-0505-X. doi:10.1109/ISIT.2006.261567.

[CHD-17] Belazzougui, Djamal; Botelho, Fabiano C.; Dietzfelbinger, Martin (2009). "Hash, displace, and compress" (PDF). Algorithms—ESA 2009: 17th Annual European Symposium, Copenhagen, Denmark, September 7–9, 2009, Proceedings. Lecture Notes in Computer Science (en inglés). Berlín: Springer. pp. 682–693. doi:10.1007/978-3-642-04128-0_61.

[cormenalgo01-18] 1 2 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). "11: Hash Tables". Introduction to Algorithms (en inglés) (3.ª ed.). MIT Press. ISBN 978-0-262-03384-8.

[19] Stroustrup, Bjarne (1997). The C++ Programming Language Third Edition (en inglés). Reading Massachusetts: Addison-Wesley. p. 503. ISBN 0-201-88954-4.

[chernoff-20] Pearson, Karl (1900). "On the criterion that a given system of deviations from the probable in the case of a correlated system of variables is such that it can be reasonably supposed to have arisen from random sampling". Philosophical Magazine. Series 5 (en inglés) 50 (302): 157–175. doi:10.1080/14786440009463897.

[plackett-21] Plackett, Robin (1983). "Karl Pearson and the Chi-Squared Test". International Statistical Review (en inglés) 51 (1): 59–72. doi:10.2307/1402731.

[:0-22] 1 2 Wang, Thomas (marzo de 1997). "Prime Double Hash Table" (en inglés). Arquivado dende o orixinal o 03 de setembro de 1999. Consultado o 20 de setembro de 2026.

[23] Wegman, Mark N.; Carter, J. Lawrence (xuño de 1981). "New hash functions and their use in authentication and set equality". Journal of Computer and System Sciences (en inglés) 22 (3): 265–279. doi:10.1016/0022-0000(81)90033-7.

[24] Demaine, Erik; Lind, Jeff (primavera de 2003). "Lecture 2" (PDF). 6.897: Advanced Data Structures. MIT Computer Science and Artificial Intelligence Laboratory (en inglés).

[askitis05-25] 1 2 3 4 Askitis, Nikolas; Zobel, Justin (outubro de 2005). "Cache-Conscious Collision Resolution in String Hash Tables". String Processing and Information Retrieval (SPIRE 2005). Lecture Notes in Computer Science (en inglés). pp. 91–102. ISBN 978-3-540-29740-6. doi:10.1007/11575832_11.

[26] Willard, Dan E. (2000). "Examining computational geometry, van Emde Boas trees, and hashing from the perspective of the fusion tree". SIAM Journal on Computing (en inglés) 29 (3): 1030–1049. doi:10.1137/S0097539797322425. .

[27] Askitis, Nikolas; Sinha, Ranjan (outubro de 2010). "Engineering scalable, cache and space efficient tries for strings". The VLDB Journal (en inglés) 19 (5): 633–660. doi:10.1007/s00778-010-0183-9.

[28] Askitis, Nikolas (2009). "Fast and Compact Hash Tables for Integer Keys" (PDF). Proceedings of the 32nd Australasian Computer Science Conference (ACSC 2009) (en inglés). pp. 113–122. ISBN 978-1-920682-72-9.

[tenenbaum90-29] Tenenbaum, Aaron M.; Langsam, Yedidyah; Augenstein, Moshe J. (1990). Data Structures Using C (en inglés). Prentice Hall. pp. 456–461, p. 472. ISBN 978-0-13-199746-2.

[clrs-30] 1 2 3 4 5 6 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). "11: Hash Tables". Introduction to Algorithms (en inglés) (3.ª ed.). MIT Press. pp. 253–285. ISBN 978-0-262-03384-8.

[Cuckoo-31] 1 2 3 Pagh, Rasmus; Rodler, Flemming Friche (2001). "Cuckoo Hashing". Algorithms — ESA 2001. Lecture Notes in Computer Science (en inglés) 2161. pp. 121–133. ISBN 978-3-540-42493-2. doi:10.1007/3-540-44676-1_10.

[chen87-32] 1 2 3 Vitter, Jeffery S.; Chen, Wen-Chin (1987). The design and analysis of coalesced hashing (en inglés). Nova York: Oxford University Press. ISBN 978-0-19-504182-8.

[nir08-33] 1 2 3 4 Herlihy, Maurice; Shavit, Nir; Tzafrir, Moran (2008). "Hopscotch Hashing". Distributed Computing. Lecture Notes in Computer Science (en inglés) 5218. pp. 350–364. ISBN 978-3-540-87778-3. doi:10.1007/978-3-540-87779-0_24.

[waterloo86-34] 1 2 3 Celis, Pedro (1986). Robin Hood Hashing (PDF) (en inglés). Ontario, Canadá: University of Waterloo, Dept. of Computer Science. ISBN 978-0-315-29700-5.

[35] Gries, David (2017). "JavaHyperText and Data Structure: Robin Hood Hashing" (PDF) (en inglés). Cornell University, Department of Computer Science.

[36] Devadas, Srini; Demaine, Erik (25 de febreiro de 2011). "Intro to Algorithms: Resizing Hash Tables" (PDF) (en inglés). Massachusetts Institute of Technology.

[37] Thareja, Reema (2014). "Hashing and Collision". Data Structures Using C (en inglés). Oxford University Press. pp. 464–488. ISBN 978-0-19-809930-7.

[scott03-38] Friedman, Scott; Krishnan, Anand; Leidefrost, Nicholas (18 de marzo de 2003). "Hash Tables for Embedded and Real-time systems" (PDF). All Computer Science and Engineering Research (en inglés) (Washington University in St. Louis). doi:10.7936/K7WD3XXV.

[39] Litwin, Witold (1980). "Linear hashing: A new tool for file and table addressing" (PDF). Proc. 6th Conference on Very Large Databases (en inglés). Carnegie Mellon University. pp. 212–223.

[dijk10-40] Dijk, Tom Van (2010). "Analysing and Improving Hash Table Performance" (PDF) (en inglés). Países Baixos: University of Twente.

[41] Baeza-Yates, Ricardo; Poblete, Patricio V. (1999). "Chapter 2: Searching". En Atallah. Algorithms and Theory of Computation Handbook (en inglés). CRC Press. pp. 2–6. ISBN 0849326494.

[42] Banachowski, Lech. "Indexes and external sorting" (en inglés). Polsko-Japońska Akademia Technik Komputerowych. ^{[Ligazón morta]}

[43] Bottomley, James (1 de xaneiro de 2004). "Understanding Caching" (en inglés). Linux Journal.

[44] Seaman, Jill (2014). "Set & Hash Tables" (PDF) (en inglés). Texas State University.

[45] "JavaScript data types and data structures - JavaScript | MDN". developer.mozilla.org (en inglés).

[46] "Map - JavaScript | MDN". developer.mozilla.org (en inglés). 20 de xuño de 2023.

[47] "Programming language C++ - Technical Specification" (PDF) (en inglés). International Organization for Standardization. pp. 812–813.

[48] "The Go Programming Language Specification". go.dev (en inglés).

[49] "Lesson: Implementations (The Java Tutorials > Collections)". docs.oracle.com (en inglés).

[50] "Design and History FAQ: How are dictionaries implemented in CPython?". Python Documentation (en inglés). Python Software Foundation.

[51] Scheffler, Jonan (25 de decembro de 2016). "Ruby 2.4 Released: Faster Hashes, Unified Integers and Better Rounding". heroku.com (en inglés).

[52] "doc.rust-lang.org" (en inglés).

[53] "HashSet Class (System.Collections.Generic)". learn.microsoft.com (en inglés).

[54] "Dictionary Class (System.Collections.Generic)". learn.microsoft.com (en inglés).

[55] "VB.NET HashSet Example". Dot Net Perls (en inglés).

[Farach-Colton_2024-56] Farach-Colton, Martin; Krapivin, Andrew; Kuszmaul, William (2024). "Optimal Bounds for Open Addressing Without Reordering". 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) (en inglés). IEEE. pp. 594–605. arXiv:2501.02305. doi:10.1109/FOCS61266.2024.00045.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

[48]

[49]

[50]

[51]

[52]

[53]

[54]

[55]

[56]