.net - hashcode c#

nuevo KeyValuePair<UInt32, UInt32>(i, j).GetHashCode(); Alta tasa de duplicados

Question

En la búsqueda de una clave compuesta rápida para Dictionary, encontré una anomalía que no puedo entender ni justificar.

En pruebas limitadas

Dictionary<KeyValuePair<UInt32, UInt32>, string>

es significativamente más lento (200: 1) que

Dictionary<KeyValuePair<UInt16, UInt16>, string>

Prueba en dos bucles de 0 a 1000 Populate y luego ContainsKey

 Poplulate ContainsKey
UInt32 92085 86578
UInt16 2201 431

El problema es ese

new KeyValuePair<UInt32, UInt32>(i, j).GetHashCode();

rinde MUCHOS duplicados.
En el bucle de i y j 1024, solo se crean 1024 valores hash únicos.

En base al comentario de avalancha de CasperOne, intenté con i * 31 yj * 97 (dos números primos) y eso resultó en 105280 único en 1024X1024. Todavía hay muchos duplicados. CasperOne Sé que no es lo mismo que al azar. Pero no es mi trabajo aleatorizar la entrada. Se supone que GetHashCode () aleatoriza la salida.

¿Por qué la gran cantidad de duplicados?

Mismo ciclo en

new KeyValuePair<UInt16, UInt16>(i, j).GetHashCode();

produce códigos hash únicos de 1024 X 1024 (perfecto).

Int32 tiene el mismo problema.

Estos valores duplicados de hash matan

Dictionary<KeyValuePair<UInt32, UInt32>, string> 

Tuple también genera muchos duplicados, no se degrada en Int32 en comparación con Int16.

Tiempo para generar el KVP sin procesar y el KPV crudo. GetCashCode es similar.

La misma anomalía con HashSet.

Dictionary<KeyValuePair<UInt32, UInt32>, string> dKVPu32 = new Dictionary<KeyValuePair<UInt32, UInt32>, string>();
Dictionary<KeyValuePair<UInt16, UInt16>, string> dKVPu16 = new Dictionary<KeyValuePair<UInt16, UInt16>, string>();
KeyValuePair<UInt32, UInt32> kvpUint32;
KeyValuePair<UInt16, UInt16> kvpUint16;
int range = 1000;
Int32 hashCode;
HashSet<Int32> kvpUint32Hash = new HashSet<Int32>();
HashSet<Int32> kvpUint16Hash = new HashSet<Int32>();
Stopwatch sw = new Stopwatch();
sw.Start();
for (UInt32 i = 0; i < range; i++)
{
for (UInt32 j = 0; j < range; j++)
{
kvpUint32 = new KeyValuePair<UInt32, UInt32>(i, j);
}
}
Console.WriteLine("UInt32 raw " + sw.ElapsedMilliseconds.ToString());
// 7
sw.Restart();
for (UInt16 i = 0; i < range; i++)
{
for (UInt16 j = 0; j < range; j++)
{
kvpUint16 = new KeyValuePair<UInt16, UInt16>(i, j);
}
}
Console.WriteLine("UInt16 raw " + sw.ElapsedMilliseconds.ToString());
// 6
sw.Restart();
for (UInt32 i = 0; i < range; i++)
{
for (UInt32 j = 0; j < range; j++)
{
hashCode = new KeyValuePair<UInt32, UInt32>(i, j).GetHashCode();
kvpUint32Hash.Add(hashCode);
}
}
Console.WriteLine("UInt32 GetHashCode " + sw.ElapsedMilliseconds.ToString() + " unique count " + kvpUint32Hash.Count.ToString());
// 285 1024
sw.Restart();
for (UInt16 i = 0; i < range; i++)
{
for (UInt16 j = 0; j < range; j++)
{
hashCode = new KeyValuePair<UInt16, UInt16>(i, j).GetHashCode();
kvpUint16Hash.Add(hashCode);
}
}
Console.WriteLine("UInt16 GetHashCode " + sw.ElapsedMilliseconds.ToString() + " unique count " + kvpUint16Hash.Count.ToString());
// 398 1000000
sw.Restart();
Console.ReadLine();
for (UInt32 i = 0; i < range; i++)
{
for (UInt32 j = 0; j < range; j++)
{
dKVPu32.Add(new KeyValuePair<UInt32, UInt32>(i, j), String.Format("{0} {1}", i.ToString(), j.ToString()));
}
}
Console.WriteLine("hsKVPu32 pop " + sw.ElapsedMilliseconds.ToString());
// 92085
sw.Restart();
for (UInt32 i = 0; i < range; i++)
{
for (UInt32 j = 0; j < range; j++)
{
if (!dKVPu32.ContainsKey(new KeyValuePair<UInt32, UInt32>(i, j))) Debug.WriteLine("Opps"); ;
}
}
Console.WriteLine("hsKVPu32 find " + sw.ElapsedMilliseconds.ToString());
// 86578
dKVPu32.Clear();
dKVPu32 = null;
GC.Collect();
sw.Restart();
for (UInt16 i = 0; i < range; i++)
{
for (UInt16 j = 0; j < range; j++)
{
dKVPu16.Add(new KeyValuePair<UInt16, UInt16>(i, j), String.Format("{0} {1}", i.ToString(), j.ToString()));
}
}
Console.WriteLine("hsKVPu16 pop " + sw.ElapsedMilliseconds.ToString());
// 2201
sw.Restart();
for (UInt16 i = 0; i < range; i++)
{
for (UInt16 j = 0; j < range; j++)
{
if (!dKVPu16.ContainsKey(new KeyValuePair<UInt16, UInt16>(i, j))) Debug.WriteLine("Opps"); ;
}
}
sw.Stop();
Console.WriteLine("hsKVPu16 find " + sw.ElapsedMilliseconds.ToString());
// 431

