Untuk menulis catatan singkat ini, saya diminta oleh beberapa wawancara baru-baru ini untuk posisi pengembang utama di perusahaan kami. Beberapa pelamar, ternyata, tidak berpengalaman dalam mekanisme seperti apa ini, Kamus, dan bagaimana seharusnya digunakan. Saya bahkan menemukan pendapat yang sangat radikal: mereka mengatakan bahwa kamus bekerja sangat lambat, dan karena fakta bahwa ketika ditempatkan langsung di tumpukan objek besar (LOH), itu tidak dapat digunakan dalam kode dan lebih baik untuk menerapkan kueri ke koleksi reguler menggunakan filter LINQ !
Tentu saja, ini bukan pernyataan yang sepenuhnya benar. Kamus sebagai mekanisme sangat sering dibutuhkan baik dalam membangun kode yang sangat dimuat maupun dalam mengimplementasikan logika bisnis. Pengembang harus membayangkan bagaimana kamus disusun, bagaimana kerjanya dengan memori, berapa mahal itu, berapa banyak "jejak" yang akan ditinggalkan secara turun-temurun dan LOH, menyebabkan beban yang tidak perlu pada pengumpul sampah; bagaimana menginisialisasi dengan lebih baik, dalam hal ini lebih baik menggunakan koleksi pasangan nilai kunci, di mana koleksi diurutkan, dll.
Pada artikel ini kami akan mencoba menangani beberapa masalah ini.
Implementasi kamus dari Microsoft didasarkan, seperti yang diketahui semua orang, pada mekanisme tabel hash. Ini memberikan dalam beberapa skenario yang tidak dapat dicapai untuk algoritma lain kompleksitas konstan ideal O (1) untuk memasukkan, mencari, dan menghapus operasi. Dalam beberapa skenario, penolakan untuk menggunakan mekanisme ini dipenuhi dengan masalah yang signifikan dengan kinerja dan konsumsi memori.
Fitur penting dari arsitektur adalah penyimpanan data diatur menggunakan dua array dengan ukuran yang sama:
int[] _buckets = new int[size];
Entry[] _entries = new Entry[size];
Array ini menyimpan data dan elemen layanan yang berguna untuk akses cepat ke mereka. Array dibuat dengan margin, artinya hampir selalu kosong.
Entitas pembantu entri yang membungkus setiap pasangan nilai kunci adalah tipe signifikan:
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>.
.
, .
: , . .
Dalam semua contoh yang disajikan, harus diingat bahwa data kecil digunakan dalam konfigurasi pengujian, oleh karena itu, overhead untuk informasi layanan relatif tinggi.
Proyek uji dapat ditemukan di sini .