Quais são as vantagens de sondagem linear sobre encadeamento separado ou vice-versa ao implementar tabelas de hash?

6

Eu estive aprimorando algoritmos e revisando esses dois métodos de implementação de tabelas de hash. Parece que eles têm características de desempenho e requisitos de memória semelhantes.

Eu posso pensar em algumas desvantagens para sondagem linear - ou seja, que o alargamento da matriz poderia ser caro (mas isso é feito, o que, 2 log N vezes no máximo? Provavelmente não é grande coisa) e que o gerenciamento de exclusões é um um pouco mais difícil. Mas eu estou supondo que há vantagens também, ou não seria apresentado em livros didáticos como um método viável de implementação próximo à implementação mais óbvia.

Por que você escolheria um sobre o outro?

    
por Casey 07.04.2015 / 16:08
fonte

3 respostas

7

Com sondagem linear (ou qualquer sondagem realmente) uma deleção tem que ser "soft". Isso significa que você precisa inserir um valor fictício (geralmente chamado de marca de exclusão) que não corresponderá a nada que o usuário possa pesquisar. Ou você precisaria refazer todas as vezes. Rehashing quando muitas lápides se acumulam ainda é aconselhado ou alguma estratégia para desfragmentar o cemitério.

O encadeamento separado (cada intervalo é um ponteiro para uma lista vinculada de valores) tem a desvantagem de você acabar pesquisando uma lista vinculada com todos os problemas relacionados ao cache disponíveis.

Outra vantagem do método de investigação é que todos os valores residem no mesmo array. Isso torna a cópia na gravação muito fácil apenas copiando a matriz. Se você puder ter certeza de que o original não é modificado por invariante de classe, então tirar uma foto é O (1) e pode ser feito sem bloquear.

    
por 07.04.2015 / 17:14
fonte
2

Confira esta ótima resposta:

link

Citando aqui:

I'm surprised that you saw chained hashing to be faster than linear probing - in practice, linear probing is typically significantly faster than chaining. In fact, that's the main reason it's used.

Although chained hashing is great in theory and linear probing has some known theoretical weaknesses (such as the need for five-way independence in the hash function to guarantee O(1) expected lookups), in practice linear probing is typically significantly faster due to locality of reference. Specifically, it's faster to access a series of elements in an array than it is to follow pointers in a linked list, so linear probing tends to outperform chained hashing even if it has to investigate more elements.

There are other wins in chained hashing. For example, insertions into a linear probing hash table don't require any new allocations (unless you're rehashing the table), so in applications like network routers where memory is scarce, it's nice to know that once the table is set up, the elements can be placed into it with no risk of a malloc fail.

    
por 16.10.2015 / 08:30
fonte
1

Eu pulo com uma resposta tendenciosa onde eu prefiro separar o encadeamento com listas ligadas individualmente e achar mais fácil para alcançar o desempenho com elas (eu sou não estou dizendo que são ideais, apenas mais fácil para meus casos de uso), por mais contraditório que isso pareça.

É claro que o ótimo teórico ainda é uma tabela de hash sem colisões ou uma técnica de sondagem com o mínimo de clustering. No entanto, a solução de encadeamento separada não precisa lidar com problemas de agrupamento.

Dito isto, a representação de dados que utilizo não invoca uma atribuição de memória separada por nó. Aqui está em C:

struct Bucket
{
    int head;
};

struct BucketNode
{
    int next;
    int element;
};

struct HashTable
{
    // Array of buckets, pre-allocated in advance.
    struct Bucket* buckets;

    // Array of nodes, pre-allocated assuming the client knows
    // how many nodes he's going to insert in advance. Otherwise
    // realloc using a similar strategy as std::vector in C++.
    struct BucketNode* nodes;

    // Number of bucket heads.
    int num_buckets;

    // Number of nodes inserted so far.
    int num_nodes;
};

Os buckets são apenas índices de 32 bits (não uso nem mesmo uma estrutura na realidade) e os nós são apenas dois índices de 32 bits. Frequentemente, nem preciso do element index porque os nós são frequentemente armazenados em paralelo com o array de elementos a serem inseridos na tabela, reduzindo a sobrecarga da tabela de hash para 32 bits por bucket e 32 bits por elemento inserido. A versão real que eu uso com mais frequência é assim:

struct HashTable
{
    // Array of head indices. The indices point to entries in the 
    // second array below.
    int* buckets;

    // Array of next indices parallel to the elements to insert.
    int* next_indices;

    // Number of bucket heads.
    int num_buckets;
};

Além disso, se a localidade espacial degrada, posso executar facilmente uma passagem de pós-processamento onde eu construo uma nova tabela de hash onde cada nó do bucket é contíguo ao outro (função de cópia trivial que apenas faz uma passagem linear pela tabela de hash e construções um novo - devido à natureza em que ele atravessa a tabela de hash, a cópia termina com todos os nós vizinhos em um intervalo contíguo entre si.

Quanto às técnicas de sondagem, ele traz os benefícios de a localidade espacial já estar lá desde o início, sem pools de memória ou uma matriz de backup, e eles também não têm a sobrecarga de 32 bits por bucket e nó , mas você pode ter que lidar com problemas de clustering que podem começar a se acumular de uma forma viciosa com muitos conflitos.

Eu acho que a própria natureza do agrupamento é uma dor de cabeça que requer muita análise no caso de muitas colisões. O benefício desta solução é que muitas vezes consigo obter um resultado decente na primeira vez sem análises e testes tão profundos. Além disso, se a tabela for redimensionada implicitamente, encontrei casos em que esses designs acabaram explodindo o uso da memória de maneiras que superaram em muito o que essa solução básica que requer 32 bits por bucket e 32 bits por nó seria executada mesmo no pior cenário. É uma solução que evita tornar-se muito ruim mesmo se houver um número de colisões.

A maior parte da minha base de código gira em torno de estruturas de dados que armazenam índices e geralmente armazenam índices em paralelo com a matriz de elementos a serem inseridos. Isso reduz o tamanho da memória, evita cópias profundas supérfluas dos elementos a serem inseridos e facilita muito o raciocínio sobre o uso da memória. Além disso, no meu caso, tenho a tendência de me beneficiar tanto do desempenho previsível quanto do desempenho ideal. Um algoritmo que é ótimo em muitos casos comuns, mas pode ter um desempenho horrível nos piores cenários, é menos preferível para mim do que aquele que funciona razoavelmente bem o tempo todo e não faz com que as taxas de quadros gaguejem em horários imprevisíveis. tendem a favorecer esses tipos de soluções.

    
por 07.12.2017 / 12:17
fonte