Министерство Образования и Исследований

Республики Молдова
Технический Университет Молдовs

Отчет
по лабораторной работе Nr.4.
Analiza şi proiectarea algoritmilor
Тема: Хеш-таблицы

Вариант 23

Выполнил ст.гр. TI-2210 Шологан Артемиос

Проверил ассист.универ. Скороходова Т.А.

Кишинев – 2023

Цель:Изучить работу алгоритмов: прямой адресации, хеш-таблицы и

открытой адресации. Реализовать перечисленные выше алгоритмы и
провести их сравнительный анализ.
Вариант:

Содержание отчета
1. Привести все используемые алгоритмы в псевдокодах. Здесь
необходимо указать использованные хэш-функции HASH(k), а также
процедуры добавления элементов HASH-INSERT(k).
2. Продемонстрировать работу алгоритмов на примере (см. раздел
«задание к лабораторной работе»).

Прямая адресация:

DIRECT-ADDRESS-SEARCH (T,k)
return T[k]
DIRECT-ADDRESS-INSERT (T,k)
T[k] = k
DIRECT-ADDRESS-DELETE (T,k)
T[k] = NULL

Хеш-таблицы:

CHAINED-HASH-INSERT (T,k)
добавить k в голову списка T[h[k]]
CHAINED-HASH-SEARCH (T,k)
найти k в списке T[h[k]]
CHAINED-HASH-DELETE (T,k)
удалить k из списка T[h[k]]

h(k)
return k mod m
 Открытая адресация:

HASH-INSERT (T,K)
i=0
repeat j=h(k,i)
if T[ j]=NULL
then T[ j]=k
return j
else i=i+1
until i=m
Error “Хеш-таблица переполнена”

HASH-SEARCH (T,k)
i=0
repeat j=h(k,i)
if T[ j]=k
then return j;
i=i+1
until T[ j]=NULL or i=m
return NULL

h(k,i)
return (k mod m + 1) mod m

HASH-DELETE (T,k)
i=0
repeat j=h(k,i)
if T[ j]=k
then T[ j]=NULL
i=i+1
until T[ j]=NULL or i=m
Error “Элемент уже удален”
2. Продемонстрировать работу алгоритмов для массива ключей.

Ключи 50,49,48,47,46

Для
ℎ(46)=⌊20((46⋅0.61803)mod 1)⌋
h(46)=⌊20((46⋅0.61803)mod1)⌋
ℎ(46)=⌊20(28.42938mod 1)⌋
h(46)=⌊20(28.42938mod1)⌋
ℎ(46)=⌊20⋅0.42938⌋
h(46)=⌊20⋅0.42938⌋
ℎ(46)=⌊8.5876⌋
h(46)=⌊8.5876⌋
ℎ(46)=8

Для
ℎ(47)=⌊20((47⋅0.61803)mod 1)⌋
h(47)=⌊20((29,04741)mod1)⌋
ℎ(47)=⌊20⋅((0,04741))⌋
h(47)=0

CHAINED-HASH-INSERT (T,46)
добавить 46 в голову списка T[h[46]]
CHAINED-HASH-INSERT (T,45)
добавить 47 в голову списка T[h[47]]
CHAINED-HASH-INSERT (T,48)
добавить 48 в голову списка T[h[48]]
CHAINED-HASH-INSERT (T,49)
добавить 49 в голову списка T[h[49]]
CHAINED-HASH-INSERT (T,50)
добавить 50 в голову списка T[h[50]]

0 … 5 … 8 … 13 … 18
47 Null 49 Null 46 Null 48 Null 50

CHAINED-HASH-DELETE (T,46)
удалить 46 из списка T[h[46]]
CHAINED-HASH-DELETE (T,47)
удалить 47 из списка T[h[47]]

0 … 5 … 8 … 13 … 18
Null Null 49 Null Null Null 48 Null 50

Прямая адресация:

DIRECT-ADDRESS-INSERT (T,50)
 T[50]=50