PS El más rápido es empacar .EG ((UInt32) int1 << 16) | int2;

El hash de la primera columna UInt32 es igual al hash de KVP de los siguientes dos.

2281371105 8 992
2281371104 8 993
2281371107 8 994

2281371145 0 0
2281371147 0 2
2281371149 0 4
2281371151 0 6
2281371137 0 8

2281371144 0 1
2281371146 0 3
2281371148 0 5
2281371150 0 7
2281371136 0 9

2281371144 1 0
2281371145 1 1
2281371146 1 2
2281371147 1 3
2281371148 1 4
2281371149 1 5
2281371150 1 6
2281371151 1 7
2281371136 1 8
2281371137 1 9

2281371147 2 0
2281371146 2 1
2281371144 2 3
2281371151 2 4
2281371150 2 5
2281371149 2 6
2281371148 2 7
2281371139 2 8

El único patrón que he encontrado es que coincide con la suma o la diferencia o el KVP.
Pero no pudo encontrar un patrón para cuándo sumar y cuándo restar.
Es un hash malo, por lo que saber de qué se trata tiene poco valor.

Answer 1

La regla básica es siempre anular GetHashCode si quieres que muchas de tus cosas se pongan en una estructura que tenga como un diccionario. Puede usar esta extensión para ver qué tan bien se llena un diccionario. Informará espacios vacíos, llaves duplicadas y demás. A punto de ponerlo en sourceforge, pero aquí está;

