Tabla de Hash: ¿Debo aumentar el número de elementos en las colisiones?

Question

En este momento mis tablas hash contar el número de cada elemento insertado en la tabla hash. Yo uso este recuento, con el tamaño total de la tabla hash, para calcular el factor de carga y cuando llega al igual que el 70%, lo que REHASH.

Estaba pensando que tal vez sólo deben contar con los elementos insertados con rellenos una ranura vacía en lugar de todos ellos. Porque el método de colisión que estoy usando es encadenamiento separado. El factor de carga sigue aumentando, pero si no puede haber unas pocas colisiones dejando un montón de espacios vacíos en la tabla hash.

Usted probablemente está pensando que si tengo que muchas colisiones, tal vez no estoy usando el mejor método de hash. Pero eso no es el punto, estoy usando uno de los algoritmos de hash saber por ahí, he probado 3 de ellos en mis datos de la muestra y seleccionó el que produce menos colisiones.

Mi pregunta sigue siendo. ¿Debo seguir contando cada elemento insertado, o sólo las que llenan un espacio vacío en la tabla hash?

Answer 1

refrito está destinado a reducir la probabilidad de colisiones, así sistemáticamente ignorando las colisiones de decidir cuándo repetición parece contraproducente.

podría ser mejor si se mantienen con cada entrada el valor hash original completo (una colisión por supuesto, sino que corresponde el hash modulo su tamaño actual) y contó sólo las colisiones que se deben a la operación de módulo - reconociendo implícitamente que Si la colisión es debido a los valores de hash completos idénticos para diferentes elementos, no hay nada refrito puede hacer para ayudar (a no ser por "refrito" que también implican el cambio a una función hash diferente, pero no se parece a eso es lo que usted se refiere aquí; -.)

Mantener los valores hash completo también significa refrito más barato ya que no es necesario para ejecutar la función hash de nuevo (lo relevante es que depende de lo costoso de su función hash es calcular, por supuesto).