Para escribir esta breve nota, varias entrevistas recientes me solicitaron el puesto de desarrollador líder en nuestra empresa. Resultó que algunos solicitantes no están bien informados sobre qué tipo de mecanismo es este, Diccionario, y cómo debe usarse. Incluso me encontré con una opinión muy radical: dicen que el diccionario funciona muy lentamente, y debido al hecho de que cuando se coloca de inmediato en el montón de objetos grandes (LOH), no se puede usar en el código y es mejor aplicar consultas a colecciones regulares usando filtros LINQ !
Por supuesto, estas no son declaraciones completamente ciertas. Un diccionario como mecanismo tiene mucha demanda tanto en la creación de código altamente cargado como en la implementación de la lógica empresarial. El desarrollador debe imaginar cómo está organizado el diccionario, cómo funciona con la memoria, qué tan costoso es, cuántos "rastros" dejará en generaciones y LOH, causando una carga innecesaria en el recolector de basura; cómo inicializarlo mejor, en qué casos es mejor usar una colección de pares clave-valor en su lugar, en la que una colección ordenada, etc.
En este artículo trataremos de tratar algunos de estos problemas.
La implementación del diccionario de Microsoft se basa, como todos saben, en el mecanismo de la tabla hash. Esto da en algunos escenarios la complejidad constante constante O (1) que es inalcanzable para otros algoritmos para operaciones de inserción, búsqueda y eliminación. En algunos escenarios, la negativa a utilizar este mecanismo está plagada de problemas significativos con el rendimiento y el consumo de memoria.
Una característica importante de la arquitectura es que el almacenamiento de datos se organiza utilizando dos matrices del mismo tamaño:
int[] _buckets = new int[size];
Entry[] _entries = new Entry[size];
Estas matrices almacenan datos útiles y elementos de servicio para acceder rápidamente a ellos. Las matrices se crean con un margen, es decir, casi siempre están vacías.
La entidad auxiliar de entrada que envuelve cada par clave-valor es un tipo significativo:
private struct Entry
{
public uint hashCode;
public int next;
public TKey key;
public TValue value;
}
, , , _entries. , ConcurrentDictionary, . ( 64 16 8 ) , .
_entries Dictionary 85000 LOH (, , 64 3372 , 1932). , , .
Microsoft _entries , Entry? LOH (, , ). , , .
, . 12 (4 _buckets 4 hashCode next Entry). , , , 12 . ? .
Dictionary . . Dictionary<int, int> ( ). , – ( ). 500 . 13 . 500 .
, . , , , .
, _buckets _entries , «», . LOH, .
, 746 3 .
, Dictionary . , , , .NET Core TrimExcess, .
:
- , EnsureCapacity. .
- , 400 10. (80 ). new Dictionary<int, int>(10001000), 190. , , .
- , Dictionary EnsureCapacity(capacity*), . , _buckets _entries . . , EnsureCapacity(0).
- , ( ) , , Dictionary: . , . , ( ).
- TrimExcess. LOH . .
Dictionary. , Dictionary<Key, Value>, :
public class Key
{
public int Item { get; set; }
public Key(int item)
{
Item = item;
}
public override bool Equals(object obj)
{
return Item.Equals(obj);
}
public override int GetHashCode()
{
return Item.GetHashCode();
}
}
public class Value
{
public int Item { get; set; }
public Value(int item)
{
Item = item;
}
}
.
?
:
- 64 (8 ) (8 ).
- , , 8 «» .
- Item Key Value 8 , , Item 4 .
20 76 .
:
, . ? , ( 10-20-30 ) . ?
. , Dictionary<int, int>(int count) :
struct Entry<TValue>
{
public int[] Keys;
public TValue[] Values;
public Entry(int count)
{
Keys = new int[count];
Values = new TValue[count];
}
public bool TryGetValue(int key, out TValue value)
{
for (int j = 0; j < Keys.Length; ++j)
{
if (Keys[j] == key)
{
value = Values[j];
return true;
}
}
value = default(TValue);
return false;
}
}
count – -, .
.
, 18 count=10 134 count=190 ( 50 . ). ( – 29 ), ( 150) , (, ).
, (, , Entry , ).
, (callvirt GetHashCode Equals). – . , , , (generic) . .
SortedList<int, int>.
.
, .
: , . .
En todos los ejemplos presentados, debe tenerse en cuenta que se utilizan datos pequeños en la configuración de prueba; por lo tanto, la sobrecarga para la información de servicio es relativamente alta.
Los proyectos de prueba se pueden encontrar aquí .