(Quando) é a pesquisa de tabela de hash O (1)?

71

Costuma-se dizer que a pesquisa de tabela de hash opera em tempo constante: você calcula o valor do hash, que fornece um índice para uma pesquisa de matriz. No entanto, isso ignora colisões; na pior das hipóteses, todos os itens chegam ao mesmo balde e o tempo de pesquisa se torna linear ( ). $\Theta(n)$

Existem condições nos dados que podem tornar a pesquisa de tabela de hash verdadeiramente ? Isso é apenas em média, ou uma tabela de hash pode ter pesquisa de pior caso? $O(1)$ $O(1)$

Nota: Estou vindo da perspectiva de um programador aqui; quando eu armazeno dados em uma tabela de hash, quase sempre são cadeias de caracteres ou algumas estruturas de dados compostas, e os dados são alterados durante a vida útil da tabela de hash. Portanto, embora eu aprecie respostas sobre hashes perfeitos, eles são fofos, mas engraçados e não são práticos do meu ponto de vista.

Acompanhamento do PS: Para que tipo de dados são as operações da tabela de hash O (1)?

algorithm-analysis data-structures runtime-analysis hash-tables Gilles 'SO- parar de ser mau'
fonte

3

Você pode conviver com tempo de acesso amortizado? Em geral, o desempenho da tabela de hash dependerá muito da quantidade de sobrecarga para tabelas de hash esparsas que você está preparado para tolerar e de como os valores de hash reais são distribuídos.

O (1)

$\cal{O}(1)$

Raphael

5

Ah, btw: você pode evitar o comportamento linear de pior caso usando árvores de pesquisa (balanceadas) em vez de listas.

Raphael

11

@ Rafael, eu ficaria muito interessado em uma resposta que explique (em linhas gerais) quando posso contar com amortizado e quando não posso. Quanto à forma como os valores de hash são distribuídos, isso faz parte da minha pergunta: como posso saber? Eu sei que as funções de hash devem distribuir bem os valores; mas se eles sempre fizessem o pior caso, nunca seriam alcançados, o que não faz sentido.

O (1)

$O(1)$

Gilles 'SO- stop be evil'

11

Também tenha cuidado com a otimização prematura; para dados pequenos (vários milhares de elementos), tenho visto frequentemente árvores binárias balanceadas superam as hashtables devido à sobrecarga mais baixa (as comparações de strings são muito mais baratas que os hashes de strings).

O (\log n)

$O(\log n)$

Isturdy

Vamos continuar esta discussão no chat .

Raphael

41

Existem duas configurações nas quais você pode obter pior caso. $O(1)$

Se sua configuração for estática, o hash do FKS obterá as garantias pior das hipóteses . Mas, como você indicou, sua configuração não é estática. $O(1)$
Se você usar hash Cuckoo, as consultas e exclusões serão pior caso, mas a inserção é apenas esperada. O hash do cuco funciona muito bem se você tiver um limite superior no número total de pastilhas e definir o tamanho da tabela para ser aproximadamente 25% maior. $O(1)$ $O(1)$

Há mais informações aqui .

Suresh
fonte

3

Você poderia expandir o FKS e o Cuckoo? Ambos os termos são novos para mim.

Gilles 'SO- stop be evil'

11

E o hashing perfeito dinâmico? Possui pesquisas de pior caso e inserção e exclusão amortizadas. ( Citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.8165 )

O (1)

$O(1)$

O (1)

$O(1)$

Joe

2

FKS são as iniciais de (Fredman, Komlós, Szemerédi) e cuco é o nome de uma espécie de brid. É usado para esse tipo de hash, porque filhotes de cuco empurram ovos sibilings para fora do ninho. Isso se parece um pouco com o modo como esse método hasing funciona.

1313 uli

11

@Suresh: Sério? Eu pensei que você precisava de funções independentes, que eu sempre associei à necessidade de expansores. Eu estou corrigido. Excluirá meu comentário daqui a pouco.

\log n

$\log n$

Louis

11

Para fazer um comentário mais útil sobre essa resposta, como aponta o @Suresh, o hash cuco funcionará bem sem as funções sofisticadas (e grandes) de hash usadas para analisá-la teoricamente.

Louis

21

Esta resposta resume partes do TAoCP Vol 3, Ch 6.4.

Suponha que temos um conjunto de valores , dos quais queremos armazenar em uma matriz do tamanho . Empregamos uma função de hash ; tipicamente,. Chamamos o factor de carga de . Aqui, assumiremos o natural ; em cenários práticos, temos , porém, e tem que mapear até nós mesmos. $V$ $n$ $A$ $m$ $h : V \to [0..M)$ $M \ll |V|$ $\alpha = \frac{n}{m}$ $A$ $m=M$ $m \ll M$ $m$