DIRECT-ADDRESS-INSERT (T,49)
T[49]=49
DIRECT-ADDRESS-INSERT (T,48)
T[48]= 48
DIRECT-ADDRESS-INSERT (T,47)
T[47]= 47
DIRECT-ADDRESS-INSERT (T,46)
T[46]= 46
… 17 … 21 … 32 … 45 46 47 48 4
0 … 3 … 6 … 9 10
9
NIL … NIL … NIL … NIL … NIL 46 47 48 4
NIL … NIL … … NIL NIL
9

DIRECT-ADDRESS-DELETE (T,47)
return T[47]=NULL
DIRECT-ADDRESS-DELETE (T,49)
return T[49]=NULL
DIRECT-ADDRESS-DELETE (T,50)
return T[50]=NULL

0 … 3 … 6 … 9 10 … 17 … 21 … 32 … 45 46 47 48 49
… NIL … NIL NIL … NIL … NIL … NIL … NIL 46 NIL 48 NIL
NIL … NIL

Закрытая адресация(метод цепочек):

Массив :49, 8, 10, 19, 37, 54, 7, 5, 2

CHAINED-HASH-INSERT (T,49)
добавить 49 в голову списка T[h[49]]
CHAINED-HASH-INSERT (T,8)
добавить 8 в голову списка T[h[8]]
CHAINED-HASH-INSERT (T,10)
добавить 10 в голову списка T[h[10]]
CHAINED-HASH-INSERT (T,19)
добавить 19 в голову списка T[h[19]]
CHAINED-HASH-INSERT (T,37)
добавить 37 в голову списка T[h[37]]
CHAINED-HASH-INSERT (T,54)
Добавить 54 в голову списка T[h[54]]
CHAINED-HASH-INSERT (T,7)
добавить 7 в голову списка T[h[7]]
CHAINED-HASH-INSERT (T,5)
добавить 5 в голову списка T[h[5]]
CHAINED-HASH-INSERT (T,2)
добавить 2 в голову списка T[h[2]]

Ключ 49: h(49)=49mod9=4. Ключ 49 помещается на позицию 4.

Ключ 8: h(8)=8mod9=8. Ключ 8 помещается на позицию 8.
Ключ 10: h(10)=10mod9=1. Ключ 10 помещается на позицию 1.
Ключ 19:h(19)=19mod9=1. Так как позиция 1 уже занята ключом 10, ключ
19 добавляется в цепочку перед ключом 10.
Ключ 37: h(37)=37mod9=1. Так как позиция 1 уже занята ключами 10 и 19,
ключ 37 добавляется в цепочку перед ключом 19.
Ключ 54: h(54)=54mod9=0. Ключ 54 помещается на позицию 0.
Ключ 7: h(7)=7mod9=7. Ключ 7 помещается на позицию 7.
Ключ 5:h(5)=5mod9=5. Ключ 5 помещается на позицию 5.
Ключ 2: h(2)=2mod9=2. Ключ 2 помещается на позицию 2.

Таким образом, хеш-таблица должна выглядеть так:

Позиция 0: 54
Позиция 1: 37 -> 19 -> 10
Позиция 2: 2
Позиция 4: 49
Позиция 5: 5
Позиция 7: 7
Позиция 8: 8
 Открытая адресация:
Линейный метод:
m=11
h(k,i)=(h′(k)+i)mod m

HASH-INSERT (T,49)
HASH-INSERT (T,8)
HASH-INSERT (T,10)
HASH-INSERT (T,19)
HASH-INSERT (T,37)
HASH-INSERT (T,54)
HASH-INSERT (T,7)
HASH-INSERT (T,5)
HASH-INSERT (T,2)

Вставка ключа 49:

h′(49)=49mod11=5

Ключ 49 помещается в ячейку 5.

Вставка ключа 8:
h′(8)=8mod11=8

Ключ 8 помещается в ячейку 8.

Вставка ключа 10:

