¿Cuál es la complejidad temporal de búsqueda de un conjunto de hash teóricamente sin límite de tamaño?

Sé que en una única máquina, el tiempo de búsqueda en un conjunto de hash se cita como O(1). En los conjuntos de hash distribuidos del mundo real, será O(logn) o similar, ya que hay una jerarquía de nodos. Descargo de responsabilidad, probablemente el resto de esta pregunta no sea aplicable a la vida real, ya que vamos más allá de las palabras de moda “escala web”, “escala planetaria”, “interplanetaria…”. ahora es a escala de universo.

Digamos que estamos considerando un número verdaderamente ilimitado de claves de tamaño fijo, y vamos a construir el hardware necesario para admitir eso. Para ayudar a visualizar esto, estoy describiendo un sistema con los términos informáticos actuales. La búsqueda en el conjunto de hash siempre tiene que comenzar en el mismo punto físico, digamos que es el terminal del usuario. El conjunto está compuesto por muchas máquinas, tan pegadas entre sí como sea posible en una formación esférica llena alrededor del terminal. Dada una clave, cada máquina puede decirte si está en el conjunto o decirte qué máquina está directamente conectada a ella, y más hacia afuera en la esfera, a la que preguntar. Entonces comienzas desde el núcleo y sigues un camino hacia la superficie. También podrías pensar en esto como una red IP, ya que las búsquedas distribuidas en los conjuntos de hash son como el enrutamiento IP. O podrías pensar en esto como una búsqueda de memoria en una máquina con toneladas de RAM y cachés empaquetadas de manera eficiente.

Supongo que al final, estamos limitados por dos cosas que estoy asumiendo que son constantes aquí: qué tan densamente podemos empacar las máquinas y la velocidad de la luz. Debido a lo primero, la cantidad de claves que podemos almacenar es proporcional al volumen de nuestro sistema. Si el tiempo de búsqueda está limitado por nuestra velocidad constante de la luz, debemos considerar el radio de la esfera, que es proporcional a la raíz cúbica del volumen, por lo que tenemos un tiempo de búsqueda O(raíz cúbica). Multiplica el tamaño de nuestro conjunto por 8, y el volumen se multiplica por 8, por lo que el radio se multiplica por 2.

Pero tal vez la memoria de cada máquina sea lo suficientemente densa como para indicar muchas más máquinas de las que son posibles de colocar en una capa en la esfera (definitivamente cierto con las máquinas de propósito general de hoy en día, pero no sé acerca de algo totalmente construido para este propósito), y obtendrías una complejidad de tiempo de búsqueda logarítmica al hacer intencionalmente la esfera más dispersa. Aquí es donde mi cerebro se derrite. ¿Alguien sabe la respuesta a esto?