• Идея: выбрать алгоритм (probing), по которому будет выбираться следующая ячейка, если произошла коллизия
• Искать записи при помощи того же алгоритма
• Раширять таблицу, когда она заполнится достаточно сильно (load factor) </font>

Сложности¶

• Выбор хэш-функции, пробинга
• Образование кластеров
• Операция удаления

Виды пробинга¶

Есть несколько основных видов пробинга, от сосвсем простых до более сложных. Это, например,

• Линейный пробинг
• Квадратичный пробинг
• Двойное хэширование

Они различаются количеством вариантов обхода при поиске и "равномерностью" распределения данных по массиву.

Для того, чтобы понять, как работают таблицы, мы рассмотрим линейный пробинг, а потом перейдем к другим видам пробинга и сравним их.

Линейный пробинг

• $hash(k, i) = (hash'(k) + i)\mod M$
• $hash'(k, i)$ - вспомогательная хэш-функция (например, остаток от деления)
• Неравномерно, склонно к образованию кластеров
• Чем больше кластер, тем быстрее он растет: $(s + 1)/M$, где $s$ - размер кластера

На иллюстрации используется хеш-таблица с разщмером $M=12$

• желтые квадраты - "сдвинутые" ключи
• зеленые - ключи на "своих" местах
• $i = 1$

На иллюстрации ошибка: на самом деле, вероятность увеличения кластеров = 1/3, 5/12, 1/6!

Псевдокод операций¶

• Вставка: `OpenAddressInsert(Table, key, value)` - O(1) в среднем, O(n) в худшем
• Поиск: `OpenAddressSearch(Table, key)` - O(1) в среднем, O(n) в худшем
• Удаление: `OpenAddressDelete(Table, key)` - O(1) в среднем, O(n) в худшем
• Псевдокод операций (шаг $i = 1$):

1  M - размер таблицы
2  hash: key → index ∈ {0..M-1}
3
4
5  OpenAddressInsert(Table, key, value)
6      i = 0
7      repeat
8          j = hash(key, i)
9          if Table[j] == NIL
10             return j
11         else:
12             i = i + 1
13     until i == m
14     return "overflow"

15
16
17 OpenAddressSearch(Table, key)
18     i = 0
19     repeat
20         j = hash(key, i)
21         if Table[j] == key
22             return j
23         i = i + 1
24     until T[j] == NIL or i == m
25     return NIL

</pre></font>
Удаление?


Создавать дополнительный массив - "данные удалены" (замедляет поиск, "портит" _load factor_)
Пропускаем ячеки с другим хэшем; значение с первым совпадающим ключом копируем в текущую ячейку; удаляем его. Однако на практике такой подход не используется из-за его высокой сложности и не слишком высокой эффективнсоти. Кроме того, он плозо работает со сложными схемами пробинга.

</font>
Разбор удаления при открытой адресации¶



Удаление с Sentinel'ом / Tombstone'ом
1  M - размер таблицы
2  hash: key → index ∈ {0..M-1}
3
4
5  OpenAddressInsert(Table, key, value)
6      i = 0
7      repeat
8          j = hash(key, i)
9          if Table[j] == NIL or Table[j] == DELETED:
10             return j
11         else:
12             i = i + 1
13     until i == m
14     return "overflow"            
15
16
17 OpenAddressSearch(Table, key)
18     i = 0
19     repeat
20         j = hash(key, i)
21         if Table[j] == key
22             return j
23         i = i + 1
24     until T[j] == NIL or i == m
25     return NIL
26
27
28 OpenAddressDeleted(Table, key)
29     i = 0
30     repeat
31         j = hash(key, i)
32         if Table[j] == DELETED
33             return j
34         i = i + 1
35     until T[j] == NIL or i == m
36     return NIL
"Ленивое" удаление

Во время поиска элемента запомнить первый индекс, где попалось DELETED (если такой встретился)
Поменять первый найденный DELETED с найденным элементом местами - это в будущем ускорит поиск
Я не очень понимаю, почему такая схема называется "ленивой", с ленивыми вычислениями тут мало общего

Используется практически та же таблица, что и на прошлых изображениях. Красные квадраты - удаленные данные.

Примеры использования открытой адресации
Рассмотрим удаление на примере практической реализации общего назначнения - dictobject.c языка Python.
Sentinel для удаленных значений - DKIX_DUMMY:
Dummy.  index == DKIX_DUMMY  (combined only)
   Previously held an active (key, value) pair, but that was deleted and an
   active pair has not yet overwritten the slot.  Dummy can transition to
   Active upon key insertion.  Dummy slots cannot be made Unused again
   else the probe sequence in case of collision would have no way to know
   they were once active.
Код метода dict_popitem (dict.pop(key)), который удаляет и возвращает элемент по ключу:
0  static PyObject *
1  dict_popitem(PyDictObject *mp, PyObject *Py_UNUSED(ignored))
2  {
3      Py_ssize_t i, j;
4      PyDictKeyEntry *ep0, *ep;
5      PyObject *res;
6
7      res = PyTuple_New(2);
8      if (res == NULL)
9          return NULL;
10     if (mp->ma_used == 0) {
11        Py_DECREF(res);
12        PyErr_SetString(PyExc_KeyError,
13                        "popitem(): dictionary is empty");
14        return NULL;
15    }
16    /* Convert split table to combined table */
17    if (mp->ma_keys->dk_lookup == lookdict_split) {
18        if (dictresize(mp, DK_SIZE(mp->ma_keys))) {
19            Py_DECREF(res);
20            return NULL;
21        }
22    }
23    ENSURE_ALLOWS_DELETIONS(mp);
24
25    /* Pop last item */
26    ep0 = DK_ENTRIES(mp->ma_keys);
27    i = mp->ma_keys->dk_nentries - 1;
28    while (i >= 0 && ep0[i].me_value == NULL) {
29        i--;
30    }
31    assert(i >= 0);
32
33    ep = &ep0[i];
34    j = lookdict_index(mp->ma_keys, ep->me_hash, i);
35    assert(j >= 0);
36    assert(dictkeys_get_index(mp->ma_keys, j) == i);
37    dictkeys_set_index(mp->ma_keys, j, DKIX_DUMMY);
38
39    PyTuple_SET_ITEM(res, 0, ep->me_key);
40    PyTuple_SET_ITEM(res, 1, ep->me_value);
41    ep->me_key = NULL;
42    ep->me_value = NULL;
43    /* We can't dk_usable++ since there is DKIX_DUMMY in indices */
44    mp->ma_keys->dk_nentries = i;
45    mp->ma_used--;
46    mp->ma_version_tag = DICT_NEXT_VERSION();
47    assert(_PyDict_CheckConsistency(mp));
48    return res;
49 }
А вот так выглядит Search:
1  static Py_ssize_t
2  lookdict_index(PyDictKeysObject *k, Py_hash_t hash, Py_ssize_t index)
3  {
4      size_t mask = DK_MASK(k);
5      size_t perturb = (size_t)hash;
6      size_t i = (size_t)hash & mask;
7  
8      for (;;) {
9          Py_ssize_t ix = dictkeys_get_index(k, i);
10         if (ix == index) {
11             return i;
12         }
13         if (ix == DKIX_EMPTY) {
14             return DKIX_EMPTY;
15         }
16         perturb >>= PERTURB_SHIFT;
17         i = mask & (i*5 + perturb + 1);
18     }
19     Py_UNREACHABLE();
20 }
В принципе, ничего особенного, кроме схемы сдвига, зедсь нет - это практически псевдокод, переведенный на C.
в начало
</font>