h′(10)=10mod11=10

Ключ 10 помещается в ячейку 10.

Вставка ключа 19:

h′(19)=19mod11=8
Ячейка 8 занята ключом 8, так что переходим к следующей ячейке.
h(19,0)=(h′(19)+1)mod 11=9 Вставляем потому что свободно

Ключ 19 помещается в ячейку 9 (следующая свободная после 8).

Вставка ключа 37:

h′(37)=37mod11=4

Ключ 37 помещается в ячейку 4.

Вставка ключа 54:
h′(54)=54mod11=10

Ячейка 10 занята ключом 10, так что переходим к следующей ячейке.

h(54,1)=(h′(54)+1)mod 11=0 Вставляем потому что свободно

Ключ 54 помещается в ячейку 0 (следующая свободная после 10).

Вставка ключа 7:
h′(7)=7mod11=7

Ключ 7 помещается в ячейку 7.

Вставка ключа 5:
h′(5)=5mod11=5

Ячейка 5 занята ключом 49, так что переходим к следующей ячейке.

h(5,1)=(h′(5)+1)mod 11=6 Вставляем потому что свободно

Ключ 5 помещается в ячейку 6 (следующая свободная после 5).

Вставка ключа 2: ℎ′(2)=2mod 11=2h′(2)=2mod11=2

Ключ 2 помещается в ячейку 2.

0 1 2 3 4 5 6 7 8 9 10
54 None 2 None 37 49 5 7 8 19 10
h′=k mod m
h(k,i)=h′+c1*i+c2*i^2
Квадратичная:
Вставка ключа 49:

h′(49)=49mod11=5
Проба 0:Ключ 49 помещается в ячейку 5.

Вставка ключа 8:

h′(8)=8mod11=8
Проба 0:Ключ 8 помещается в ячейку 8.

Вставка ключа 10:

h′(10)=10mod11=10
Ключ 10 помещается в ячейку 10.

Вставка ключа 19:

h′(19)=19mod11=8 (ячейка 8 занята ключом 8)

h(19,1)=(8+1+3⋅1)mod11=12mod11=1 (ячейка 1 свободна)

Ключ 19 помещается в ячейку 1.

Вставка ключа 37:

h′(37)=37mod11=4 (ячейка 4 свободна)

Ключ 37 помещается в ячейку 4.

Вставка ключа 54:

h′(54)=54mod11=10 (ячейка 10 занята ключом 10)

Начинаем пробирование:
h(54,1)=(10+1+3⋅1)mod11=14mod11=3 (ячейка 3 свободна)
Ключ 54 помещается в ячейку 3.

Вставка ключа 7:

h′(7)=7mod11=7 (ячейка 7 свободна)

Ключ 7 помещается в ячейку 7.

Вставка ключа 5:

h′(5)=5mod11=5 (ячейка 5 занята ключом 49)

Начинаем пробирование:
h(5,1)=(5+1+3⋅1)mod11=9 (ячейка 9 свободна)
Ключ 5 помещается в ячейку 9.

Вставка ключа 2:

Проба 0:h′(2)=2mod11=2 (ячейка 2 свободна)

Ключ 2 помещается в ячейку 2.

0 1 2 3 4 5 6 7 8 9 10
None 19 2 54 37 49 None 7 8 5 10
двойного хеширования
ℎ1 ( k ) =k mod m
ℎ ( k , i )=( ℎ 1 ( k )+ iℎ2 ( k ) ) mod m,
ℎ2 ( k ) =¿)
Массив :49, 8, 10, 19, 37, 54, 7, 5, 2
Ключ 49:
h1=49mod11=5
h2=1+(49mod10)=10
Попытка №0: (5+0⋅10)mod 11=5
T[5] пусто, поэтому вставляем 49 в T[5].

Ключ 8:
h1=8mod11=8
h2=1+(8mod10)=9
Попытка №0: (8+0⋅9)mod 11=8
T[8] пусто, поэтому вставляем 8 в T[8].

