Vantagens das árvores de pesquisa binárias em relação às tabelas de hash

101

Quais são as vantagens das árvores de pesquisa binárias sobre as tabelas de hash?

As tabelas de hash podem pesquisar qualquer elemento no tempo Theta (1) e é tão fácil adicionar um elemento ... mas não tenho certeza das vantagens do contrário.

Devotado
fonte
para tabelas hash, quais são os tempos de execução para find () insert () e remove ()? teta (1) teta (1) e teta (1) certo?
Devotado em
8
Quase sempre, sim. Se você se deparar com muitas colisões, esses tempos podem crescer até O (n).
Christian Mann
1
Esses tempos também dependem da sua função de hashing. Se por alguma razão estranha não for O (1), obviamente suas operações terão um limite mínimo de qualquer eficiência em que sua função hash é executada.
Christian Mann
Eu diria que as maiores vantagens do BST é que ele está em uma estrutura de dados classificada. Detalhe o caso de uso já listado aqui .
Yuantao
Possível duplicata de Árvores Binárias vs. Listas Vinculadas vs. Tabelas Hash
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功

Respostas:

93

Lembre-se de que as árvores de pesquisa binárias (baseadas em referência) são eficientes em termos de memória. Eles não reservam mais memória do que o necessário.

Por exemplo, se uma função hash tem um intervalo R(h) = 0...100, você precisa alocar uma matriz de 100 (ponteiros para) elementos, mesmo se estiver apenas fazendo hash de 20 elementos. Se você fosse usar uma árvore de pesquisa binária para armazenar as mesmas informações, alocaria apenas o espaço necessário, bem como alguns metadados sobre links.

Christian Mann
fonte
33
Não é verdade que toda a gama de saídas da função hash deva existir no array. Os valores de hash podem simplesmente ser modificados pelo comprimento da matriz para permitir uma matriz menor. Obviamente, o número final de elementos adicionados pode não ser conhecido, portanto, a tabela hash ainda pode alocar mais espaço do que o necessário. As árvores binárias de busca podem desperdiçar a mesma quantidade de memória ou mais. Implementações vinculadas precisam de espaço para pelo menos dois ponteiros adicionais por elemento (três se estiver usando um ponteiro pai), e os BSTs baseados em array podem desperdiçar muita memória para porções não preenchidas da árvore.
Solaraeus
4
@Solaraeus: BSTs baseados em array são os melhores para comparar com tabelas de hash e eles não são mais desperdiçadores do que tabelas de hash. Você também pode expandir um BST com pouco mais do que uma cópia da memória, em comparação com a recomputação de toda a tabela.
Guvante,
125

Uma vantagem que ninguém mais apontou é que a árvore de pesquisa binária permite que você faça pesquisas por intervalo de forma eficiente.

Para ilustrar minha ideia, quero fazer um caso extremo. Digamos que você queira obter todos os elementos cujas chaves estão entre 0 e 5.000. E, na verdade, existe apenas um desses elementos e 10.000 outros elementos cujas chaves não estão no intervalo. O BST pode fazer pesquisas de intervalo de forma bastante eficiente, pois não pesquisa uma subárvore que é impossível ter a resposta.

Enquanto, como você pode fazer pesquisas de intervalo em uma tabela hash? Você precisa iterar cada espaço de bucket, que é O (n), ou você tem que verificar se cada um de 1,2,3,4 ... até 5000 existe. (e as chaves entre 0 e 5000 são um conjunto infinito? por exemplo, as chaves podem ser decimais)

Alex
fonte
11
Os BSTs fazem pesquisas de alcance com eficiência! Para mim, esta é a melhor resposta em termos de abordagem prática e algorítmica.
ady
4
uau, isso realmente explica por que as árvores são tão associadas aos bancos de dados; seus benefícios são mais visíveis quando você precisa executar a filtragem com base em chave. com mapas de hash, você precisa percorrer todas as chaves para resolver "encontrar todos os itens com chave entre 1000 e 3290"
Dmitry
77

Uma "vantagem" de uma árvore binária é que ela pode ser percorrida para listar todos os elementos em ordem. Isso não é impossível com uma tabela de hash, mas não é uma operação normal de um projeto em uma estrutura de hash.

