Collision həlli

Collision — iki fərqli açarın eyni bucket indeksinə düşməsidir. Bu, pis kodun nəticəsi deyil, riyazi olaraq qaçılmazdır.

Pigeonhole prinsipi: mümkün açarların sayı bucket-ların sayından həmişə çoxdur. 16 bucket-ə 17 açar yerləşdirsən, ən azı iki açar mütləq eyni bucket-i bölüşəcək — heç bir hash funksiyası bundan qaça bilməz.

Birthday paradoksu isə bunun nə qədər tez baş verdiyini göstərir: 365 gün olsa da, cəmi 23 nəfərlik otaqda iki nəfərin ad gününün üst-üstə düşmə ehtimalı 50%-i keçir. Hash table-a tərcüməsi: 1 milyon bucket olsa belə, təxminən 1200 açardan sonra ilk collision-un olma ehtimalı 50%-dir. Yəni collision nadir istisna deyil — normal iş rejimidir və hər hash table onu həll etmək məcburiyyətindədir.

İki əsas strategiya var.

Separate chaining — hər bucket bir kolleksiya saxlayır (əlaqəli siyahı, massiv, bəzən ağac). Collision olanda yeni cüt sadəcə həmin siyahıya əlavə olunur.

• Sadə və proqnozlaşdırıla biləndir; silmək asandır — sadəcə siyahıdan çıxarırsan.
• Load factor 1-dən böyük ola bilər (bucket-dan çox element saxlaya bilərsən).
• Hər node üçün əlavə göstərici yaddaşı; cache lokallığı zəifdir.

Open addressing — hər bucket yalnız bir cüt saxlayır. Yer tutulubsa, boş xana tapılana qədər probing aparılır:

• Linear probing: index + 1, +2, +3... — cache üçün ən yaxşısı, amma dolu xanaların bir yerə yığılmasına (primary clustering) meyllidir.
• Quadratic probing: index + 1², +2², +3²... — clustering-i azaldır, amma capacity ilə əlaqəli olaraq bəzi xanaları heç vaxt yoxlamaya bilər.
• Double hashing: addımın özü ikinci hash funksiyası ilə hesablanır — paylanma ən yaxşısı, hesablama bir az bahadır.

Open addressing-də load factor 1-i keçə bilməz və 0.7-dən sonra performans kəskin düşür.

Open addressing-in silmə problemi — bu, müsahibələrdə ən çox sevilən detaldır.

Tutaq ki, A 5-ci xanaya düşüb, B collision səbəbindən probing ilə 6-cı xanaya keçib. İndi A-nı silib xananı sadəcə boş qoysan, B-ni axtaranda 5-ci xanaya baxırsan, boş görürsən və "yoxdur" qərarı verirsən — halbuki B düz yanındadır. Probing zənciri qırılıb.

Həll: silinən xananı boş yox, tombstone (məzar daşı) kimi işarələmək — "burada nəsə vardı, axtarışa davam et". Tombstone axtarışı dayandırmır, amma yeni element üçün yer kimi istifadə oluna bilər.

Qiyməti: tombstone-lar yığıldıqca axtarış uzanır, çünki hər biri yoxlanmalıdır. Buna görə open addressing istifadə edən strukturlar vaxtaşırı tam rebuild edib tombstone-ları təmizləyir.