Tabelas hash versus árvores binárias

30

Ao implementar um dicionário ('Desejo procurar dados do cliente por seus IDs de cliente'), as estruturas de dados típicas usadas são tabelas de hash e árvores de pesquisa binária. Eu sei, por exemplo, que a biblioteca C ++ STL implementa dicionários (eles os chamam de mapas) usando árvores de pesquisa binária (balanceadas) e o .NET framework usa tabelas de hash sob o capô.

Quais são as vantagens e desvantagens dessas estruturas de dados? Existe alguma outra opção razoável em determinadas situações?

Observe que não estou particularmente interessado nos casos em que as chaves têm uma estrutura subjacente forte, digamos, são todos números inteiros entre 1 e n ou algo assim.

Alex ten Brink
fonte
1
Exasperarei você, mas você não pode simplesmente dizer "números inteiros entre 1 e n", pois, nesse caso, uma matriz supera todas as outras estruturas de dados :-). "Strings" parece justo e cobre a maioria das situações.
Jmad
@ jmad ele disse que não está interessado nesse caso.
13133 Joe
@ Joe, pensei que estava claro que levei isso em conta. De qualquer forma, esse não é um motivo para dar o pior exemplo possível de chave.
Jmad
1
Na verdade, o .NET possui dois dicionários implementados usando árvores e dicionários implementados usando tabelas de hash (e o C ++ também desde o padrão de 2011).
sepp2k
Possível mesmo no SO: stackoverflow.com/questions/371136/…
Ciro Santilli escreveu

Respostas:

26

n

A resposta curta é que as tabelas de hash são mais rápidas na maioria dos casos , mas podem ser muito ruins na pior das hipóteses. As árvores de pesquisa têm muitas vantagens, incluindo o pior comportamento , mas são um pouco mais lentas em casos típicos.

O(eug(n))euog2(n)

2nO(1)

O(1)

  • O(n)
  • O(1)

Quando você coloca a localidade dos dados na mistura, as tabelas de hash se saem mal. Eles funcionam precisamente porque armazenam elementos relacionados distantes, o que significa que, se o aplicativo procurar elementos que compartilham um prefixo em sequência, ele não se beneficiará dos efeitos do cache. Isso não é relevante se o aplicativo fizer pesquisas essencialmente aleatórias.

Outro fator a favor das árvores de pesquisa é que elas são uma estrutura de dados imutável : se você precisar fazer uma cópia de uma árvore e alterar alguns elementos nela, poderá compartilhar a maior parte da estrutura de dados. Se você tirar uma cópia de uma tabela de hash, precisará copiar toda a matriz de ponteiros. Além disso, se você estiver trabalhando em uma linguagem puramente funcional, as tabelas de hash geralmente não são uma opção.

k1k2h(k1)=h(k2)

Em particular, se você precisar da ordem das teclas, por exemplo, se quiser listar as chaves em ordem alfabética, as tabelas de hash não ajudarão (você precisará classificá-las), enquanto você pode atravessar diretamente uma árvore de pesquisa em ordem.

Você pode combinar árvores de pesquisa binária e tabelas de hash na forma de árvores de hash . Uma árvore de hash armazena chaves em uma árvore de pesquisa de acordo com seu hash. Isso é útil, por exemplo, em uma linguagem de programação puramente funcional na qual você deseja trabalhar com dados que não possuem uma relação de ordem fácil de calcular.

Quando as chaves são cadeias (ou números inteiros), um trie pode ser outra opção. Um trie é uma árvore, mas indexado de forma diferente de uma árvore de pesquisa: você escreve a chave em binário e sai à esquerda para 0 e à direita para 1. 1. O custo de um acesso é, portanto, proporcional ao comprimento da chave. As tentativas podem ser compactadas para remover nós intermediários; isso é conhecido como uma árvore patricia trie ou radix . As árvores Radix podem superar as árvores equilibradas, principalmente quando muitas chaves compartilham um prefixo comum.

Gilles 'SO- parar de ser mau'
fonte
2
Os BSTs também não têm localidade de dados incorreta?
svick
@svick Eles podem ou não, dependendo de como os nós estão alocados. Aumentar a aridade da árvore pode ajudar sem comprometer o tempo de execução (o custo é um código maior e mais complexo).
Gilles 'SO- stop be evil'
2
Em um BST, é fácil obter os elementos "em ordem", pois uma tabela de hash está fora de questão.
vonbrand
Exceto por razões de segurança, por que importa se as tabelas de hash têm um pior momento para pior caso, se o caso médio for melhor que o das árvores binárias? Imagino que a utilidade / conveniência do usuário tenha uma relação aproximadamente linear com o tempo que leva para a árvore terminar, portanto o valor (médio) esperado deve ser tudo o que importa.
Kelmikra
@ Kyth'Py1k O que você quer dizer com “a árvore para terminar”? O objetivo das tabelas de hash é acessar um valor de cada vez, não a árvore inteira; caso contrário, uma lista ou matriz funcionaria melhor. Mesmo nas situações em que o valor médio é o que importa (o que nem sempre é o caso, por exemplo, quando você tem restrições em tempo real), é a média das solicitações feitas em uma determinada situação, que geralmente não são uniformes sobre a mesa - por exemplo, tendencioso para um determinado prefixo.
Gilles 'SO- stop be evil'