(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 ( ).Θ(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)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)?

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)
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)
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(logn)
Isturdy

Respostas:

41

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

  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)

  2. 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)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)
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. logn
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.n A m h : V [ 0 .. M ) M | V | α = nVnAmh:V[0..M)M|V| Am=MmMmα=nmAm=MmMm

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.O ( 1 )hO(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.C S n C U n[0..M)CnSCnU

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. C S n1+αnm

CnS1+α2 and CnU1+α22.

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,,0,m1,,h(v)+1
vα1
CnS12(1+11α) and CnU12(1+(11α)2).
α<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

CnS1αln(11α) and CnU11α.

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.O(1)α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 emS{0,1,2,...,n}O(1)O(1)lSlxxSO(|l|)SO(|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 elUNSUxSllh:U{true,false}hh(x)=falsexUylh(y)=trueO(|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 ).lO(|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.Uh

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(|S|)O(|l||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. hh:U{false,true}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.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.O ( 1 ) O ( 1 ) O ( 1 )O(1)O(1)O(1)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