Zəncirləmə (separate chaining) üsulunda heş cədvəlinin hər xanası (səbət, bucket) bir siyahıdır. Eyni səbətə düşən bütün açarlar bu siyahıda saxlanılır. Beləliklə toqquşma problem deyil: sadəcə zəncir uzanır. Heş funksiyaları əvvəlki mövzudan tanışdır.

Massiv və zəncirlər: açarlar 1, 5, 9 eyni səbətə düşür
Massiv və zəncirlər: açarlar 1, 5, 9 eyni səbətə düşür

Əməliyyatlar

  • Əlavə (put): səbət nömrəsi hash(key) % m. Zəncirdə açar varsa, qiyməti yenilə, yoxdursa, sona əlavə et.
  • Axtarış (get): eyni səbəti tap və zənciri keç, == ilə müqayisə et.
  • Silmə (remove): zəncirdən elementi çıxar.

Müqayisə == ilə aparılır, ona görə açarların __eq__/__hash__ müqaviləsi vacibdir.

Reallaşdırma

python
class HashMap:
    def __init__(self, capacity=8):
        self._buckets = [[] for _ in range(capacity)]
        self._size = 0

    def _bucket(self, key):
        return self._buckets[hash(key) % len(self._buckets)]