Executar tempo para inserir elementos n em uma tabela hash vazia

Question

As pessoas dizem que é preciso O amortizado (1) para colocar em uma tabela hash. Portanto, n colocando elementos devem ser O (n). Isso não é verdade para n grande, no entanto, uma vez que como um respondente disse: "Tudo que você precisa para satisfazer esperado O amortizado (1) para expandir a tudo mesa e repetição com uma nova função hash aleatório sempre que houver uma colisão."

Então: qual é o running-tempo médio de inserção de n elementos em uma tabela hash? Sei que este é provavelmente dependente de implementação, de modo menção que tipo de aplicação que você está falando.

Por exemplo, se houver (log n) colisões igualmente espaçados, e cada colisão leva O (k) deliberar, onde k é o tamanho atual da tabela hash, então você tem essa relação de recorrência:

T(n) = T(n/2) + n/2 + n/2

(isto é, você tomar o tempo para inserir N / 2 elementos, então você tem uma colisão, tendo n / 2 para resolver, então você faz as restantes n / 2 inserções sem uma colisão). Isto ainda acaba por ser o (n), de modo yay. Mas isso é razoável?

Answer 1

É completamente depende de quão ineficiente seu rehashing é. Especificamente, se você pode corretamente estimar o tamanho esperado do seu hashtable pela segunda vez, o seu tempo de execução ainda se aproxima de O (n). Efetivamente, você tem que especificar como ineficiente seu cálculo do tamanho da repetição é antes que você possa determinar a ordem esperada.

Answer 2

As pessoas dizem que é preciso O amortizado (1) para colocar em uma tabela hash.

Do ponto de vista teórico, é esperado amortizado O (1).

As tabelas de hash são fundamentalmente uma estrutura de dados randomizado, no mesmo sentido que quicksort é um algoritmo aleatório. Você precisa gerar suas funções hash com alguma aleatoriedade, ou então existem entradas patológicos que não são O (1).

Você pode conseguir esperado amortizado O (1) usando dinâmica hashing perfeito :

A idéia ingênua I originalmente era a repetição com uma nova função hash aleatório em cada colisão. (Ver também funções perfeito de hash ) O problema com isto é que este requer o (n ^ 2 ) espaço, a partir paradoxo do aniversário.

A solução é ter dois tabelas de hash, com a segunda tabela de colisões; resolver colisões em que a segunda tabela, reconstruí-lo. Que a tabela terá O (\ sqrt {n}) elementos, por isso iria crescer para O (n) tamanho.

Na prática, muitas vezes você só usar uma função hash fixo porque você pode assumir (ou não se importam se) a sua entrada é patológico, bem como muitas vezes você quicksort sem prerandomizing de entrada.

Answer 3

Todos O (1) está dizendo é que a operação é realizada em tempo constante, e é não dependente do número de elementos na sua estrutura de dados.

Em palavras simples, isso significa que você vai ter que pagar o mesmo custo, não importa quão grande é a sua estrutura de dados é.

Em termos práticos, isto significa que as estruturas de dados simples, como as árvores são geralmente mais eficaz quando você não tem que armazenar uma grande quantidade de dados. Na minha experiência, eu acho árvores mais rápido até ~ 1k elementos (inteiros de 32 bits), em seguida, tabelas hash assumir. Mas, como YMMW habitual.

Answer 4

Porque não basta fazer alguns testes em seu sistema? Talvez se você postar a fonte, podemos voltar e testá-los em nossos sistemas e poderíamos realmente moldar isso em uma discussão muito útil.

Não é apenas a implementação, mas o ambiente bem que decide quanto tempo o algoritmo realmente leva. No entanto, pode procurar se quaisquer amostras de benchmarking estão disponíveis ou não. O problema com me a postar meus resultados não será de nenhum uso desde pessoas não têm idéia do que está em execução no meu sistema, quanta memória RAM é livre direito agora e assim por diante. Você pode sempre apenas ter uma idéia geral. E isso é quase tão bom quanto o que o big-O lhe dá.