Hashing tələləri: Hashable və == uyğunluğu

1. Hashing-i xatırlayırıq

İlk dəfə “hashing” sözünü eşidəndə belə düşünmək asandır: “Axı bərabərlik == var, gəlin sadəcə onu müqayisə edək”. Amma hər yeni elementi artıq saxlanılanların hamısı ilə müqayisə etsəniz — bu, xətti axtarış olacaq və böyük verilənlərdə “ağrımağa” başlayacaq. Hashing — namizədlər dairəsini tez daraltmaq üsuludur: əvvəlcə hash hesablayırıq (sanki “rəfin indeksi” kimi), sonra isə lazım gələrsə, müqayisələrlə dəqiqləşdiririk.

Swift-də Set və Dictionary elementlərin/açarların Hashable olmasını tələb edir. Bu sadəcə “kompilyator formallığı” deyil, müqavilədir: tip elə hashing-ə qoşula bilməlidir ki, data strukturu elementləri tez və düzgün tapa bilsin. Swift hashing modelini xüsusi olaraq inkişaf etdirib (o cümlədən Hasher və hash(into:) ilə), belə ki hash-kolleksiyalar etibarlı və proqnozlaşdırıla bilən olsun.

Təsəvvür edin ki, kitabxanadasınız. Kitabı tapmaq istəyirsiniz. Rəflər üzrə gedib hər kitabın adını lazım olanla müqayisə edə bilərsiniz. Edə bilərsiniz. Amma kitab on ədəd olanda bu, dözüləndir, on min ədəd olanda isə siz kitabxana qisasçısı karyerasına başlayacaqsınız. Hashing isə kataloq kimidir: əvvəlcə lazım olan “bölməni” tapırsınız, sonra isə bir neçə kitabın içində hansının doğru olduğunu dəqiqləşdirirsiniz.

2. Dictionary və Set hash və ==-ni necə istifadə edir

Bir əsas mexanikanı başa düşmək vacibdir: hash ==-ni əvəz etmir. Hash tez bir sahəyə düşmək üçün lazımdır, amma son həqiqəti adətən bərabərlik müqayisəsi həll edir. Bu xüsusilə vacibdir, çünki kolliziyalar (fərqli dəyərlərin eyni hash verməsi) mümkündür və normal hal sayılır.

Çox sadələşdirilmiş iş məntiqi belə görünür:

flowchart TD
    A[There is key K] --> B["Compute hash(K)"]
    B --> C[Find 'approximate place' in structure]
    C --> D{Are there already elements there?}
    D -- no --> E[Put K here]
    D -- yes --> F[Compare via == with candidates]
    F --> G{Found equal?}
    G -- yes --> H[This is the same key/element]
    G -- no --> I[Collision: store separately, but nearby]

Məna: hash “rayon ünvanı” verir, == isə — “dəqiq mənzil nömrəsi”.

Buradan dərhal iki fikir çıxır.

Birincisi: əgər bərabərlik məntiqiniz və ya hashing məntiqiniz “sınıbsa” (və ya onlar uyğun deyilsə), Set və Dictionary ev ünvanını “Pushkin küçəsi, Kolotuşkin evi” ilə axtaran insan kimi davranmağa başlayır — yəni sanki demək olar ki, düzdür, amma nəticə adətən gülünc olur.

İkincisi: kolliziyalar mümkün olduğuna görə, hash unikal olmağa borclu deyil. O, strukturu orta hesabla sürətli saxlayacaq qədər yaxşı olmalı və bərabərliklə uyğun olmalıdır — əsas kritik məqam budur.

3. Uyğunluq qanunu: a == b ⇒ eyni hash

Budur yadda saxlamalı olduğunuz əsas müqavilə (və bu, “böyüklər belə dediyi üçün” deyil, əks halda data strukturları sınacağı üçün vacibdir):

Əgər iki dəyər == ilə bərabərdirsə, onlar mütləq eyni hash verməlidirlər.

a == b ⇒ hash(a) == hash(b)

Tərsi doğru deyil və bu normaldır:

hash(a) == hash(b) ⇏ a == b

Yəni eyni hash hələ dəyərlərin bərabər olması demək deyil — bunlar kolliziyalardır və onlar icazəlidir.

Niyə qanun məhz belədir? Çünki Dictionary/Set əvvəlcə axtarışı daraltmaq üçün hash-ə istinad edir. Əgər iki bərabər dəyər birdən-birə müxtəlif hash sahələrinə “sürüşsə”, struktur saxladığı şeyi sadəcə tapa bilməyə bilər.

Bunu praktikaya yaxınlaşdırsaq, elə bil “mən kod yazıram, traktat yox” səviyyəsində düşünün: hash — “ünvanın sürətli qaralaması”, == — “pasportun yoxlanması” kimidir. Pasport sərt ola bilər, amma bərabər insanlar üçün qaralama ünvan üst-üstə düşməlidir, yoxsa ünvanla axtarış uğursuz olacaq.

