Con los métodos convencionales de resolución de colisiones, como el encadenamiento separado y el sondeo lineal / cuadrático, la secuencia de la sonda para una clave puede ser arbitrariamente larga: simplemente se mantiene corta con alta probabilidad manteniendo el factor de carga de la tabla bajo. Las colisiones durante la repetición no son un problema, ya que no afectan el factor de carga.
Sin embargo, con el hash de cuco (y otros métodos que ofrecen el peor tiempo de búsqueda de O (1)?), Debe producirse un cambio de tamaño cuando la secuencia de la sonda para una clave es demasiado larga. Pero cuando las teclas se barajan durante la repetición, puede ser que creen una secuencia de sondeo demasiado larga para una tecla, lo que requiere otro cambio de tamaño, posiblemente varios, si esto sucede varias veces seguidas. La probabilidad es pequeña, especialmente con una buena función hash, pero lo he visto suceder.
¿Hay alguna forma, salvo generar explícitamente una función hash perfecta durante la repetición, para garantizar que los cambios de tamaño no puedan caer en cascada de esta manera? ¿Posiblemente específico para un esquema de resolución de colisión dado? La literatura que he encontrado hasta ahora parece pasar completamente por alto el asunto. Tenga en cuenta que también me interesa reducir las tablas hash, no solo cultivarlas.
fuente