¿Qué estructuras de datos son más eficientes que las tablas hash?

Cubos Una tabla hash es solo un montón de cubos con alguna forma de lidiar con las colisiones. Sin embargo, los cubos están bastante limitados al tamaño de los datos.

Aún así, una vez vi un artículo que mostraba que uno podía rastrear de manera eficiente una escena al precalcular todos los rayos posibles, a una determinada resolución, y almacenarlos en caché de una manera particularmente concisa.

Si su requisito es probar la membresía de un elemento en un conjunto de gran número de elementos de una manera rápida y eficiente en el espacio, Bloom Filter podría ser útil. Es una estructura de datos probabilística y es mucho más eficiente en espacio que las tablas hash, ya que en realidad no almacena los elementos.
Para consultas de membresía de conjunto, responde si un elemento “definitivamente no está en un conjunto” o “podría estar allí en un conjunto”. Por lo tanto, puede tener algunos falsos positivos, pero no hay falsos negativos.
Sin embargo, un filtro Bloom no puede reemplazar completamente una tabla hash porque ambos sirven para diferentes propósitos.

Más explicación: filtro Bloom

comprueba las matrices judy, los árboles rojos y negros