h1=10mod11=10
h2=1+(10mod10)=1
Попытка №0: (10+0⋅1)mod 11=10
T[10] пусто, поэтому вставляем 10 в T[10].

Ключ 19:
h1=19mod11=8
h2=1+(19mod10)=10
Попытка №0: (8+0⋅10)mod 11=8
T[10] занято.i=i+1.
Попытка №1: (8+1⋅10)mod 11=7
T[7] пусто, поэтому вставляем 19 в T[7].

Ключ 37:
h1=37mod11=4
h2=1+(37mod10)=8
Попытка №0: (4+0⋅8)mod 11=4
T[4] пусто, поэтому вставляем 37 в T[4].

Ключ 54
h1=54mod11=10
h2=1+(54mod10)=5
Попытка №0: (10+0⋅5)mod 11=10
T[10] занято .
Попытка №1: (10+1⋅5)mod 11=4(занято)
Попытка №2: (10+2⋅5)mod 11=9
T[9] пусто, поэтому вставляем 54 в T[9].

Ключ 7:
h1=7mod11=7
h2=1+(7mod10)=8
Попытка №0: (7+0⋅8)mod 11=7(занято)
Попытка №1: (7+1⋅8)mod 11=4(занято)
Попытка №2: (7+2⋅8)mod 11=1

T[1] пусто, поэтому вставляем 7 в T[1].

Ключ 5:
h1=5mod11=5
h2=1+(5mod10)=6
Попытка №0: (5+0⋅6)mod 11=1(занято)
Попытка №1: (5+1⋅6)mod 11=0

T[0] пусто, поэтому вставляем 5 в T[0].

Ключ 2:
h1=2mod11=2
h2=1+(2mod10)=3
Попытка №0: (2+0⋅3)mod 11=2

T[2] пусто, поэтому вставляем 2 в T[2].

0 1 2 3 4 5 6 7 8 9 10
5 7 2 Null 37 49 Null 19 8 54 10

Код программы :
# Хеш-функция методом деления
def hash_division(k, m):
return k % m

# Добавление элемента в хеш-таблицу с цепочками

def chained_hash_insert(table, k, m=9):
index = hash_division(k, m)
table[index].insert(0, k)
print(f"Элемент {k} добавлен на индекс {index}")

def chained_hash_delete(table, k, m=9):

index = hash_division(k, m)
chain = table[index]
if k in chain:
[Link](k)
print(f"Элемент {k} удален с индекса {index}")
return True
else:
print(f"Элемент {k} не найден для удаления")
return False
# Хеш-функция методом умножения
def hash_multiply(k, m=20, A=0.61803):
return int(m * ((k * A) % 1))
# Хеш-функция методом деления
def hash_division(k, m):
return k % m

# Линейное пробирование
def linear_probing(k, i, m):
return (hash_division(k, m) + i) % m

def direct_addressing_insert(table, k):

if 0 <= k < len(table):
table[k] = k
else:
raise Exception("Ключ вне допустимого диапазона")

def direct_addressing_delete(table, k):

if 0 <= k < len(table):
table[k] = None
else:
raise Exception("Ключ вне допустимого диапазона")

def direct_addressing_search(table, k):

if 0 <= k < len(table):
return table[k] is not None
else:
raise Exception("Ключ вне допустимого диапазона")

# Функции для хеш-таблицы методом умножения

def hash_multiply_insert(table, k, m=20, A=0.61803):
index = hash_multiply(k, m, A)
if table[index] is None:
table[index] = [k]
else:
if k not in table[index]:
table[index].append(k)

def hash_multiply_delete(table, k, m=20, A=0.61803):

index = hash_multiply(k, m, A)
if table[index] is not None and k in table[index]:
table[index].remove(k)
return True
return False

def hash_multiply_search(table, k, m=20, A=0.61803):

index = hash_multiply(k, m, A)
return table[index] is not None and k in table[index]

# Функция хеширования методом умножения

