GetHashCode () dan Philosopher's Stone, atau garis besar singkat penggaruk

Tampaknya topik kamus, tabel hash, dan semua jenis kode hash dilukis naik turun, dan setiap pengembang kedua, yang dibangunkan dari tidur siang sekitar pukul 01:28, dengan cepat membuat sketsa algoritme penyeimbangan Hashtable di selembar kertas, sekaligus membuktikan semua properti di dalamnya. notasi big-O.

Mungkin sangat menyadari subjek percakapan kita dapat merugikan dengan menanamkan rasa percaya diri yang salah: "Sesederhana itu! Apa yang bisa salah di sini?"

Ternyata bisa! Apa sebenarnya yang dapat ditemukan dalam beberapa kisah Jumat programmer, tepat setelah program pendidikan singkat tentang apa itu tabel hash.

Karena artikelnya masih hari Jumat, program pendidikan akan menjadi sangat singkat dan secara akademis tidak ketat.

Tabel hash untuk si kecil

Tentunya, banyak dari Anda pergi ke poliklinik, kantor perumahan, kantor paspor dan institusi lain yang tingkat filantropinya meningkat dari model lama. Ketika Anda, membungkuk ke jendela, ucapkan nama belakang Anda (alamat, nomor paspor dan nomor tanda lahir), nenek dandelion di sisi lain mengangguk, berjalan terseok-seok ke dalam perut kantor, dan kemudian setelah beberapa saat membawa selembar kertas Anda : baik itu kartu medis, atau bahkan paspor baru.

Keajaiban yang memungkinkan tidak ada karyawan tercepat di dunia untuk menemukan dokumen yang diinginkan di antara ribuan lainnya tidak lebih dari tabel hash yang terwujud dalam dunia fisik:

Dengan organisasi data ini, setiap objek memiliki kode hash yang sesuai. Dalam kasus klinik, kode hash mungkin adalah nama belakang Anda.

Tabel hash sendiri adalah semacam "lemari berlaci" dengan laci, yang masing-masing berisi objek, dikelompokkan dengan cara tertentu menurut kode hashnya. Mengapa, orang bertanya-tanya, apakah pengelompokan khusus ini perlu, dan mengapa tidak menggunakan nilai hash itu sendiri sebagai tulisan di kotak? Mungkin karena sekumpulan kotak untuk semua nama keluarga yang mungkin di dunia tidak akan muat di setiap poliklinik.

: , . "" "", .

( IT), , .

, , - :

1. - - , .
   
   , "".

2. - - .
   
   , , - , - , .

3. - - , ( ).
   
   - , - , . , .

4. ( , ) . , , - , , - .

( ) .

, EF

. -

public class Document
{
  public Int32 Id {get; set;}
  public String Name {get; set;}
  ...
}

Entity Framework. - .

-:

HashSet<Document> _openDocuments;

- , , :

var newDocument = new Document(); // document is created
_openDocuments.Add(newDocument); // document is open, nobody else can edit it.

context.Documents.Add(newDocument);
await context.SaveChangesAsync(); // so it's safe to write the document to the DB

, test , ?

Boolean test = _openDocuments.Contains(newDocument);

, false, . , - EF Document.

EF Id , ORM . , Id 0, - :

var newDocument = new Document(); // newDocument.Id == 0
_openDocuments.Add(newDocument);

context.Documents.Add(newDocument);
await context.SaveChangesAsync(); // newDocument.Id == 42

, , - , , , Document :

public class Document
{
	public Int32 Id {get; set;}
	public String Name {get; set;}
  
	public override int GetHashCode()
 	{
    return Id;
 	}
}

: - - 0, 42.

: , , , - , GetHashCode Equals . .

, GetHashCode, .

-

- , ( ) , . [20, 20], [30, 30] [20, 20], [20, 20] [30, 30]. , -:

private static IEnumerable<Size> FilterRectangles(IEnumerable<Size> rectangles)
{
	HashSet<Size> result = new HashSet<Size>();
	foreach (var rectangle in rectangles)
    result.Add(rectangle);

	return result;
}

, , - O(n^2), O(n). , Computer Science, , , , .

HashSet , Size - FCL. , , - :

    var a = new Size(20,20).GetHashCode(); // a == 0 
    var b = new Size(30,30).GetHashCode(); // b == 0

, - ( , , , ), , -, .

, , : SizeF, , , :

var a = new SizeF(20,20).GetHashCode(); // a == 346948956
var b = new SizeF(30,30).GetHashCode(); // b == 346948956

, a b ! 346948956...

, - , FCL, :

var a = Int64.MinValue.GetHashCode(); // a == 0
var b = Int64.MaxValue.GetHashCode(); // a == 0

, .... , , .

? , :

1. .

2. - ... (. Resharper).

3. . - .