Heş funksiyası istənilən açarı (sətir, tuple, say) sabit ölçülü tam ədədə çevirir. Heş cədvəli bu ədəddən massivdə yer seçmək üçün istifadə edir: index = h(key) % m, burada m — massivin ölçüsü. Heş funksiyası nə qədər yaxşıdırsa, açarlar bir o qədər bərabər paylanır və axtarış O(1)-ə yaxın olur.

Açar heş funksiyasından keçir və `% 8` ilə massivdə yer seçir
Açar heş funksiyasından keçir və % 8 ilə massivdə yer seçir

Yaxşı heş funksiyasının xassələri

  • Deterministik: eyni açar həmişə (bir proses daxilində) eyni heş verir.
  • Uyğunluq: a == b isə hash(a) == hash(b) olmalıdır (tərsi doğru deyil: heşlər üst-üstə düşə bilər).
  • Bərabər paylanma: nəticələr 0..m-1 aralığına mümkün qədər eyni sıxlıqla düşməlidir.
  • Sürətli: açarın ölçüsünə nisbətən xətti vaxt.
  • Qəfil dəyişkənlik: açarın bir simvolu dəyişəndə heş çox dəyişməlidir.

Sətir heşi: toplamaq pisdir, polinom yaxşıdır

Simvol kodlarını sadəcə toplamaq (sum_hash) anaqramları eyni heşə salır. Polinom heş isə mövqeyi də nəzərə alır: h = s[0]*p^(n-1) + ... + s[n-1] (mod m). Horner sxemi ilə hesablama O(n) çəkir: h = h * p + ord(ch).

python
def sum_hash(s):
    return sum(ord(ch) for ch in s)

def poly_hash(s, p=31, m=2**32):
    h = 0
    for ch in s:
        h = (h * p + ord(ch)) % m
    return h

for w in ["listen", "silent", "enlist", "banana"]:
    print(w, sum_hash(w), poly_hash(w))
text
listen 655 3192458695
silent 655 3392640085
enlist 655 2996453575
banana 609 2898612069