def hash_multiply(k, m=20, A=0.61803):
return int(m * ((k * A) % 1))
# Квадратичное пробирование
def quadratic_probing(k, i, m, c1=1, c2=3):
h1 = hash_division(k, m)
return (h1 + c1*i + c2*i*i) % m

# Двойное хеширование
def double_hashing(k,i,m):

h1 = hash_division(k, m)
h2 = 1 + (k % (m - 1))
h = (h1 + i*h2) % m
return h

# Прямая адресация
def direct_addressing(keys, max_key_value):
# Создаем таблицу с размером равным максимальному значению ключа
table = [None] * (max_key_value + 1)
for k in keys:
table[k] = k # Используем ключ как индекс
return table

# Создание хеш-таблицы с цепочками

def create_chained_hash_table(keys, m=9):
table = [[] for _ in range(m)]
for k in keys:
# Добавляем элемент в начало списка для соответствующей позиции
хеша
table[hash_division(k, m)].insert(0, k)
return table

# Добавление ключей в хеш-таблицу с открытой адресацией

def open_addressing(keys, m=11, method='linear'):
table = [None] * m
for k in keys:
i=0
while True:
if method == 'linear':
j = linear_probing(k, i, m)
elif method == 'quadratic':
j = quadratic_probing(k, i, m)
elif method == 'double':
j = double_hashing(k, i, m)
if table[ j] is None:
table[ j] = k
break
else:
i += 1
if i == m:
raise Exception("Хеш-таблица заполнена!")
return table
# Меню выбора
# Удаление элемента из хеш-таблицы с цепочками
def chained_hash_delete(table, k, m=9):
index = hash_division(k, m)
chain = table[index]
if k in chain:
[Link](k)
print(f"Элемент {k} удален с индекса {index}")
return True
else:
print(f"Элемент {k} не найден на индексе {index} для удаления")
return False

def chained_hash_search(table, k, m=9):

index = hash_division(k, m)
if k in table[index]:
print(f"Элемент {k} найден на индексе {index}")
return True
else:
print(f"Элемент {k} не найден на индексе {index}")
return False

# Поиск элемента в хеш-таблице с цепочками

def chained_hash_search(table, k, m=9):
index = hash_division(k, m)
if k in table[index]:
print(f"Элемент {k} найден на индексе {index}")
return True
else:
print(f"Элемент {k} не найден на индексе {index}")
return False

# Вставка элемента в хеш-таблицу с открытой адресацией

def open_addressing_insert(table, k, m=11, method='linear'):
i=0
while i < m:
if method == 'linear':
j = linear_probing(k, i, m)
elif method == 'quadratic':
j = quadratic_probing(k, i, m)
elif method == 'double':
j = double_hashing(k, i, m)
if table[ j] is None:
table[ j] = k
print(f"Элемент {k} добавлен на индекс {j}")
return True
else:
i += 1
 print(f"Невозможно добавить элемент {k}, таблица заполнена")
return False

def open_addressing_delete(table, k, m=11, method='linear'):

i=0
while i < m:
if method == 'linear':
j = linear_probing(k, i, m)
elif method == 'quadratic':
j = quadratic_probing(k, i, m)
elif method == 'double':
j = double_hashing(k, i, m)
if table[ j] == k:
table[ j] = None
print(f"Элемент {k} удален с индекса {j}")
return True
elif table[ j] is None:
print(f"Элемент {k} не найден для удаления")
return False
i += 1
print(f"Элемент {k} не найден для удаления")
return False
# Поиск элемента в хеш-таблице с открытой адресацией
def open_addressing_search(table, k, m=11, method='linear'):
i=0
while i < m:
if method == 'linear':
j = linear_probing(k, i, m)
elif method == 'quadratic':
j = quadratic_probing(k, i, m)
elif method == 'double':
j = double_hashing(k, i, m)
if table[ j] == k:
return True
elif table[ j] is None:
return False
i += 1
return False