NealB
fonte
3
atravessar em qualquer ordem provavelmente não faria sentido em uma tabela de hash.
FrustratedWithFormsDesigner
2
@FrustratedWithFormsDesigner. Consulte a tabela de hash linear classificada
NealB
Obrigado pelo link, essa é uma ideia interessante! Acho que nunca vi ou usei uma implementação disso (pelo menos não intencionalmente).
FrustratedWithFormsDesigner
1
Link Wayback Machine para o artigo - web.archive.org/web/20100323091632/http://www.concentric.net/…
rahulroy9202
51

Além de todos os outros comentários positivos:

As tabelas de hash em geral têm um melhor comportamento de cache, exigindo menos leituras de memória em comparação com uma árvore binária. Para uma tabela hash, você normalmente só faz uma única leitura antes de ter acesso a uma referência que contém seus dados. A árvore binária, se for uma variante balanceada, requer algo na ordem de k * lg (n) memória lê para alguma constante k.

Por outro lado, se um inimigo conhece sua função hash, ele pode forçar sua tabela hash para fazer colisões, prejudicando bastante seu desempenho. A solução alternativa é escolher a função hash aleatoriamente de uma família, mas um BST não tem essa desvantagem. Além disso, quando a pressão da tabela hash aumenta muito, você geralmente tende a ampliar e realocar a tabela hash, o que pode ser uma operação cara. O BST tem um comportamento mais simples aqui e não tende a alocar repentinamente muitos dados e fazer uma operação de rehashing.

As árvores tendem a ser a estrutura de dados média final. Eles podem atuar como listas, podem ser facilmente divididos para operação paralela, têm rápida remoção, inserção e pesquisa na ordem de O (lg n) . Eles não fazem nada muito bem, mas também não têm um comportamento excessivamente ruim.

Finalmente, BSTs são muito mais fáceis de implementar em linguagens funcionais (puras) em comparação com tabelas de hash e não requerem atualizações destrutivas para serem implementadas (o argumento de persistência de Pascal acima).

EU DEU RESPOSTAS DE CRAP
fonte
3
BSTs are much easier to implement in (pure) functional languages compared to hash-tables- realmente? Quero aprender uma linguagem funcional agora!
nawfal
1
A tabela hash precisa ser persistente em uma linguagem funcional. Isso geralmente complica as implementações.
EU DÊ RESPOSTAS DE CRAP
para elaborar, se você faz estruturas de dados de presidente em linguagens funcionais, tudo o que você realmente acaba fazendo é escrever o mesmo código que faria em assembly, exceto em cada operação que você transforma explicitamente seu array de memória / registradores, ou fala com um servidor para fingir fazer isso. Estou totalmente ciente de seu estado, mas é isomórfico à abordagem imperativa, se feito corretamente (você não pode copiar de forma realista uma grande quantidade de dados em cada transformação na vida real, você precisa trapacear).
Dmitry
27

As principais vantagens de uma árvore binária em relação a uma tabela hash é que a árvore binária fornece duas operações adicionais que você não pode fazer (facilmente, rapidamente) com uma tabela hash

  • encontre o elemento mais próximo de (não necessariamente igual a) algum valor-chave arbitrário (ou mais próximo acima / abaixo)

  • iterar através do conteúdo da árvore em ordem classificada

Os dois estão conectados - a árvore binária mantém seu conteúdo em uma ordem de classificação, portanto, as coisas que exigem essa ordem de classificação são fáceis de fazer.

Chris Dodd
fonte
O BST encontra a correspondência mais próxima, apenas se a correspondência exata não existir, certo? E se você encontrar uma correspondência exata na própria raiz?
desenvolvedor747
2
@ developer747: O próximo abaixo e acima são a folha mais à direita da subárvore esquerda e a folha mais à esquerda da subárvore direita.
Chris Dodd,
16

Uma árvore de pesquisa binária (balanceada) também tem a vantagem de que sua complexidade assintótica é na verdade um limite superior, enquanto os tempos "constantes" para tabelas de hash são tempos amortizados: se você tiver uma função hash inadequada, você pode acabar degradando para o tempo linear , em vez de constante.

