Para escrever esta nota curta, fui solicitado por várias entrevistas recentes para a posição de desenvolvedor líder em nossa empresa. Alguns candidatos, como se viu, não são bem versados em que tipo de mecanismo é este, Dicionário, e como ele deve ser usado. Eu até me deparei com uma opinião muito radical: eles dizem que o dicionário funciona muito lentamente e, devido ao fato de que, quando é imediatamente colocado na pilha de objetos grandes (LOH), não pode ser usado em código e é melhor aplicar consultas a coleções regulares usando filtros LINQ !
Obviamente, essas não são afirmações inteiramente verdadeiras. Um dicionário como mecanismo é muito procurado tanto na criação de códigos altamente carregados quanto na implementação da lógica de negócios. O desenvolvedor deve imaginar como o dicionário está organizado, como funciona com a memória, como é caro, quantos "rastreios" ele deixará em gerações e LOH, causando uma carga desnecessária no coletor de lixo; como inicializá-lo melhor; nesses casos, é melhor usar uma coleção de pares de valores-chave, em que uma coleção classificada etc.
Neste artigo, tentaremos lidar com alguns desses problemas.
A implementação do dicionário da Microsoft é baseada, como todos sabem, no mecanismo de tabela de hash. Isso fornece em alguns cenários a complexidade constante constante O (1) que é inatingível para outros algoritmos para operações de inserção, pesquisa e exclusão. Em alguns cenários, a recusa em usar esse mecanismo está repleta de problemas significativos com o desempenho e o consumo de memória.
Uma característica importante da arquitetura é que o armazenamento de dados é organizado usando duas matrizes do mesmo tamanho:
int[] _buckets = new int[size];
Entry[] _entries = new Entry[size];
Essas matrizes armazenam dados úteis e elementos de serviço para acesso rápido a eles. Matrizes são criadas com uma margem, ou seja, quase sempre estão vazias.
A entidade auxiliar de Entrada que agrupa cada par de valor-chave é um 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>.
.
, .
: , . .
Em todos os exemplos apresentados, deve-se ter em mente que pequenos dados são usados na configuração de teste; portanto, a sobrecarga para informações de serviço é relativamente alta.
Projetos de teste podem ser encontrados aqui .