def print_chained_hash_table(table):
print("Вывод хеш-таблицы с цепочками:")
for i, chain in enumerate(table):
if chain:
print(f"Индекс {i}: {chain}")
else:
print(f"Индекс {i}: Пусто")

def print_open_addressing_table(table):
print("Вывод хеш-таблицы с открытой адресацией:")
for i, element in enumerate(table):
 if element is not None:
print(f"Индекс {i}: {element}")
else:
print(f"Индекс {i}: Пусто")

def print_direct_addressing_table(table):
print("Вывод таблицы прямой адресации:")
for i, element in enumerate(table):
if element is not None:
print(f"Индекс {i}: {element}")
else:
print(f"Индекс {i}: Пусто")

# Создание хеш-таблицы с цепочками

def create_chained_hash_table(m=9):
return [[] for _ in range(m)]

# Создание хеш-таблицы с открытой адресацией

def create_open_addressing_table(m=11):
return [None] * m
MAX_KEY_VALUE = 100

def menu():
# Создаем все необходимые таблицы
chained_table = create_chained_hash_table()
open_table = create_open_addressing_table()
direct_table = [None] * (MAX_KEY_VALUE + 1)

while True:
print("\nВыберите операцию:")
print("1 - Операции с хеш-таблицей с цепочками")
print("2 - Операции с хеш-таблицей с открытой адресацией")
print("3 - Операции с таблицей прямой адресации")
print("4 - Выход")

operation_choice = input("Введите номер операции: ")

if operation_choice == '1':
# Операции с хеш-таблицей с цепочками
perform_chained_hash_operations(chained_table)
elif operation_choice == '2':
# Операции с хеш-таблицей с открытой адресацией
perform_open_addressing_operations(open_table)
elif operation_choice == '3':
# Операции с таблицей прямой адресации
perform_direct_addressing_operations(direct_table)
elif operation_choice == '4':
print("Выход из программы.")
break
else:
 print("Неправильный выбор операции. Попробуйте снова.")

def perform_chained_hash_operations(table):
print("\nВыберите действие с хеш-таблицей с цепочками:")
print("1 - Добавить элемент")
print("2 - Удалить элемент")
print("3 - Найти элемент")
print("4 - Вывод на экран")

action = input("Введите номер действия: ")

k = int(input("Введите ключ: "))

if action == '1':
chained_hash_insert(table, k)
elif action == '2':
if chained_hash_delete(table, k):
print(f"Элемент {k} удален.")
else:
print(f"Элемент {k} не найден.")
elif action == '3':
if chained_hash_search(table, k):
print(f"Элемент {k} найден.")
else:
print(f"Элемент {k} не найден.")
elif action == '4':
print_chained_hash_table(table)