A primeira observação é que, mesmo que tenha características uniformes¹, a probabilidade de dois valores terem o mesmo valor de hash é alta; este é essencialmente um exemplo do infame paradoxo do aniversário . Portanto, geralmente teremos que lidar com conflitos e podemos abandonar a esperança do pior caso de tempo de acesso. $h$ $\mathcal{O}(1)$

Mas e o caso médio? Vamos supor que todas as chaves de ocorram com a mesma probabilidade. O número médio de entradas marcadas (pesquisa bem-sucedida) resp. (pesquisa malsucedida) depende do método de resolução de conflitos usado. $[0..M)$ $C_n^S$ $C_n^U$

Encadeamento

Cada entrada da matriz contém (um ponteiro para o início) uma lista vinculada. Essa é uma boa idéia, pois o tamanho esperado da lista é pequeno ( ), mesmo que a probabilidade de ter colisões seja alta. No final, obtemos Isso pode ser melhorado um pouco, armazenando as listas (parcial ou completamente) dentro da tabela. $\frac{n}{m}$

C_{n}^{S} \approx 1 + \frac{α}{2} and C_{n}^{U} \approx 1 + \frac{α^{2}}{2} .

$C_n^S \approx 1 + \frac{\alpha}{2} \quad \text{ and } \quad C_n^U \approx 1 + \frac{\alpha^2}{2} .$

Sondagem linear

Ao inserir (resp. Pesquisando um valor) , verifique as posições nesta ordem até uma posição vazia (resp. ) for encontrado. A vantagem é que trabalhamos localmente e sem estruturas de dados secundárias; no entanto, o número médio de acessos diverge de : Para , no entanto, o desempenho é comparável ao encadeamento². $v$

h (v), h (v) - 1, \dots, 0, m - 1, \dots, h (v) + 1

$h(v), h(v)-1,\dots,0,m-1,\dots,h(v)+1$

v

$v$

α \to 1

$\alpha \to 1$

C_{n}^{S} \approx \frac{1}{2} (1 + \frac{1}{1 - α}) and C_{n}^{U} \approx \frac{1}{2} (1 + {(\frac{1}{1 - α})}^{2}) .

$C_n^S \approx \frac{1}{2}\left(1 +\frac{1}{1-\alpha}\right) \quad \text{ and } \quad C_n^U \approx \frac{1}{2}\left(1 +\left(\frac{1}{1-\alpha}\right)^2\right).$

α < 0.75

$\alpha < 0.75$

Hashing Duplo

Semelhante a sondagem linear mas o tamanho do passo de pesquisa é controlada por uma segunda função hash que é coprime para . Nenhuma derivação formal é fornecida, mas observações empíricas sugerem Este método foi adaptado por Brent; sua variante amortiza os custos de inserção com pesquisas mais baratas. $M$

C_{n}^{S} \approx \frac{1}{α} \ln (\frac{1}{1 - α}) and C_{n}^{U} \approx \frac{1}{1 - α} .

$C_n^S \approx \frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\quad \text{ and } \quad C_n^U \approx \frac{1}{1-\alpha} .$

Observe que a remoção de elementos e a extensão de tabelas tem graus variados de dificuldade para os respectivos métodos.

Bottom line, você tem que escolher uma implementação que se adapte bem aos seus casos de uso típicos. O tempo esperado de acesso em é possível se nem sempre garantido. Dependendo do método usado, manter baixo é essencial; você precisa trocar o tempo de acesso (esperado) versus a sobrecarga de espaço. Uma boa escolha para também é central, obviamente. $\mathcal{O}(1)$ $\alpha$ $h$

1] Como programadores desinformados arbitrariamente ~~burros~~ podem fornecer , qualquer suposição sobre sua qualidade é um exagero na prática. 2] Observe como isso coincide com as recomendações para o uso de Java . $h$
Hashtable

Rafael
fonte

10