Jamesnvc
fonte
3
Para esclarecer esse ponto, um caso degenerado é quando a coleção contém muitas cópias de apenas 1 chave. no BST, a inserção é O (log n), em uma tabela Hash, a inserção é O (n)
SingleNegationElimination
2
Quando uma tabela hash contém muitas cópias de apenas 1 chave, a inserção é (ainda) O (1), não O (n). O problema das tabelas de hash é quando existem muitas chaves diferentes com o mesmo hash. Isso pode ser evitado por um esquema de hash dinâmico que alterna para uma função de hash diferente quando há muitas colisões.
Chris Dodd
Observe que uma árvore não balanceada pode degenerar em uma lista e também ter pesquisa O (n).
awiebe
9

Uma tabela de hash ocuparia mais espaço quando é criada pela primeira vez - ela terá slots disponíveis para os elementos que ainda não foram inseridos (quer tenham ou não sido inseridos), uma árvore de pesquisa binária terá apenas o tamanho necessário estar. Além disso, quando uma tabela hash precisa de mais espaço, expandir para outra estrutura pode ser demorado, mas pode depender da implementação.

FrustratedWithFormsDesigner
fonte
8

Uma árvore de pesquisa binária pode ser implementada com uma interface persistente , onde uma nova árvore é retornada, mas a velha árvore continua a existir. Implementadas com cuidado, as árvores novas e antigas compartilham a maioria de seus nós. Você não pode fazer isso com uma tabela de hash padrão.

Pascal Cuoq
fonte
6

Uma árvore binária é mais lenta para pesquisar e inserir, mas tem o recurso muito bom de travessia de infixo que essencialmente significa que você pode iterar através dos nós da árvore em uma ordem classificada.

Iterar pelas entradas de uma tabela hash simplesmente não faz muito sentido porque todas elas estão espalhadas na memória.

Blagovest Buyukliev
fonte
6

De Entrevista Cracking the Coding, 6ª Edição

Podemos implementar a tabela hash com uma árvore de pesquisa binária balanceada (BST). Isso nos dá um tempo de pesquisa O (log n). A vantagem disso é potencialmente usar menos espaço, uma vez que não alocamos mais um grande array. Também podemos iterar pelas chaves em ordem, o que pode ser útil às vezes.

Guy Kahlon
fonte
5

Os BSTs também fornecem as operações "findPredecessor" e "findSuccessor" (para encontrar o próximo menor e o próximo maior elemento) em tempo O (logn), que também podem ser operações muito úteis. A tabela de hash não pode fornecer eficiência de tempo.

Balaji
fonte
Se você estiver procurando por operações "findPredecessor" e "findSuccessor", então HashTable é uma escolha ruim para estrutura de dados em primeiro lugar.
AKDesai
1

Se você deseja acessar os dados de uma maneira classificada, uma lista classificada deve ser mantida em paralelo à tabela hash. Um bom exemplo é o Dicionário em .Net. (consulte http://msdn.microsoft.com/en-us/library/3fcwy8h6.aspx ).

Isso tem o efeito colateral de não apenas desacelerar as inserções, mas também consome uma quantidade maior de memória do que uma árvore b.

Além disso, como uma árvore b é classificada, é simples encontrar intervalos de resultados ou realizar uniões ou mesclagens.

IamIC
fonte
1

Também depende do uso, o Hash permite localizar a correspondência exata. Se você deseja consultar um intervalo, o BST é a escolha. Suponha que você tenha muitos dados e1, e2, e3 ..... en.

Com a tabela hash, você pode localizar qualquer elemento em tempo constante.

Se você deseja encontrar valores de intervalo maiores que e41 e menores que e8, o BST pode encontrar isso rapidamente.

O principal é a função hash usada para evitar uma colisão. Claro, não podemos evitar totalmente uma colisão, caso em que recorremos ao encadeamento ou outros métodos. Isso faz com que a recuperação não seja mais um tempo constante nos piores casos.

Depois de cheia, a tabela hash precisa aumentar o tamanho do balde e copiar todos os elementos novamente. Este é um custo adicional não presente no BST.

sreeprasad
fonte
1

Tabelas de hash não são boas para indexação. Quando você está procurando por um intervalo, os BSTs são melhores. Essa é a razão pela qual a maioria dos índices de banco de dados usam árvores B + em vez de tabelas de hash

ssD
fonte
índices de bancos de dados são de ambos os tipos hash e árvores B +. Quando você deseja fazer comparação como maior que ou menor que, o índice de árvores B + é útil, caso contrário, o índice de hash é útil para pesquisa. Pense também em quando os dados não são comparáveis ​​e se você deseja criar um índice, então o db criará um índice hash e não um índice de árvore B +. @ssD
Sukhmeet Singh
1

Árvores de pesquisa binárias são uma boa escolha para implementar o dicionário se as chaves tiverem alguma ordem total (as chaves são comparáveis) definidas nelas e você quiser preservar as informações da ordem.

Como o BST preserva as informações do pedido, ele fornece quatro operações de conjunto dinâmico adicionais que não podem ser realizadas (eficientemente) usando tabelas de hash. Essas operações são:

  1. Máximo
  2. Mínimo
  3. Sucessor
  4. Antecessor

Todas essas operações, como toda operação BST, têm complexidade de tempo de O (H). Além disso, todas as chaves armazenadas permanecem classificadas no BST, permitindo que você obtenha a sequência classificada de chaves apenas percorrendo a árvore em ordem.

Em resumo, se tudo o que você deseja são as operações de inserir, excluir e remover, a tabela hash é imbatível (na maioria das vezes) em desempenho. Mas se você quiser alguma ou todas as operações listadas acima, você deve usar um BST, de preferência um BST com autobalanceamento.

mightyWOZ
fonte
0

A principal vantagem da tabela hash é que ela faz quase todas as operações em ~ = O (1). E é muito fácil de entender e implementar. Resolve muitos "problemas de entrevista" com eficiência. Então, se você quiser fazer uma entrevista de codificação, faça melhores amigos com uma mesa de hash ;-)

