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.