def perform_open_addressing_operations(table):
print("\nВыберите метод хеширования для операций с открытой
адресацией:")
print("1 - Линейное пробирование")
print("2 - Квадратичное пробирование")
print("3 - Двойное хеширование")

method_choice = input("Метод хеширования (1/2/3): ")

method = 'linear' if method_choice == '1' else 'quadratic' if method_choice ==
'2' else 'double'

print("\nВыберите действие с хеш-таблицей с открытой адресацией:")

print("1 - Добавить элемент")
print("2 - Удалить элемент")
print("3 - Найти элемент")
print("4 - Вывод на экран")

action = input("Введите номер действия: ")

k = int(input("Введите ключ: "))

if action == '1':
if open_addressing_insert(table, k, method=method):
 print(f"Элемент {k} добавлен.")
else:
print(f"Невозможно добавить элемент {k}.")
elif action == '2':
if open_addressing_delete(table, k, method=method):
print(f"Элемент {k} удален.")
else:
print(f"Элемент {k} не найден.")
elif action == '3':
if open_addressing_search(table, k, method=method):
print(f"Элемент {k} найден.")
else:
print(f"Элемент {k} не найден.")
elif action == '4':
print_open_addressing_table(table)

def print_open_addressing_table(table):
print("Хеш-таблица с открытой адресацией:")
for i, element in enumerate(table):
print(f"Индекс {i}: {element if element is not None else 'Пусто'}")

def perform_direct_addressing_operations(table):
print("\nВыберите действие с таблицей прямой адресации:")
print("1 - Добавить элемент")
print("2 - Удалить элемент")
print("3 - Найти элемент")
print("4 - Вывод на экран")

action = input("Введите номер действия: ")

k = int(input(f"Введите ключ (0-{MAX_KEY_VALUE}): "))

if action == '1':
try:
direct_addressing_insert(table, k)
print(f"Элемент {k} добавлен.")
except Exception as e:
print(e)
elif action == '2':
try:
direct_addressing_delete(table, k)
print(f"Элемент {k} удален.")
except Exception as e:
print(e)
elif action == '3':
if direct_addressing_search(table, k):
print(f"Элемент {k} найден.")
else:
print(f"Элемент {k} не найден.")
elif action == '4':
 print_direct_addressing_table(table)

def print_direct_addressing_table(table):
print("Таблица прямой адресации:")
for i, element in enumerate(table):
print(f"Индекс {i}: {element if element is not None else 'Пусто'}")

def print_chained_hash_table(table):
print("Хеш-таблица с цепочками:")
for i, chain in enumerate(table):
print(f"Индекс {i}: {chain if chain else 'Пусто'}")

# Запуск обновленного меню

menu()

Каждый из методов хеширования и разрешения коллизий имеет свои

преимущества и недостатки. Подробно рассмотрим каждый из них:

В реальности, прямая адресация редко используется в чистом виде, так как

она неэффективна для больших множеств ключей, где ключи распределены
неравномерно. Вместо этого часто используются хеш-функции для
сокращения пространства ключей до размера хеш-таблицы.

Хеш-функция методом умножения

Эффективность: Хорошее распределение ключей, особенно когда размер
таблицы m - степень двойки.
Реализация: Проста в реализации, но требует вычисления с плавающей
точкой.
Хеш-функция методом деления
Эффективность: Может приводить к коллизиям, если m выбрано неудачно
(например, близко к степени двойки или к множителю ключей).
Реализация: Простейшая реализация, работает очень быстро на
целочисленной арифметике.
Линейное пробирование
Эффективность: Просто в реализации, но страдает от проблемы
кластеризации, что может сильно ухудшить производительность при высокой
заполненности таблицы.
Реализация: Простая, но при большом количестве коллизий эффективность
падает из-за увеличения числа проб.
Квадратичное пробирование
Эффективность: Уменьшает проблему кластеризации по сравнению с
линейным пробированием, но все равно может страдать от вторичной
кластеризации.
Реализация: Сложнее линейного пробирования из-за дополнительных
вычислений, но лучше разбрасывает ключи по таблице.
Двойное хеширование
Эффективность: Считается одним из лучших методов разрешения коллизий
из-за низкой вероятности кластеризации. Реализация: Более сложная
реализация, так как требует двух хеш-функций, но это позволяет
равномернее распределять ключи.
Хеш-таблица с цепочками
Эффективность: Хорошо справляется с коллизиями и позволяет таблице быть
заполненной более чем на 100%, но может потребовать дополнительной
памяти для ссылок/указателей.
Реализация: Требует дополнительной структуры данных (списки или связные
списки) для каждой позиции в хеш-таблице.
Сравнение между разными типами адресации
Квадратичное против двойного хеширования: Двойное хеширование
обеспечивает лучшее распределение ключей и избегает вторичной
кластеризации, что делает его предпочтительнее для больших таблиц.
Цепочки против открытой адресации: Цепочки лучше справляются с
большим количеством коллизий и позволяют таблице переполняться, тогда
как методы открытой адресации страдают, когда таблица заполнена более
чем на 70-80%.
В зависимости от конкретного применения и характеристик набора данных
один метод может быть предпочтительнее другого.