Və vacib məqam: bu kursun bu mərhələsində siz adətən hash-i əl ilə yazmırsınız. Swift bir çox tip üçün hashing-i avtomatik sintez edə bilir və ümumiyyətlə elə edir ki, siz “sehrli bit sehrləri” yazmayasınız. Amma tələlər yenə də mümkündür — çünki problem çox vaxt hash formulunda deyil, nəyi bərabər saydığınızda və açarları necə formalaşdırdığınızda olur.

4. Kanonik açar: eyni fikir → eyni açar

Çox real bir tələ var: Dictionary və Set düzgündür, amma siz onlara fərqli açarlar verirsiniz, halbuki məna baxımından “eyni” istəyirsiniz.

Bu, ən çox sətirlərlə olur: boşluqlar, registr, təsadüfi ikiqat boşluqlar, "Swift" vs "swift". Burada hashing-in ümumiyyətlə günahı yoxdur: siz sadəcə məlumatı bir açarla qoyur, başqa açarla axtarırsınız.

Əziyyət çəkməmək üçün kanonik açar ideyası tətbiq edilir: bu, verilənlərin sizin hər yerdə eyni istifadə etdiyiniz normallaşdırılmış təqdimatıdır.

Mini nümunə: eyni “mətn”, amma fərqli açarlar

import Foundation

let raw = " Swift "
let keyA = raw.lowercased()
let keyB = raw.trimmingCharacters(in: .whitespacesAndNewlines).lowercased()

print(keyA == keyB) // false

Bəli, bunlar iki fərqli açardır. Və əgər siz haradasa trimmingCharacters(in:)-i unutmusunuzsa, indeksiniz iki paralel kainata “dağılacaq”.

Eyni şey, amma artıq lüğət xətası kimi

import Foundation

var counts: [String: Int] = [:]

let raw = " Swift "
let storedKey = raw.trimmingCharacters(in: .whitespacesAndNewlines).lowercased()
let lookupKey = raw.lowercased()

counts[storedKey, default: 0] += 1
print(counts[lookupKey, default: 0]) // 0

Diqqət edin: dict[key, default:] məhz tezlik xəritələri və yığma üçün istifadə etdiyimiz alətdir. Amma siz hansı açardan istifadə etdiyinizdə “üzürsünüzsə”, bu sizi xilas etməyəcək.

Bizim tədris “kitabxana üzrə axtarış”ımızdan mini parça

“Kitablar”ı hələlik çox sadə təsəvvür edəcəyik: id (ədəd) və title (sətir) var. Öz tiplərimizsiz, tamamilə artıq bildiklərinizlə.

import Foundation

func normalizeToken(_ s: String) -> String {
    s.trimmingCharacters(in: .whitespacesAndNewlines).lowercased()
}

let token1 = normalizeToken("Swift")
let token2 = normalizeToken("  swift ")

print(token1 == token2) // true

Fikir sadədir: normallaşdırma qaydası bir olmalı və hər yerdə tətbiq edilməlidir: həm indeks qurarkən, həm də axtarış edərkən.

5. Açarın sabitliyi: niyə Set-də sıraya güvənmək olmaz

“Deyirlər açar sabit olmalıdır” deyiləndə, yeni başlayan çox vaxt bunu mistik bir şey kimi təsəvvür edir, sanki “açarları narahat etməyin, yoxsa qaçıb gedərlər”. Praktikada məna daha sadədir: əgər sonra qoyduğunuz şeyi tapmaq istəyirsinizsə, siz yenə tam eyni açarı ala bilməlisiniz.

Bəzən qeyri-sabitlik açarın “başqa cür” hesablanmasına görə yaranır (məsələn, normallaşdırma unudulub). Bəzən isə siz açarı garantili sırası olmayan bir strukturdan qurursunuz. Bu artıq “dünən işləyirdi, bu gün yox” kimi görünən xətaya bənzəyir.

Tələ: anaqram üçün açarı Set vasitəsilə qururuq

Siz artıq anaqramlar üçün “kanonik açar” ideyasını görmüsünüz — adətən bu, sıralanmış hərflərdir: "tea" → "aet", "eat" → "aet". Bu sabitdir.

Amma qeyri-sabit yanaşma belədir: “Set vasitəsilə unikal hərfləri götürək və yenidən sətirə çevirək”. Problem ondadır ki, Set-in gəzilmə sırası müqavilə kimi güvənilməli bir şey deyil. (Qısası: Set unikallıq üçündür, sıra üçün yox.) Bu, birbaşa hash-kolleksiyaların təbiəti ilə bağlıdır.

Nümunə (amma məntiq pisdir):

