¿Colección 'adecuada' para usar para obtener elementos en O (1) vez en C# .NET?

Question

algo que hago a menudo si estoy almacenar un montón de valores de cadena y quiero ser capaz de encontrarlos en O (1) tiempo después decir:

foreach (String value in someStringCollection) 
{ 
    someDictionary.Add(value, String.Empty); 
} 

De esta manera, puedo realizar cómodamente constante -Tiempo búsquedas sobre estos valores de cadena más adelante, tales como:

if (someDictionary.containsKey(someKey)) 
{ 
    // etc 
} 

Sin embargo, me siento como si estuviera engañando, haciendo que el valor String.Empty. ¿Hay una colección .NET más apropiada que debería estar usando?

Answer 1

Si está utilizando .Net 3.5, intente HashSet. Si no está usando .Net 3.5, intente con C5. De lo contrario, su método actual está bien (bool como @leppie sugiere que es mejor, o no como sugiere @JonSkeet, dun dun dun!).

HashSet<string> stringSet = new HashSet<string>(someStringCollection); 

if (stringSet.Contains(someString)) 
{ 
    ... 
} 

Answer 2

Puede utilizar HashSet<T> en .NET 3.5, que yo lo que sólo se adhieren a método actual (en realidad yo preferiría Dictionary<string,bool> pero uno no siempre tiene ese lujo).

Answer 3

algo que es posible que desee agregar es un tamaño inicial a su hash. No estoy seguro si C# se implementa de forma diferente que Java, pero generalmente tiene un tamaño predeterminado, y si agrega más que eso, amplía el conjunto. Sin embargo, un hash de tamaño adecuado es importante para lograr lo más cerca posible de O (1). El objetivo es obtener exactamente 1 entrada en cada segmento, sin que sea realmente enorme. Si realiza alguna búsqueda, sé que hay una proporción sugerida para dimensionar la tabla hash, suponiendo que sabe de antemano cuántos elementos va a agregar. Por ejemplo, algo así como "el hash debe tener el tamaño de 1.8x la cantidad de elementos que se agregarán" (no la proporción real, solo un ejemplo).

De Wikipedia:

Con una buena función hash, una tabla hash normalmente puede contener aproximadamente 70% -80% tantos elementos como lo hace ranuras de mesa y todavía funciona bien. Dependiendo del mecanismo de resolución de colisiones , el rendimiento puede comenzar a sufrir gradualmente o dramáticamente a medida que se agregan más elementos . Para hacer frente a esto, cuando el factor de carga supera cierto umbral, es necesario para asignar una nueva tabla más grande , y agregar todo el contenido de la tabla original a esta nueva tabla. En la clase HashMap de de Java, por ejemplo, el umbral del factor de carga predeterminado es 0,75.

Answer 4

Probablemente debería hacer esto una pregunta, porque veo el problema tan a menudo. ¿Qué te hace pensar que los diccionarios son O (1)? Técnicamente, lo único que probablemente sea algo así como O (1) es el acceso a una matriz de encuadernación fija indexada con enteros estándar usando un valor de índice entero (no hay búsqueda en las matrices implementadas de esa manera).

La presunción de que si se ve como una matriz de referencia que es O (1) cuando el "índice" es un valor que debe pueden consultar alguna manera, sin embargo detrás de las escenas, significa que no es probable una junta (1) esquema a menos que tenga la suerte de obtener una función hash con datos que no tengan colisiones (y probablemente muchas celdas desperdiciadas).

Veo estas preguntas e incluso veo respuestas que dicen O (1) [no sobre esta pregunta en particular, pero sí las veo], sin justificación o explicación de lo que se requiere para asegurar que O (1) en realidad se logra.

Hmm, supongo que esta es una pregunta decente. Lo haré después de publicar este comentario aquí.