От какви компоненти се състои хеш таблицата?

Хеш таблицата се състои от две основни компоненти:

1. Масив (или списък) от клетки (кофи): Това е основната структура за съхранение. Всяка клетка може да съдържа един или повече елементи от данни (двойки ключ-стойност).

2. Хеш функция: Алгоритъм, който преобразува входния ключ в числов индекс, който се използва за определяне на клетката, където трябва да бъде съхранен или намерен съответният елемент от данни.

Освен това, за разрешаване на колизии (ситуации, когато различни ключове хешират в един и същи индекс), се използват механизми като:

• Метод на веригите: Във всяка клетка се съхранява списък (например свързан списък) от елементи, които са хеширани в този индекс.
• Метод на отвореното адресиране: При колизия алгоритъмът търси следващата свободна клетка, следвайки определена стратегия (линейно пробиране, квадратично пробиране, двойно хеширане).

# Пример за проста хеш функция
def simple_hash(ключ, размер_на_масива):
    # Преобразуване на ключа в число
    if isinstance(ключ, str):
        стойност_hash = sum(ord(символ) for символ in ключ)
    elif isinstance(ключ, int):
        стойност_hash = ключ
    else:
        raise TypeError("Несъвместим тип ключ")

    # Връщане на индекса в рамките на размера на масива
    return стойност_hash % размер_на_масива

# Пример за компонент на масива за метода на веригите
class HashTable:
    def __init__(self, размер):
        self.размер = размер
        self.array = [[] for _ in range(self.размер)] # Масив от списъци (вериги)

    def вмъкни(self, ключ, стойност):
        индекс = simple_hash(ключ, self.размер)
        self.array[индекс].append((ключ, стойност)) # Добавяне на двойка ключ-стойност към списъка

    def търси(self, ключ):
        индекс = simple_hash(ключ, self.размер)
        for k, v in self.array[индекс]:
            if k == ключ:
                return v
        return None # Ключът не е намерен