let word = "spoon"

let unstableKey = String(Set(word)) // symbols order is not guaranteed
print(unstableKey)                  // for example, "onps" (or differently)

Bunu bir neçə dəfə müxtəlif mühitlərdə işə salsanız, fərqli sətirlər ala bilərsiniz. Deməli, sabit şəkildə qruplaşdıra bilməyəcəksiniz.

Anaqramlar üçün sabit açar: sıralama

let word = "spoon"

let stableKey = String(word.sorted())
print(stableKey) // "noopps"

Bu deterministdir: eyni giriş → eyni açar. Məhz Dictionary(grouping:by:), indekslər və qruplaşdırmalar üçün lazım olan şey budur. (Yeri gəlmişkən, Dictionary(grouping:by:) ilə qruplaşdırma elə bu cür tapşırıqları daha asan yazmaq üçün yaranmış standart, rahat alətdir.)

6. Qeyri-açıq görünən açar dəyərləri: NaN, -0.0 və tuple etiketləri

Bəzən “qəribəliklər” sizin Hashable reallaşdırmanızdan yox, dəyərin özünün bərabərlik və hashing-də necə davrandığından yaranır. Aşağıda əvvəlcədən bilməyə dəyən üç hal var ki, sonra Set ilə canlı varlıq kimi mübahisə etməyəsiniz.

Double.nan: əlavə etdiyiniz, amma sonra “tapılmayan” element

Double (ümumiyyətlə üzən nöqtəli ədədlər) IEEE 754-ə uyğundur. Və bu modeldə NaN (Not a Number) mövcuddur. Onun ən vacib xüsusiyyəti: NaN özünə bərabər deyil.

Yəni:

Double.nan == Double.nan // false

Burada əyləncə başlayır, çünki Set və Dictionary Hashable-a, Hashable isə bərabərliyə istinad edir. Əgər bərabərlik “biz bərabər deyilik” deyirsə, data strukturu buna inanmağa məcburdur.

Set və NaN: “qoydum, amma contains false deyir”

let nan = Double.nan
var s: Set<Double> = [nan]

print(nan == nan)        // false
print(s.contains(nan))   // false (yes, that's true)

Bu, Set xətası kimi görünür, amma əslində bu, == müqaviləsidir: əgər element “heç vaxt özünə bərabər deyil”, onda contains “eyni elementi” tapdığını təsdiq edə bilməz.

NaN-i Set-ə iki dəfə “əlavə etmək” olar

var s: Set<Double> = []
s.insert(Double.nan)
s.insert(Double.nan)

print(s.count) // often 2

Çünki Set üçün bunlar iki fərqli elementdir: o, “bərabər” olanı yoxlayır — bərabər yoxdur.

Dictionary və NaN: yazı var, oxu yoxdur

var dict: [Double: String] = [:]
dict[Double.nan] = "mystery"

print(dict[Double.nan] as Any) // nil

Praktik nəticə çox sadədir: NaN-i açar kimi istifadə etməyin və “tapıldı/tapılmadı” semantikasına ehtiyacınız varsa, NaN-i Set-də saxlamayın. Əgər sizin tapşırığınızda NaN mümkünürsə, daxil etmə/axtarışdan əvvəl adətən isNaN yoxlanışı edilir və ayrıca emal olunur.

0.0 və -0.0: daxildə fərqli, amma == ilə bərabər

Double üçün 0.0 == -0.0 doğrudur. Buna görə Dictionary-də bu, eyni açar olacaq və təyinat dəyəri yeniləyəcək.

var dict: [Double: String] = [0.0: "zero"]
dict[-0.0] = "minus zero?"

print(dict.count)     // 1
print(dict[0.0]!)     // minus zero?

Bu xəta deyil. Sadəcə yadda saxlayın: bəzən dəyərlərin “fərqli” təqdimatları (daxili olaraq) məntiqi baxımdan bərabər sayılır və Dictionary məntiqi bərabərliyi izləməlidir.

Tuple etiketləri Hashable-da iştirak etmir

Tuple-ları artıq bilirsiniz. Və budur nüans: Hashable-da iştirak edən tuple-lar üçün etiketlər (x:/y:) “bərabərlik”/“hash” hissəsinin bir parçası sayılmır — yalnız mövqelərə görə dəyərlər vacibdir. Etiketlər oxunaqlılığı artırır, amma müqayisə/hashing semantikasını dəyişmir.

var grid: [(x: Int, y: Int): String] = [:]
grid[(x: 1, y: 2)] = "Hero"

print(grid[(1, 2)] as Any) // Optional("Hero")

Bu faydalı ola bilər (daha az “səs-küylü” çevirmələr), amma bəzən çaşdırır: siz “yazılış formaları” fərqli olanda açarların da fərqli olacağını gözləyirsiniz, amma onlar eyni açar çıxır.

