Existe uma versão genérica do HybridDictionary?

9

A descrição de System.Collection.Specialized.HybridDictionary é esta:

  

Implementa IDictionary usando um   System.Collections.Specialized.ListDictionary   enquanto a coleção é pequena, e   depois mudar para um   System.Collections.Hashtable quando o   coleção fica grande.

Existe uma implementação genérica equivalente?

    
por Micah 22.12.2008 в 18:34
fonte

1 resposta

3

Não que eu saiba. No entanto, existe uma necessidade comprovada? As tabelas de hash não têm uma sobrecarga grande, mesmo para N muito pequeno, deve ser mais rápido usar a tabela de hash normal do que pesquisar linearmente.

EDIT Eu não tenho uma referência para provar isso, mas apenas comparando os algoritmos concluo que as tabelas de hash devem ser mais rápidas do que a pesquisa linear assim que N & gt ; 6 em média (para chaves de string ou hashes não triviais semelhantes), então não há realmente nenhuma razão para uma implementação híbrida.

O argumento é o seguinte. Na busca linear, em média, metade dos elementos devem ser comparados à sua entrada, ou seja, N / 2. Em uma tabela de hash, sabe-se que o número esperado de comparações é 2, independentemente do tamanho da entrada (para tabelas hash muito pequenas com um fator de carga menor que 0.1, isso está realmente se aproximando de 1). Além disso, o hash deve ser calculado. Isso resulta em 3 operações em sua entrada, além de uma pequena sobrecarga que pode ser negligenciada. Assim, procuramos por qual N é verdade que 3 > N / 2, o que é trivialmente N > 6.

Observe que o cálculo acima está errado porque, para esse pequeno número de elementos, o fator de carga do Dictionary do .NET será muito menor que 0,1. O ponto de inflexão é, portanto, ainda mais baixo.

    
por Konrad Rudolph 22.12.2008 / 18:44
fonte