É possível acelerar uma tabela de hash usando árvores de pesquisa binária para encadeamento separado?

11

Desejo implementar uma tabela de hash usando árvores de pesquisa binária para reduzir a complexidade da pesquisa no processo de encadeamento separado de O (n) (usando lista vinculada) a O (log n) (usando BST). Isso pode ser feito e, se sim, como? Seria mais fácil entender se a solução é passo a passo, implementação da lógica.

Desejo reduzir o tempo de pesquisa na hashtable (compilação usando encadeamento separado), mas, ao mesmo tempo, não quero que o tempo de inserção aumente. Para o meu projeto, não posso alterar a função hash para reduzir colisões. Mas, devido à escalabilidade, colisões estão acontecendo. Estou tentando encontrar uma solução alternativa para que, de alguma forma, eu possa trabalhar com o melhor acesso e inserir tempo no caso de uma colisão ... ou seja, para gerenciar o estado atual das coisas do que para reestruturar todo o algoritmo. Se não der certo, terá que se reestruturar. Então, alguma idéia?

Aviral
fonte
4
As tabelas de hash e as árvores de pesquisa binária são contêineres diferentes . Portanto, você não pode fazer o que sugere (ou está cometendo um erro terminológico).
Basile Starynkevitch
Eu acho que você poderia colocar um par de hash / valor em cada nó de uma árvore ... mas isso seria uma tabela de hash ruim ou uma árvore binária ruim. Sem alguns esclarecimentos sobre o motivo pelo qual você deseja fazer isso e do que deseja que o resultado final seja capaz, não tenho certeza de que isso seja realmente responsável.
Ixrec
1
@AK_: Sim, algo desse tipo, como você disse. Eu quero lidar com as colisões usando a árvore de pesquisa binária. Corrigi um pouco minha pergunta para torná-la mais clara.
Aviral
1
Observe que vem com a penalidade de O (n log n) para cada inserção então. Em geral, quando você tem uma tabela de hash que começa a ficar muito cheia (e você tem cadeias mais longas do que você pode tolerar), reconstrói o hash. Se você encontrar correntes regularmente com mais de 3 ou 4, algo está errado.
3
Há uma infinidade de variações na tabela de hash para redução de colisão, endereçamento aberto e redimensionamento dinâmico da tabela. Qual deles se encaixa nos seus requisitos é algo que você precisará analisar. Sua abordagem atual é coberto pelo encadeamento separado com outras estruturas

Respostas:

11

O que você está pedindo é possível, dadas as suas restrições.

Análise

A força de uma tabela de hash é sua rápida pesquisa e velocidade de inserção. Para obter essa velocidade, é preciso abandonar qualquer aparência de ordem na tabela: ou seja, as entradas são todas desordenadas. Uma lista é aceitável para uso como entrada da tabela porque, embora a travessia seja O (n), as listas tendem a ser curtas, supondo que a tabela de hash seja suficientemente grande e que os objetos armazenados na tabela sejam hash usando um algoritmo de hash de boa qualidade.

Uma árvore de pesquisa binária (BST) tem inserção e pesquisa rápidas em O (log 2 n). Também impõe uma restrição aos elementos que armazena: deve haver alguma maneira de ordenar os elementos. Dados dois elementos A e B armazenados na árvore, deve ser possível determinar se A vem antes de B ou se eles têm ordem equivalente.

Uma tabela de hash não impõe essa restrição: os elementos em uma tabela de hash devem ter duas propriedades. Primeiro, deve haver uma maneira de determinar se são equivalentes; segundo, deve haver uma maneira de calcular um código hash determinístico. A ordem não é um requisito.

Se seus elementos da tabela de hash tiverem um pedido, você poderá usar uma BST como uma entrada da tabela de hash para manter objetos com o mesmo código de hash (colisões). No entanto, devido a uma BST ter pesquisa e inserção de O (log 2 n), isso significa que o pior caso para toda a estrutura (tabela de hash mais BST) é tecnicamente melhor do que usar uma lista como entrada da tabela. Dependendo da implementação do BST, será necessário mais armazenamento do que uma lista, mas provavelmente não muito mais.