Uma função hash perfeita pode ser definida como uma função injetiva de um conjunto para um subconjunto dos números inteiros . Se existir uma função de hash perfeita para suas necessidades de dados e armazenamento, você poderá obter facilmente o comportamento . Por exemplo, você pode obter desempenho de uma tabela hash para a seguinte tarefa: dado um array de inteiros e um conjunto de inteiros, determine se contém para cada . Uma etapa de pré-processamento envolveria a criação de uma tabela de hash em , seguida pela verificação de cada elemento de contra ele em $S$ $\{0, 1, 2, ..., n\}$ $O(1)$ $O(1)$ $l$ $S$ $l$ $x$ $x \in S$ $O(|l|)$ $S$ $O(|S|)$ . No total, este é . Uma implementação ingênua usando pesquisa linear pode ser ; usando a pesquisa binária, é possível executar (observe que esta solução é o espaço , pois a tabela de hash deve mapear números inteiros distintos em para compartimentos distintos. $O(|l| + |S|)$ $O(|l||S|)$ $O(\log(|l|)|S|)$ $O(|l|)$ $l$

EDIT: Para esclarecer como a tabela de hash é gerada em : $O(|l|)$

A lista contém inteiros a partir de um conjunto finito , possivelmente, com repetições, e . Queremos determinar se está em . Para fazer isso, pré-calculamos uma tabela de hash para elementos de : uma tabela de pesquisa. A tabela de hash codificará uma função . Para definir , inicialmente assumir para todos . Em seguida, varra linearmente os elementos de , configurando . Isso leva tempo e $l$ $U \subset \mathbb{N}$ $S \subseteq U$ $x \in S$ $l$ $l$ $h: U \rightarrow \{true, false\}$ $h$ $h(x) = false$ $x \in U$ $y$ $l$ $h(y) = true$ $O(|l|)$ $O(|U|)$ espaço.

Observe que minha análise original assumiu que continha pelo menos elementos distintos. Se ele contiver menos elementos distintos (por exemplo, ), o requisito de espaço poderá ser maior (embora não seja mais que ). $l$ $O(|U|)$ $O(|1|)$ $O(|U|)$

EDIT2: A tabela de hash pode ser armazenada como uma matriz simples. A função hash pode ser a função identidade em . Observe que a função de identidade é trivialmente uma função perfeita de hash. é a tabela de hash e codifica uma função separada. Estou sendo desleixado / confuso em algumas das opções acima, mas tentarei melhorá-lo em breve. $U$ $h$

Patrick87
fonte

Você poderia expandir a parte em que você criou a tabela de hash em ? Eu posso ver como fazer isso se você não se preocupar com colisões, mas isso significa que as pesquisas posteriores podem levar mais de , até .

O (| l |)

$O(|l|)$

O (| S |)

$O(|S|)$

O (| l | \cdot | S |)

$O(|l|\cdot|S|)$

Gilles 'SO- stop be evil'

Eu não entendo a definição de . Você está definindo uma função, mas não explicando como ela é representada; você poderia escrever algumas linhas de pseudocódigo? Há também um problema de notação; e bijective não combinam bem.

h

$h$

h : U \to {f a l s e, t r u e}

$h:U\to\{\mathrm{false},\mathrm{true}\}$

h

$h$

Gilles 'SO- stop be evil'

@ Gilles Basicamente, está apenas sendo usado como uma tabela de pesquisa para associação à lista. Quando você tem uma função de hash perfeita com um inverso barato e conhecido, em vez de armazenar a coisa em si, você só precisa armazenar 1 bit (se a coisa com o hash exclusivo foi adicionada). Se colisões forem possíveis, acho que fazer isso é chamado de filtro Bloom, mas, em qualquer caso, pode fornecer um "não" definitivo à questão da associação, o que ainda é útil em muitos cenários.

Patrick87

9

Uma função de hash perfeita resultará em pesquisa de pior caso. $\cal{O}(1)$

Além disso, se o número máximo de colisões possível for , pode-se dizer que a consulta à tabela de hash é no pior caso. Se o número esperado de colisões for , a consulta da tabela de hash poderá ser no caso médio. $\cal{O}(1)$ $\cal{O}(1)$ $\cal{O}(1)$ $\cal{O}(1)$

Nicholas Meyer
fonte

Uma função de hash perfeita seria perfeita, mas como faço para obter uma? Quanto vai me custar? E como sei qual é o número máximo ou esperado de colisões?

Gilles 'SO- stop be evil'

2

@Gilles uma função de hash perfeita é qualquer função que produzirá um hash exclusivo para todas as entradas possíveis. Se suas entradas possíveis são finitas (e exclusivas), isso é fácil.

Rafe Kettler

11

@RafeKettler Minhas entradas são tipicamente cadeias de caracteres ou estruturas de dados compostas, e geralmente adiciono e removo entradas à medida que meus dados evoluem. Como faço um hash perfeito para isso?

Gilles 'SO- stop be evil'

4

Sim, mas esse é o ponto. Uma função hash perfeita determinística não existe se o domínio for maior que o intervalo.

Suresh

@Suresh: se você tem permissão para escolher uma nova função de hash e aumentar o tamanho da tabela sempre que houver uma colisão, sempre poderá encontrar uma função (determinística) de hash que - para os dados que já estão na tabela mais a nova item que você está tentando inserir - não tem colisões (é "perfeito"). É por isso que o hashing perfeito dinâmico seleciona periodicamente uma nova função aleatória de hash.

David Cary

(Quando) é a pesquisa de tabela de hash O (1)?

Respostas:

Encadeamento

Sondagem linear

Hashing Duplo