using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Linq;
using System.Reflection;
// This unit is Freeware. It was developed by Jerremy Koot & Ivo Tops. July 2011
//
// Version By Changes
// ======= ===== ==============================================================
// v1.02 Ivo Removed not-working Hashtable support and simplified code
// v1.01 Ivo Lowered memory usage
// v1.00 I&J First Version
namespace FastLibrary
{
/// <summary>
/// Static Extension Methods for Dictionary, ConcurrentDictionary and HashSet
/// </summary>
public static class ExtHashContainers
{
/// <summary>
/// Checks a dictionary for performance statistics
/// </summary>
public static string Statistics<TKey, TValue>(this Dictionary<TKey, TValue> source)
{
return ExamineData(source.Keys, source);
}
/// <summary>
/// Checks a concurrent dictionary for performance statistics
/// </summary>
public static string Statistics<TKey, TValue>(this ConcurrentDictionary<TKey, TValue> source)
{
return ExamineData(source.Keys, source);
}
/// <summary>
/// Checks a HashSet for performance statistics
/// </summary>
public static string Statistics<TKey>(this HashSet<TKey> source)
{
return ExamineData(source, source);
}
private static string ExamineData<TKey>(ICollection<TKey> source, Object hashContainer)
{
if (!source.Any()) return "No Data found.";
// Find Buckets
var b = GetBuckets(hashContainer);
if (b < 0) return ("Unable to get Buckets Field for HashContainer");
// Create our counting temp dictionaries
var d = new int[b];
var h = new Dictionary<int, int>(source.Count);
// Find Hash Collisions and Bucket Stats
foreach (var k in source)
{
var hash = k.GetHashCode() & 0x7FFFFFFF; // Hashes are stripped of sign bit in HashContainers
int bucket = hash%b; // .NET Hashers do not use negative hashes, and use % voor bucket selection
// Bucket Stats
d[bucket]++;
// Hashing Stats
int c;
if (h.TryGetValue(hash, out c)) h.Remove(hash);
else c = 0;
c++;
h.Add(hash, c);
}
// Do some math
var maxInBucket = d.Max(q => q);
var maxSameHash = h.Values.Max(q => q);
var emptyBuckets = d.Count(q => q == 0);
var emptyStr = b == 0 ? "0" : ((float) (emptyBuckets)/b*100).ToString("0.0");
var worstHash = (from i in h where i.Value == maxSameHash select i.Key).FirstOrDefault();
// Report our findings
var r = Environment.NewLine + hashContainer.GetType().Name + " has " + b + " buckets with " + source.Count +
" items. " +
Environment.NewLine + "The Largest bucket contains " + maxInBucket + " items. " +
Environment.NewLine + "It has " + (emptyBuckets) +
" empty buckets (" + emptyStr + "%)" + Environment.NewLine + "Each non-empty bucket has on average " +
((source.Count/(float) (b - emptyBuckets))).ToString("0.0") + " items." + "The " + source.Count +
" items share " + h.Count +
" unique hashes. ";
if (maxSameHash > 1)
r += Environment.NewLine + "The largest collision has " + maxSameHash +
" items sharing the same hash, which == " + worstHash;
return r;
}
private static Int32 GetBuckets(object dictionary)
{
var type = dictionary.GetType();
while (type != null && !type.IsGenericType) type = type.BaseType;
if (type == null) return -1;
string field = null;
if (type.GetGenericTypeDefinition() == typeof (Dictionary<,>)) field = "buckets";
if (type.GetGenericTypeDefinition() == typeof (ConcurrentDictionary<,>)) field = "m_buckets";
if (type.GetGenericTypeDefinition() == typeof (HashSet<>)) field = "m_buckets";
if (field == null) return -1;
var bucketsField = type.GetField(field, BindingFlags.NonPublic | BindingFlags.Instance);
if (bucketsField == null) return -1;
var buckets = bucketsField.GetValue(dictionary);
if (buckets == null) return -1;
var length = buckets.GetType().GetProperty("Length");
return (int) length.GetGetMethod().Invoke(buckets, null);
}
}
}

Answer 2

Como han mencionado otros contestadores, KeyValuePair no anula GetHashCode , y la implementación predeterminada de GetHashCode para structs no es la mejor . En su lugar, puede utilizar tuplas de dos elementos para esto, por ejemplo

var dict = new Dictionary<Tuple<uint, uint>, string>();
dict.Add(Tuple.Create(1u, 2u),"xxx"); // Tuples override GetHashCode

Sin embargo, tenga en cuenta que esto agregará una sobrecarga adicional para la asignación adicional del montón Tuple. (sin embargo, está parcialmente compensado, ya que cuando llamas a GetHashCode en una estructura que no lo anula, lo encierras implícitamente)

Answer 3

Como GetHashCode devuelve un Int32 , cada par de Int16 s (o UInt16 s) puede devolver fácilmente un valor único. Con un par de Int32 s, necesitaría combinar los valores de alguna manera para ser compatible con su diseño.

KeyValuePair no anula GetHashCode() , por lo que solo está utilizando la implementación predeterminada de ValueType.GetHashCode() , y la documentación para ello dice lo siguiente:

(desde: http://msdn.microsoft.com/en-us/library/system.valuetype.gethashcode.aspx )

Si llama al método GetHashCode del tipo derivado, es probable que el valor de retorno no sea adecuado para usar como clave en una tabla hash. Además, si el valor de uno o más de esos campos cambia, el valor de retorno puede no ser adecuado para usarlo como clave en una tabla hash. En cualquier caso, considere escribir su propia implementación del método GetHashCode que represente más de cerca el concepto de un código hash para el tipo.

Como KeyValuePair no anula GetHashCode() , supongo que no está destinado a ser utilizado como una clave de Dictionary .

Además, según esta pregunta y este código C # , la implementación predeterminada de ValueType.GetHashCode() simplemente selecciona el primer campo no estático y devuelve el resultado de su método GetHashCode() . Esto explica la gran cantidad de duplicados para KeyValuePair<UInt32, UInt32> , aunque no explica la falta de duplicados para KeyValuePair<UInt16, UInt16> .

Supongo que para KeyValuePair<UInt32, UInt32> , GetHashCode() simplemente devuelve GetHashCode() del primer valor, y para KeyValuePair<UInt16, UInt16> , GetHashCode() combina los valores que dan como resultado un hash único para cada par de valores, ya que es posible y directo hacerlo.

Answer 4

En primer lugar, podemos prescindir del aspecto de temporización de esto: me parece que esto realmente se trata de colisiones hash, ya que obviamente eso matará el rendimiento.

Entonces, la pregunta es realmente por qué hay más colisiones hash para KeyValuePair<uint, uint> que KeyValuePair<ushort, ushort> . Para ayudar a descubrir un poco más sobre eso, he escrito el siguiente programa corto:

using System;
using System.Collections.Generic;
class Program
{
const int Sample1 = 100;
const int Sample2 = 213;
public static void Main()
{
Display<uint, ushort>();
Display<ushort, ushort>();
Display<uint, uint>();
Display<ushort, uint>();
}
static void Display<TKey, TValue>()
{
TKey key1 = (TKey) Convert.ChangeType(Sample1, typeof(TKey));
TValue value1 = (TValue) Convert.ChangeType(Sample1, typeof(TValue));
TKey key2 = (TKey) Convert.ChangeType(Sample2, typeof(TKey));
TValue value2 = (TValue) Convert.ChangeType(Sample2, typeof(TValue));
Console.WriteLine("Testing {0}, {1}", typeof(TKey).Name, typeof(TValue).Name);
Console.WriteLine(new KeyValuePair<TKey, TValue>(key1, value1).GetHashCode());
Console.WriteLine(new KeyValuePair<TKey, TValue>(key1, value2).GetHashCode());
Console.WriteLine(new KeyValuePair<TKey, TValue>(key2, value1).GetHashCode());
Console.WriteLine(new KeyValuePair<TKey, TValue>(key2, value2).GetHashCode());
Console.WriteLine();
}
}

La salida en mi máquina es:

Testing UInt32, UInt16
-1888265981
-1888265981
-1888265806
-1888265806
Testing UInt16, UInt16
-466800447
-459525951
-466800528
-459526032
Testing UInt32, UInt32
958334947
958334802
958334802
958334947
Testing UInt16, UInt32
-1913331935
-1913331935
-1913331935
-1913331935

Obviamente, puede intentar variar los valores de muestra para ver dónde hay colisiones.

Los resultados de KeyValuePair<ushort, uint> son particularmente preocupantes, y los resultados de KeyValuePair<ushort, ushort> son sorprendentemente buenos.

De hecho, KeyValuePair<ushort, uint> no es solo malo - es ridículamente malo por lo que puedo ver - No tengo que encontrar ningún valor que no tenga el mismo código hash de -1913331935 cuando ejecuto el 64 bit CLR. Al ejecutar el CLR de 32 bits, obtengo un código hash diferente, pero igual el mismo código hash para todos los valores.

Parece que en .NET 4.5 (que es lo que estoy ejecutando), la implementación predeterminada de GetHashCode no solo toma el campo de primera instancia de la estructura, como se documentó previamente. Sospecho que al menos para algunos tipos, solo usa los primeros 4 bytes de memoria más allá del encabezado en el valor en caja (y habrá boxeo para cada llamada aquí), y eso termina siendo el primer campo (si campo es una uint ), a veces siendo más de un campo (por ejemplo, para ushort, ushort donde ambos campos pueden caber "dentro" de 4 bytes) y algunas veces no son campos en absoluto ( ushort, uint ).

(En realidad, esto no explica por qué obtienes 1024 códigos hash diferentes en el caso uint, uint lugar de solo 1000. Todavía no estoy seguro de eso).

En definitiva, utilizar un tipo de valor que no anule GetHashCode como clave de diccionario parece una mala idea, a menos que lo haya probado para asegurarse de que sea adecuado para sus requisitos específicos. Simplemente hay demasiada magia negra para tener confianza, IMO.