¿Distinción de elementos en el tiempo O (n)?

Todos sabemos que la distinción de elementos en el modelo basado en la comparación no se puede hacer en el tiempo . Sin embargo, en una palabra RAM, uno posiblemente puede lograr mejor.$o(n\log n)$

Por supuesto, si uno asume la existencia de una función hash perfecta que se puede calcular en tiempo lineal, obtenemos un algoritmo de tiempo lineal para la distinción de elementos: simplemente siga numerando uno por uno y devuelva 1 si hay una colisión.

Sin embargo, hay dos problemas: 1) la mayoría de las construcciones de funciones hash perfectas que pude encontrar aleatoriedad utilizada y 2) No puedo encontrar una discusión sobre el tiempo de preprocesamiento en ningún lado, es decir, el tiempo requerido para decidir qué función hash se va a utilizar. utilizar en función del conjunto de números de entrada.

Fredman et al. " Almacenar una tabla dispersa con peor caso de acceso$O(1)$ " resuelve el primer problema al proporcionar una función hash con tiempo de acceso en el peor de los casos, pero no dice nada sobre el segundo problema .$O(1)$

En resumen, esto es lo que quiero:

Diseñar un algoritmo que, dado un conjunto de n números (cada número siendo w bits de longitud) sobre una palabra-RAM con longitud de palabra w , encuentra una función hash h : S → { 1 , ... , m } en O ( n ) tiempo , donde m = O ( n ) . La función h debe tener la propiedad de que para cualquier j ∈ { 1 , ... , m } , el número de elementos de$S$$n$$w$$w$$h:S\rightarrow \{1, \ldots , m\}$$O(n)$$m = O(n)$$h$$j \in \{1, \ldots , m\}$ ese mapa a j es una constanteycalcular h ( i ) debería llevar O ( 1 ) tiempo en un modelo "razonable" de palabra-RAM, es decir, el modelo no debería permitir que se evalúen funciones "exóticas" en las palabras en O ( 1 ) tiempo.$S$$j$$h(i)$$O(1)$$O(1)$

También me gustaría saber si hay algoritmos para resolver la distinción de elementos en la palabra RAM que no utilizan funciones hash en absoluto.

$O(n\log\log n)\subset o(n\log n)$

$O(n\log\log n)$$n$$w$$O(n\log\log n)$

Hasta donde yo sé, ese es el mejor resultado conocido hasta el día de hoy.

Eso es exactamente lo que hace el documento FKS que mencionas, y lleva tiempo lineal (en expectativa). Vea la página 5 aquí para el análisis ... http://www1.icsi.berkeley.edu/~luby/PAPERS/pairwise.ps