C# Dictionary Memory Management

Question

Tengo un Dictionary<string,int> que tiene el potencial de contener más de 10+ millones de claves únicas. Estoy tratando de reducir la cantidad de memoria que esto requiere, manteniendo la funcionalidad del diccionario.

Tuve la idea de almacenar un hash de la cadena como un largo, esto disminuye el uso de memoria de las aplicaciones a una cantidad aceptable (~ 1.5 gigas a ~ .5 gigas), pero no me siento muy bien acerca de mi método para hacer esto.

long longKey= 
BitConverter.ToInt64(cryptoTransformSHA1.ComputeHash(enc.GetBytes(strKey)), 0); 

Básicamente esto corta la final de un hash SHA1, y pone la primera parte de ella en un largo, que luego utilizo como una clave. Si bien esto funciona, al menos para los datos con los que estoy probando, no creo que esta sea una solución muy confiable debido a la mayor posibilidad de colisiones clave.

¿Hay alguna otra forma de reducir la huella de memoria del diccionario, o el método que he descrito anteriormente no es tan horrible como creo que es?

[edit] Para aclarar, necesito mantener la capacidad de buscar un valor contenido en el Diccionario usando una cadena. Almacenar la cadena real en el diccionario lleva a mucha memoria. Lo que me gustaría hacer en su lugar es usar un Dictionary<long,int> donde el largo es el resultado de una función de hashing en la cadena.

Answer 1

Así que he hecho algo similar recientemente y por una serie de razones que son bastante exclusivas de mi aplicación no usé una base de datos De hecho, intenté dejar de usar una base de datos. Descubrí que GetHashCode se mejoró significativamente en 3.5. Una nota importante, NUNCA ALMACENE PERSISTENTEMENTE LOS RESULTADOS DE GetHashCode. NUNCA JAMÁS. No se garantiza que sean consistentes entre las versiones del marco.

Así que realmente necesita realizar un análisis de sus datos ya que las diferentes funciones hash podrían funcionar mejor o peor en sus datos. También necesita dar cuenta de la velocidad. Como regla general, las funciones hash criptográficas no deberían tener muchas colisiones, incluso si el número de hash se mueve a miles de millones. Para las cosas que necesito para ser único, generalmente utilizo SHA1 Managed. En general, CryptoAPI tiene un rendimiento terrible, incluso si las funciones hash subyacentes funcionan bien.

Para un hash de 64 bits Actualmente uso Lookup3 y FNV1, que son hashes de 32 bits, juntos. Para que ocurra una colisión, ambos tendrían que colisionar, lo que es matemáticamente improbable y no he visto pasar más de 100 millones de hashes. Puede encontrar el código disponible públicamente en la web.

Realice su propio análisis. Lo que funcionó para mí puede no funcionar para usted. En realidad, dentro de mi oficina, diferentes aplicaciones con diferentes requisitos en realidad usan diferentes funciones hash o combinaciones de funciones hash.

Evitaría cualquier función hash no comprobada. Hay tantas funciones hash como personas que piensan que deberían escribirlas. Haga su prueba de investigación y prueba de prueba.

Answer 2

¿Por qué no solo usa GetHashCode() para obtener un hash de la cadena?

Answer 3

Con las implementaciones de tabla hash con las que he trabajado anteriormente, el hash te lleva a un depósito que a menudo es una lista de enlaces de otros objetos que tienen el mismo hash. Los valores hash no son únicos, pero son lo suficientemente buenos como para dividir los datos en listas muy manejables (a veces solo 2 o 3 de largo) que luego puede buscar para encontrar su elemento real.

La clave para un buen hash no es su exclusividad, sino su velocidad y capacidad de distribución ... quiere que se distribuya lo más uniformemente posible.

Answer 4

Por cierto, las funciones hash/hash criptográficas son excepcionalmente malas para los diccionarios. Son grandes y lentos Al resolver el problema (tamaño) solo ha introducido otro problema más grave: la función no distribuirá la entrada de manera uniforme por más tiempo, destruyendo así la propiedad más importante de un buen hash para abordar el direccionamiento libre de colisiones (como parece que te has dado cuenta)

/EDITAR: Como Andrew ha notado, GetHashCode es la solución para este problema ya que ese es su uso previsto. Y como en un diccionario verdadero, tendrás que evitar las colisiones. Uno de los mejores esquemas para eso es double hashing. Desafortunadamente, la única forma 100% confiable será almacenar los valores originales. De lo contrario, hubieras creado una compresión infinita, que sabemos que no puede existir.

Answer 5

Con 10 millones de registros impares, ¿ha considerado utilizar una base de datos con un índice no agrupado? Las bases de datos tienen muchos más trucos bajo la manga para este tipo de cosas.

Hashing, por definición, y bajo cualquier algoritmo, tiene el potencial de colisiones, especialmente con grandes volúmenes. Dependiendo de la situación, sería muy cauteloso con esto.

Usar las cuerdas puede ocupar espacio, pero es confiable ...si está en x64, no es necesario que sea demasiado grande (aunque definitivamente cuenta como "grande" ;-))

Answer 6

Simplemente vaya a SQLite. No es probable que le gane, e incluso si lo hace, probablemente no valga la pena el tiempo/esfuerzo/complejidad.

SQLite.