rajya vardhan
fonte
Acho que o OP pediu vantagens do BST sobre o hashing.
Sniper
0

Um hashmap é uma matriz associativa definida. Portanto, sua matriz de valores de entrada é agrupada em baldes. Em um esquema de endereçamento aberto, você tem um ponteiro para um balde e cada vez que adiciona um novo valor a um balde, você descobre onde no balde há espaços livres. Existem algumas maneiras de fazer isso - você começa no início do balde e incrementa o ponteiro a cada vez e testa se ele está ocupado. Isso é chamado de sondagem linear. Em seguida, você pode fazer uma pesquisa binária como add, onde você dobra a diferença entre o início do balde e onde você dobra ou desce sempre que está procurando um espaço livre. Isso é chamado de sondagem quadrática. ESTÁ BEM. Agora, o problema em ambos os métodos é que, se o balde transbordar para o próximo endereço de balde, você precisa-

  1. Dobre o tamanho de cada balde - malloc (N baldes) / mude a função hash - Tempo necessário: depende da implementação de malloc
  2. Transfira / copie cada um dos dados de buckets anteriores para os novos dados de buckets. Esta é uma operação O (N) onde N representa todos os dados

ESTÁ BEM. mas se você usar uma lista vinculada, não deve haver tal problema, certo? Sim, nas listas vinculadas você não tem esse problema. Considerando que cada intervalo começa com uma lista vinculada, e se você tem 100 elementos em um intervalo, é necessário percorrer esses 100 elementos para chegar ao final da lista vinculada, portanto, List.add (Elemento E) levará tempo para-

  1. Hash o elemento em um balde - Normal como em todas as implementações
  2. Reserve um tempo para encontrar o último elemento na operação de cubeta-O (N).

A vantagem da implementação de lista vinculada é que você não precisa da operação de alocação de memória e transferência / cópia O (N) de todos os depósitos, como no caso da implementação de endereçamento aberto.

Portanto, a maneira de minimizar a operação O (N) é converter a implementação para a de uma Árvore de Busca Binária onde as operações de localização são O (log (N)) e você adiciona o elemento em sua posição com base em seu valor. O recurso adicional de um BST é que ele vem classificado!

Vamsavardhana Vijay
fonte
0

As árvores de pesquisa binárias podem ser mais rápidas quando usadas com chaves de string. Especialmente quando as cordas são longas.

Árvores binárias de pesquisa usando comparações para menor / maior, que são rápidas para strings (quando não são iguais). Portanto, um BST pode responder rapidamente quando uma string não for encontrada. Quando for encontrado, será necessário fazer apenas uma comparação completa.

Em uma mesa de hash. Você precisa calcular o hash da string e isso significa que você precisa passar por todos os bytes pelo menos uma vez para calcular o hash. Então, novamente, quando uma entrada correspondente for encontrada.

Calmarius
fonte