c# - ¿Qué sucede cuando ocurre una colisión de hash en la clave de diccionario?

collision-detection

Question

He estado codificando en c ++ y en java la totalidad de mi vida, pero en C #, siento que es un animal totalmente diferente.

En caso de colisión hash en el contenedor Diccionario en c #, ¿qué hace? ¿O incluso detecta la colisión?

En caso de colisiones en contenedores similares en SDL, algunos harían que una sección de valores clave vinculara los datos con una sección de valores clave como la lista enlazada, o algunos intentarían encontrar un método hash diferente.

[Actualización 10:56 AM 6/4/2010]

Estoy tratando de hacer un contador por usuario. Y el número de usuario establecido no está definido, puede aumentar o disminuir. Y estoy esperando que el tamaño de los datos sea superior a 1000.

Entonces yo quiero :

• Acceso rápido, preferiblemente no O (n). Es importante que tenga cerca de O (1) debido a los requisitos, debo asegurarme de que puedo forzar el cierre de sesión de las personas antes de que puedan ejecutar algo tonto.
• Crecimiento dinámico y encogimiento.
• datos únicos

Hashmap fue mi solución, y parece que Dictionary es lo que es similar a hashmap en c # ...

Answer 1

Consulte este enlace para obtener una buena explicación: un examen exhaustivo de las estructuras de datos utilizando C # 2.0

Básicamente, el diccionario genérico .NET encadena elementos con el mismo valor hash.

Answer 2

De acuerdo con este artículo en MSDN , en el caso de una colisión de hash, la clase del Dictionary convierte el cubo en una lista vinculada. La clase más antigua de HashTable , por otro lado, usa el refrito.

Answer 3

Ofrezco una respuesta alternativa orientada al código que demuestra que un Diccionario exhibirá un comportamiento funcionalmente libre de excepciones cuando se agregan dos elementos con claves diferentes pero las claves producen el mismo código hash.

En .Net 4.6 las cadenas "699391" y "1241308" producen el mismo código hash. ¿Qué pasa en el siguiente código?

myDictionary.Add( "699391", "abc" );
myDictionary.Add( "1241308", "def" );

El siguiente código demuestra que un Diccionario .Net acepta diferentes claves que causan una colisión de hash. No se produce ninguna excepción y la búsqueda de claves del diccionario devuelve el objeto esperado.

var hashes = new Dictionary<int, string>();
var collisions = new List<string>();

for (int i = 0; ; ++i)
{
    string st = i.ToString();
    int hash = st.GetHashCode();

    if (hashes.TryGetValue( hash, out string collision ))
    {
        // On .Net 4.6 we find "699391" and "1241308".
        collisions.Add( collision );
        collisions.Add( st );
        break;
    }
    else
        hashes.Add( hash, st );
}
Debug.Assert( collisions[0] != collisions[1], "Check we have produced two different strings" );
Debug.Assert( collisions[0].GetHashCode() == collisions[1].GetHashCode(), "Prove we have different strings producing the same hashcode" );

var newDictionary = new Dictionary<string, string>();
newDictionary.Add( collisions[0], "abc" );
newDictionary.Add( collisions[1], "def" );

Console.Write( "If we get here without an exception being thrown, it demonstrates a dictionary accepts multiple items with different keys that produce the same hash value." );

Debug.Assert( newDictionary[collisions[0]] == "abc" );
Debug.Assert( newDictionary[collisions[1]] == "def" );

Answer 4

Dictionary<> maneja correctamente las colisiones de hash, ya que mientras un objeto implemente GetHashCode() y Equals() correctamente, se devolverá la instancia correspondiente del diccionario.

Primero, no debe hacer suposiciones acerca de cómo funciona el Dictionary<> internamente, es un detalle de la implementación que es probable que cambie con el tiempo. Una vez dicho esto....

Lo que debería preocuparte es si los tipos que estás usando para las claves implementan GetHashCode() y Equals() correctamente. Las reglas básicas son que GetHashCode() debe devolver el mismo valor durante la vida útil del objeto, y que Equals() debe devolver verdadero cuando dos instancias representan el mismo objeto. A menos que lo Equals() , Equals() usa la igualdad de referencia, lo que significa que solo devuelve true si dos objetos son en realidad la misma instancia. Puede anular el funcionamiento de Equals() , pero luego debe asegurarse de que dos objetos que sean ''iguales'' también produzcan el mismo código hash.

Desde el punto de vista del rendimiento, es posible que también desee proporcionar una implementación de GetHashCode() que genere una buena distribución de valores para reducir la frecuencia de colisión del código de hash. El principal inconveniente de las colisiones de hashcode es que reduce el diccionario a una lista en términos de rendimiento. Cada vez que dos instancias de objeto diferentes producen el mismo código hash, se almacenan en el mismo grupo interno del diccionario. El resultado de esto, es que se debe realizar un escaneo lineal, llamando a Equals() en cada instancia hasta que se encuentre una coincidencia.