Observe que normalmente a sobrecarga e o comportamento de um BST não traz nada para a tabela em situações do mundo real como baldes de tabelas de hash, e é por isso que o baixo desempenho teórico de uma lista é aceitável. Em outras palavras, a tabela de hash compensa a fraqueza da lista, colocando menos itens em cada lista (bloco). No entanto : o problema declarou especificamente que a tabela de hash não pode aumentar de tamanho e as colisões são mais frequentes do que o normal em uma tabela de hash.

Implementação

Não vou colocar código aqui, porque honestamente não é realmente necessário e você não forneceu um idioma de qualquer maneira.

O que eu faria é simplesmente copiar qualquer tabela de hash padrão que a biblioteca padrão de seu idioma contenha em uma nova classe e alterar o tipo de balde de tabela de uma lista para uma árvore. Dependendo do idioma e de sua biblioteca padrão, isso pode ser algo muito trivial.

Normalmente, eu não recomendaria copiar e colar códigos como este. No entanto, é uma maneira fácil de obter uma estrutura de dados testada em batalha muito rapidamente.


fonte
Em termos assintóticos, o uso de uma árvore binária para manipulação de colisões não altera o desempenho esperado de uma tabela de hash, desde que a tabela de hash já tenha feito os truques usuais para alcançar o desempenho O (1) amortizado de qualquer maneira. Redimensionar a hashtable para garantir um bom desempenho significa que os itens esperados por depósito (o tamanho das árvores binárias) também devem ser pequenos, portanto, você acaba com o mesmo O (1) amortizado esperado de qualquer maneira. Mesmo no pior caso - sem nenhuma restrição de balanceamento especificada, o desempenho do pior caso para uma árvore binária é que ele acaba se comportando como uma lista vinculada de qualquer maneira.
31320 Steve314
@ Steve314 Lembre-se de que o problema é que existem muitas colisões; portanto, ele espera que um balde contenha mais itens do que normalmente uma tabela de hash.
Bom ponto - por exemplo, para uma tabela de hash de tamanho constante com dados ilimitados, o desempenho assintótico da tabela de hash é o mesmo que o desempenho assintótico do tratamento de colisões - a tabela de hash altera apenas os fatores constantes.
31320 Steve314
@ Steve314 certo, essencialmente se a tabela de hash não puder limitar efetivamente o número de elementos em cada bloco, o desempenho assintótico se degradará em qualquer estrutura de sub-dados usada em cada bloco. Adicionei um parágrafo à minha resposta para deixar isso claro.
7

Usar uma árvore binária para lidar com colisões em uma tabela de hash não é apenas possível - foi feito.

Walter Bright é mais conhecido como o inventor da linguagem de programação D , mas também escreveu uma variante ECMAScript chamada DMDScript . No passado, uma reivindicação principal do DMDScript (ou possivelmente um ancestral - parece que me lembro do nome DScript) era que suas hashtables tendiam a superar as de muitas linguagens semelhantes. O motivo - tratamento de colisão usando árvores binárias.

Não me lembro exatamente de onde é isso, mas as árvores usadas eram binárias ingênuas, sem um esquema de equilíbrio parcial (não AVL, preto-vermelho ou qualquer outra coisa), o que faz sentido, assumindo que a própria hashtable é redimensionada quando fica cheia demais e você não obtém taxas absurdamente improváveis ​​de colisões de hash, as árvores binárias devem sempre ser pequenas. Basicamente, o pior caso ainda é o mesmo que usar uma lista vinculada para tratamento de colisão (exceto que você paga o preço de dois ponteiros por nó em vez de um), mas o caso médio reduz a quantidade de pesquisa em cada intervalo de hash.

Steve314
fonte