Что такое хэш-таблица, хэш, хэш-функция, хэширование?

Хэш-таблица — структура данных, которая хранит элементы в массиве по индексам, вычисленным из ключей с помощью хэш-функции. Она обеспечивает быстрый доступ к данным в среднем за O(1).

---

1. Хэш (hash)

Числовое значение фиксированной длины, получаемое из объекта (например, строки, числа) с помощью хэш-функции. В Python:

hash("abc")  # -> например, 123456789

---

2. Хэш-функция (hash function)

Алгоритм, который преобразует объект в хэш. Требования:

• Быстро вычисляется.

• Для одинаковых данных даёт одинаковый результат.

• Разные данные желательно дают разные хэши (минимум коллизий).

---

3. Хэширование (hashing)

Процесс получения хэша из объекта и использования его для быстрого поиска или вставки в структуру данных.

---

4. Как работает хэш-таблица

1. Ключ → хэш-функция → хэш.

2. Хэш модулем размера массива → индекс.

3. Элемент записывается в соответствующую ячейку.

4. При коллизии (один индекс для разных ключей) используется, например, открытая адресация или цепочки.

---

Пример использования хэша в хэш-таблице:

# Пример использования хэша в хэш-таблице
hash_table = [None] * 10  # Инициализация хэш-таблицы

def hash_function(value):
    return hash(value) % 10  # Пример простой хэш-функции

def insert_into_hash_table(value):
    index = hash_function(value)
    if hash_table[index] is None:
        hash_table[index] = [value]
    else:
        hash_table[index].append(value)

# Вставка значений в хэш-таблицу
insert_into_hash_table("apple")
insert_into_hash_table("banana")
insert_into_hash_table("orange")

# Получение значения из хэш-таблицы
def search_in_hash_table(value):
    index = hash_function(value)
    if hash_table[index] is not None and value in hash_table[index]:
        return f"{value} found in hash table"
    else:
        return f"{value} not found in hash table"

print(search_in_hash_table("apple"))  # Выведет: apple found in hash table
print(search_in_hash_table("grape"))  # Выведет: grape not found in hash table

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