7. “Sınmış” hashing-i necə debug etmək olar

Dictionary/Set qəribə davrananda, çoxları kompilyatordan, ay fazasından və Merkurinin geriyə hərəkətindən şübhələnməyə başlayır. Amma çox vaxt səbəb daha sadədir və onu simptomlara görə diaqnostika etmək olar.

Aşağıdakılar “bürokratiya tipli checklist” deyil, məhz düşüncə modelidir. Əvvəlcə özünüzə sual verirsiniz: “Bu data problemidir, yoxsa struktur problemidir?”

Əgər dict[key] birdən-birə nil olursa, halbuki “dəqiq olmalı idi”, ilk etməli olduğunuz şey — qoyduğunuz açarın və axtardığınız açarın özünü çıxarmaq və onları sətir kimi (və ya ədəd kimi) müqayisə etməkdir. Çox vaxt boşluq, fərqli registr və ya fərqli format görəcəksiniz. Sətirlər üçün bu, demək olar ki, həmişə normallaşdırma məsələsidir və yuxarıdakı bölmədəki kanonik açarla həll olunur.

Əgər Set.contains(x) false qaytarırsa, amma siz “bir az əvvəl x-i əlavə etmişdim” deyirsinizsə, bu, çox vaxt x-in bərabərlikdə “qeyri-standart” davranması deməkdir. Ən parlaq nümunə — Double.nan. Burada birbaşa x == x çap etmək faydalıdır. Əgər false-dursa, contains-in niyə işləmədiyi dərhal aydın olur.

Əgər sizdə “bəzən işləyir, bəzən yox” halı varsa (xüsusilə qruplaşdırmada), düşünün ki, açarı elə bir şeydən qurursunuzmu ki, onda sabit sıra yoxdur: Set, “lüğəti sətirə çevirib birləşdirmək”, müxtəlif ardıcıllıqla toplamaq. Qruplaşdırmalar və indekslər deterministik olmalıdır: eyni giriş → eyni açar.

Küçük bir “simptom → çox rast gəlinən səbəb” cədvəli:

8. Tipik səhvlər

Səhv №1: “Sözlər məna baxımından eynidirsə, deməli açar da eynidir”.
Reallıqda Dictionary üçün açarlar konkret dəyərlərdir. "Swift" və "swift" — fərqli sətirlərdir. " Swift " və "Swift" də fərqli sətirlərdir. Əgər bir dəfə açarı normallaşdırıb, başqa dəfə unutsanız, “yarı-boş” görünən lüğət alacaqsınız. Müalicə sehrlə deyil, intizamla olur: bir normallaşdırma funksiyası, həmişə onun istifadəsi.

Səhv №2: kanonik açarı Set ilə düzəltməyə çalışıb sonra yenidən String-ə çevirmək.
Set unikallıq və membership yoxlamaları üçün yaradılıb, “gözəl, sabit təqdimat” üçün yox. String(Set(word)) etdikdə, sırası dəyişə bilən sətir alırsınız və qruplaşdırma dağılmağa başlayır. Sətirlərin kanonizasiyası üçün demək olar ki, həmişə sıralama (sorted()) lazımdır, çünki o deterministikdir.

Səhv №3: NaN-i düşünmədən Set/Dictionary-də Double istifadə etmək.
Adi ədədlər gözlənilən kimi davranır və məhz buna görə NaN xüsusilə hiyləgərdir: o, özünə bərabər deyil və data strukturu bu müqaviləyə səmimi şəkildə əməl edir. Nəticədə siz “əlavə et və tapa bilmə”. Əgər verilənlərdə NaN ola bilərsə, onu ya girişdə qadağan etmək, ya da ayrıca emal etmək lazımdır (məsələn, “NaN olmuşdu” adlı xüsusi bayraq saxlamaq).

Səhv №4: tuple etiketlərinin açarı “başqa” etdiyini gözləmək.
Swift-də etiketlər oxunaqlılığı artırır, amma tuple-lar üçün Hashable-da iştirak etmir: (x: 1, y: 2) və (1, 2) açar məntiqi baxımından üst-üstə düşür. Əgər siz “fərqli açarlar” gözləyirdinizsə, dəyər yenidən yazılacaq və siz çox təəccüblənəcəksiniz.

Səhv №5: hashing-in “unikal barmaq izi” olduğuna inanmaq və deməli kolliziyalar olmur.
Kolliziyalar olur və bu normal sayılır: hash axtarışı tez daraltmaq üçündür, son qərar isə == ilə verilir. Buna görə “əgər hash-lər bərabərdirsə, deməli elementlər də bərabərdir” kimi məntiq qurmağa çalışmayın. Bu, doğru deyil və belə optimizasiya düzgün proqramı tapmacalar generatoruna çevirir.