Buenas, no entiendo mucho la diferencia entre un arreglo de bits de tamaño n y una tabla hash de tamaño n que distribuye uniformemente.
Lo que había entendido de negativo del arreglo de bits era el tamaño que ocupaba en memoria, pero si tenes una tabla del mismo tamaño no le veo la ventaja.
Pensaría que si espero tener n elementos en mi conjunto, con una tabla de tamaño n/k, que haya k elementos en cada lista igual lo hace de O(k) o sea constante.
Mi razonamiento es correcto?
Hola Luciano.
Para usar un arreglo de bits (o booleanos) cada elemento del universo debería corresponderse de manera única con una posición: [0:N]. Si tu universo son enteros arbitrarios, números reales, strings arbitrarios, lo anterior no sería posible.
La tablas de hash permiten tener un universo sin tantas restricciones; se usa una función de hash para mapear elementos del universo a los enteros. Aquí la tabla (arreglo) almacena para cada posición los elementos que tienen el mismo valor respecto a la función de hash. Cuando dos elementos tienen el mismo valor por la función de hash se dice que hay una colisión. En hashing abierto las colisiones se resuelven guardando en cada posición de la tabla una lista (generalmente). Se busca que el número de colisiones sea bajo para que el orden de tiempo de ejecución se aproxime al de los arreglos de bits (booleanos): O(1) promedio. Para esto es importante que la función de hash distribuya los elementos uniformemente en la tabla (con similar probabilidad) y que el tamaño de la tabla sea aproximadamente igual a la cantidad de elementos esperados. Esta cantidad no es la misma que se considera en los arreglos de bits (booleanos), no refiere al tamaño del universo de datos sino a cuántos elementos de dicho universo se espera almacenar. Por ejemplo, el universo podría ser los enteros, pero se esperan guardar aproximadamente M elementos (arbitrarios de int).
Espero que estos comentarios te ayuden a entender mejor las diferencias entre arreglos de bits (booleanos) y las tablas de hash.
Saludos, Carlos
Sí, se entendio perfectamente, muchas gracias!