📦 Репозиторий занятия 32

Зачем нужен хэш: от линейного поиска к O(1)

less_17__hash__set/theory_01__Why_do_we_need_hash.md

Мотивационный конспект: почему множество вообще существует как структура данных. Разбор идёт от линейного поиска O(n) к бинарному O(log n) (требует сортировки), а от него — к мечте об поиске за O(1), которая реализуется через хеширование. Отдельно вводится различие обычной (обратимой) функции и односторонней функции — хэш-функция как раз односторонняя: посчитать легко, восстановить исходное значение по хэшу нельзя.

• Линейный поиск: `for x in arr: if x == 99` — O(n)
• Бинарный поиск по отсортированному списку — O(log n)
• Идея адресации: значение → индекс ячейки за O(1)
• Обратимая функция vs односторонняя функция (`one-way function`)
• Особенности хэш-таблицы: только неизменяемые типы, возможны коллизии
• `x.__hash__()` у строки даёт число, у списка — `None` (TypeError при вызове)

## 1. Алгоритмы поиска

Представим себе, что у нас есть список:

```python
arr = [42, 17, 8, 99, 23, 56]
```

и нам нужно проверить, есть ли там число `99`.

### 1. Линейный поиск (naive search)

Самый простой способ — пройтись по всем элементам:

```python
for x in arr:
    if x == 99:
        print("Нашли!")
```

Время: **O(n)** — чем больше данных, тем дольше.

---

### 2. Бинарный поиск

Если список отсортирован:

```python
arr = [8, 17, 23, 42, 56, 99]
```

то можно искать быстрее — <a href="https://en.wikipedia.org/wiki/Binary_search#/media/File:Binary-search-work.gif" target="_blank">**бинарным поиском**</a>.  
Суть: берём середину и отбрасываем половину данных на каждом шаге.

Время: **O(log n)** — быстро, но требует *упорядоченности*.

---

### Идея: а можно ли искать за O(1)?

То есть — мгновенно, без обходов и сортировок, вне зависимости от числа данных.
Да, если **мы сразу знаем, где лежит элемент**.
Например, как если бы у нас был словарь с адресами:

| Ключ | Адрес в памяти |
| ---- | -------------- |
| 42   | 0x001          |
| 17   | 0x002          |
| ...  | ...            |

Тогда поиск — это просто «сходить по адресу».
Вот ради этого и придумали **хеширование**.

---

## 2. Обычные и односторонние функции

Чтобы знать, *куда* класть объект, нужно вычислить **его адрес**.
Но мы не можем хранить адреса всех возможных значений (иначе теряет смысл сама идея мгновенного поиска).  
…

set: свойства, создание, методы — главный конспект урока

less_17__hash__set/theory_02__set.md

Центральный справочный файл про `set`: определение как неупорядоченной коллекции уникальных хэшируемых элементов, таблица свойств, три способа создания (фигурные скобки, `set()`, set comprehension) с оговоркой про пустые `{}` (создают `dict`). Далее — полные таблицы методов: добавление (`add`/`update`), удаление (`remove`/`discard`/`pop`/`clear`), операции над множествами (`intersection`/`union`/`difference`/`symmetric_difference`/`issuperset`/`issubset`/`isdisjoint`) с сопоставлением операторам (`&`, `|`, `-`, `^`, `>=`, `<=`), плюс `len()`, `in` и три способа глубокого копирования. Файл ссылается на все `.py`-примеры урока.

• Таблица свойств: изменяемость, хэшируемость элементов, отсутствие порядка, отсутствие дублей
• 3 способа создания: `{}`, `set()`, `{x**2 for x in range(5)}`
• Добавление: `add()` (один элемент) vs `update()` (несколько из iterable)
• Удаление: `remove()` (KeyError) vs `discard()` (без ошибки) vs `pop()`/`clear()`
• Операции над множествами и их операторные эквиваленты (& | - ^ >= <=)
• `len()`, `in`, три способа копирования (`copy()`, `set()`, comprehension)

**`set`** — это неупорядоченная коллекция уникальных хэшируемых элементов.  

Иными словами: 
* в `set` нельзя хранить повторяющиеся значения, 
* а порядок элементов не фиксирован.
* каждый элемент СТРОГО `hashable`.


---

## Свойства `set`

| Свойство | Описание                                          |
|---|---------------------------------------------------|
| Изменяемость | Можно добавлять и удалять элементы после создания |
| Хэшируемость | Каждый элемент `set` строго хэшируемый            |
| Порядок не сохраняется | Элементы НЕупорядочены                            |
| Не допускает дубликатов | Повторяющиеся элементы автоматически удаляются    |

---

## Основные способы создания `set`

* При создании сета из коллекции, каждый элемент этой коллекции должен быть хэшируемым!
* Дубликаты удалятся
* Пустые `{}` создают **словарь**, а не множество!

| Способ                        | Пример                                 | Результат         | Пояснение                                                                         |
|-------------------------------| -------------------------------------- | ----------------- |-----------------------------------------------------------------------------------|
| **1. Фигурные скобки `{}`**   | `set1 = {1, 2, 'a'}`                   | `{1, 2, 'a'}`     | Создаёт множество сразу с элементами. <br> Пустые `{}` → `dict`.                  |
| **2. Функция `set()`**        | `set([1, 2, 3])`                       | `{1, 2, 3}`       | Создаёт множество из итерируемого объекта. <br> Элементы должны быть хэшируемыми. |
| **2.1 Пустое множество**      | `set()`                                | `set()`           | Создаёт пустое множество.                                                         |
| **3. Set comprehension**      | `{x**2 for x in range(5)}`             | `{0,1,4,9,16}`    | Как list comprehension, <br> только возвращает не `list`, а `set`.                |


---

## Методы `set`.



### 1. Добавление элементов

| Метод      | Пример                   | Что делает                                                                              |
| ---------- | ------------------------ |-----------------------------------------------------------------------------------------|
| `add()`    | `s.add(5)`               | Добавляет один элемент `5` в множество. <br>Если элемент уже есть — ничего не меняется. |
| `update()` | `s.update([6,7], {8,9})` | Добавляет несколько элементов сразу  <br>из любого итерируемого объекта                 |

[Примеры](./theory_05_set_create.py)

---

### 2. Удаление элементов

| Метод       | Пример         | Отличие                                                                     |
| ----------- | -------------- | --------------------------------------------------------------------------- |
| `remove()`  | `s.remove(5)`  | Удаляет элемент `5`. Если элемента нет — **вызывает ошибку `KeyError`**.    |
| `discard()` | `s.discard(5)` | Удаляет элемент `5`. Если элемента нет — **ничего не делает** (без ошибки). |
| `pop()`     | `s.pop()`      | Удаляет и возвращает **любый элемент** множества (порядок случайный).       |
| `clear()`   | `s.clear()`    | Очищает множество, делает его пустым: `set()`.                              |
…

Пересечение, объединение, разность — методы и операторы

less_17__hash__set/theory_03_set_methods.py

Демонстрирует пять операций над двумя множествами `{1, 2, 3}` и `{2, 3, 4}`: пересечение, объединение, разность в обе стороны и симметричную разность. Каждый результат сразу сверяется через `==` с операторной формой (`&`, `|`, `-`, `^`), чтобы показать: метод и оператор дают идентичный результат — это два способа записи одного и того же.

• set1.intersection(set2) и set1 & set2 — пересечение
• set1.union(set2) и set1 | set2 — объединение
• set1.difference(set2) и set2.difference(set1) — разность в обе стороны
• set1.symmetric_difference(set2) и set1 ^ set2 — симметричная разность
• Пять сравнений метод == оператор — все True

Что выводит: {2, 3}, затем {1, 2, 3, 4}, {1}, {4}, {1, 4} — результаты пяти операций по порядку. Далее пять раз True: подтверждают, что вызов метода и операторная запись дают одинаковый результат.

set1 = {1, 2, 3}
set2 = {2, 3, 4}
intersection = set1.intersection(set2)
union = set1.union(set2)
difference1_2 = set1.difference(set2)
difference2_1 = set2.difference(set1)
symmetric_difference = set1.symmetric_difference(set2)
print(intersection)  # Выводит {2, 3}
print(union)  # Выводит {1, 2, 3, 4}
print(difference1_2)  # Выводит {1}
print(difference2_1)  # Выводит {4}
print(symmetric_difference)  # Выводит {1, 4}

print(set1.intersection(set2) == set1 & set2)  # True
print(set1.union(set2) == set1 | set2)    # True
print(set1.difference(set2) == set1 - set2)    # True
print(set2.difference(set1) == set2 - set1)    # True
print(set1.symmetric_difference(set2) == set1 ^ set2)    # True

issuperset, issubset, isdisjoint и сравнение set/list

less_17__hash__set/theory_04_set_methods.py

Показывает проверки отношений между множествами: `issuperset`/`issubset` (и их операторные эквиваленты `>=`/`<=`), `isdisjoint` (есть ли общие элементы), а также сравнение множеств на равенство `==`/`!=`. В конце — ключевая иллюстрация: `{1, 2, 3} == {3, 1, 2}` истинно (порядок не важен), а для списков `[1, 2, 3] == [3, 1, 2]` ложно (порядок важен) — наглядная разница между `set` и `list`.

• set1.issuperset(set2) и set2.issubset(set1) — проверка вложенности
• Сверка метод == оператор: `>=` и `<=`
• {1}.isdisjoint({1, 2, 3}) — False, {4}.isdisjoint({1, 2, 3}) — True
• set1 == set2 и set1 != set2 для непересекающихся по составу множеств
• {1, 2, 3} == {3, 1, 2} — True, порядок в set не важен
• [1, 2, 3] == [3, 1, 2] — False, порядок в list важен

Что выводит: True, True, True, True — issuperset/issubset и их операторные эквиваленты совпадают. Затем isdisjoint False и isdisjoint True. Далее False и True — set1 не равен set2, а значит не равен. Пустая строка, затем True — множества {1,2,3} и {3,1,2} равны. Пустая строка, затем False и True — списки [1,2,3] и [3,1,2] не равны, а [1,2,3] и [1,2,3] равны.

set1 = {1, 2, 3}
set2 = {2}
issuperset = set1.issuperset(set2)
issubset = set2.issubset(set1)
print(issuperset)
print(issubset)

print(set1.issuperset(set1) == (set1 >= set2))    # True
print(set2.issubset(set1) == (set2 <= set1))    # True

# У множеств нет ни одного общего элемента
print('isdisjoint', {1}.isdisjoint({1, 2, 3}))  # False
print('isdisjoint', {4}.isdisjoint({1, 2, 3}))  # True

set1 = {1, 2, 3}
set2 = {2}
issuperset = set1.issuperset(set2)
issubset = set2.issubset(set1)
print(issuperset)
print(issubset)

print(set1.issuperset(set1) == (set1 >= set2))    # True
print(set2.issubset(set1) == (set2 <= set1))    # True

# У множеств нет ни одного общего элемента
print('isdisjoint', {1}.isdisjoint({1, 2, 3}))  # False
print('isdisjoint', {4}.isdisjoint({1, 2, 3}))  # True


print(set1 == set2)   # False
print(set1 != set2)   # True
print()

# =============== set equality ===============
print({1, 2, 3} == {3, 1, 2})
print()

# =============== list equality ===============
print([1, 2, 3] == [3, 1, 2])
print([1, 2, 3] == [1, 2, 3])

Все способы создания set и типичные ошибки

less_17__hash__set/theory_05_set_create.py

Проходит по трём способам создания множества (фигурные скобки, `set()`, set comprehension) и специально провоцирует ошибки, чтобы показать требования к аргументу: он должен быть iterable, а каждый его элемент — хэшируемым. `set(1)` падает, потому что число не итерируемо; `set([[1], [2]])` и `{x for x in [[1], [2]]}` падают, потому что список внутри — нехэшируемый элемент. Отдельно показано, что пустые `{}` создают `dict`, а не `set`.

• `{1, 2, 'a'}` — фигурные скобки создают set
• `{}` — пустые фигурные скобки создают dict, а не set!
• `set(1)` → TypeError: 'int' object is not iterable
• `set([[1], [2]])` → TypeError: unhashable type: 'list'
• `set("abc")` → {'a', 'b', 'c'} — строка разбивается на символы
• `{x for x in [[1], [2]]}` → тот же TypeError в set comprehension

Что выводит: Блок 1: тип set1 — <class 'set'>, значение {1, 2, 'a'}; тип set2 (пустые {}) — <class 'dict'>, значение {}. Блок 2: сначала две пойманные ошибки (2.1 TypeError: 'int' object is not iterable, 2.2 TypeError: unhashable type: 'list'), затем набор результатов set() → set(), set("") → set(), set("a") → {'a'}, set([]) → set(), set(['']) → {''}, set(['a']) → {'a'}, set(['abc']) → {'abc'}, set("abc") → {'b', 'c', 'a'} (порядок символов не гарантирован). Блок 3: пойманная ошибка 3.2 TypeError: unhashable type: 'list', затем my_set = {1, 2, 'a'} из comprehension с дублями 1 и 2.

"""Методы (и способы) создания множества"""


print(""" 1. =============== curly braces {} =============== """)
set1 = {1, 2, 'a'}
print(type(set1))  # <class 'set'>
print(set1)        # {1, 2, 'a'}


print(""" Внимание!!! Пустые скобки создают тип данных dict, а не set!!! """)
set2 = {}
print(type(set2))  # <class 'dict'>
print(set2)        # {}

"""Методы (и способы) создания множества"""


print(""" 1. =============== curly braces {} =============== """)
set1 = {1, 2, 'a'}
print(type(set1))  # <class 'set'>
print(set1)        # {1, 2, 'a'}


print(""" Внимание!!! Пустые скобки создают тип данных dict, а не set!!! """)
set2 = {}
print(type(set2))  # <class 'dict'>
print(set2)        # {}


print(""" 2. =============== function set() ===============
IMPORTANT: 
    a.) Must have iterable object!!!
    b.) And every item must be hashable!!!!!
""")

try:
    set(1)
except Exception as e:
    print(f"2.1.{e.__class__.__name__}: {e}")

try:
    set([[1], [2]])
except Exception as e:
    print(f"2.2.{e.__class__.__name__}: {e}")


print(set())       # set()
print(set(""))     # set()
print(set("a"))    # {'a'}
print(set([]))     # set()
print(set(['']))   # {''}
print(set(['a']))  # {'a'}
print(set(['abc']))  # {'abc'}
print(set("abc"))  # {'a', 'b', 'c'}
print()


print(""" 3. =============== set comprehension ===============
IMPORTANT: 
    a.) Must have iterable object!!!
    b.) And every item must be hashable!!!!!
""")

try:
    my_set = {x for x in [[1], [2]]}
except Exception as e:
    print(f"3.2.{e.__class__.__name__}: {e}")

my_set = {x for x in [1, 2, 2, 1, 'a']}
print('\n3.3. my_set =', my_set)

Размер множества и проверка вхождения

less_17__hash__set/theory_06_set_methods.py

Минимальный файл на два вызова: `len()` для подсчёта количества элементов множества и оператор `in` для проверки, содержится ли значение в множестве. Демонстрация того, что `in` для `set` — операция поиска по хэшу, а не перебор.

• my_set = {1, 2, 3}
• len(my_set) — размер (мощность) множества
• 2 in my_set — проверка наличия элемента

Что выводит: 3 — размер множества из трёх элементов. True — элемент 2 действительно содержится в множестве.

"""Размер (мощность) множества и проверка наличия элемента в множества"""


my_set = {1, 2, 3}

""" 1. ===== size (размер) or cardinality (мощность) of a set - len() ===== """
print(len(my_set))  # Выводит размер множества


""" 2. ====================== in - поиск элемента  ====================== """
print(2 in my_set)  # Выводит True, так как элемент 2 содержится во множестве

Сравнение скорости поиска: list O(n) против set O(1)

less_17__hash__set/theory_07_set_vs_list__speed_comparison.py

Практическое измерение разницы в скорости: декоратор `timer` замеряет время выполнения функции через `time()` до и после вызова. Обе функции ищут одно и то же отсутствующее значение (`-1`) 20 000 раз подряд — один раз в списке из 20 000 строк, другой раз в множестве из тех же строк. Результат наглядно показывает, во сколько раз поиск в `set` быстрее поиска в `list` на большом объёме данных.

• @timer — декоратор, замеряющий время через `time()` до/после вызова
• find_item_in_list(value, lst, num) — 20 000 проверок `value in lst`
• find_item_in_set(value, sset, num) — 20 000 проверок `value in sset`
• lst = ['a' * n for n in range(20000)] — список неравных по длине строк
• value = -1 — заведомо отсутствующее значение (худший случай для list)

Что выводит: Поиск в списке занял около 48 секунд (полный перебор всех 20 000 элементов на каждой из 20 000 попыток, да ещё и сравнение с длинными строками). Поиск в множестве занял примерно 0.00 секунд — поиск по хэшу не зависит от размера коллекции. Конкретные секунды зависят от машины, но разница на порядки — стабильна.

"""Сравнение скорости поиска элементов в list и set"""

from time import time


def timer(func):
    def wrapper(*args, **kwargs):
        start = time()
        print(f"{50 * '='}\nStart func {func.__name__} ...")
        func(*args, **kwargs)
        end = time()
        print(f"Func {func.__name__} execution time: {end - start:.2f}")
    return wrapper

"""Сравнение скорости поиска элементов в list и set"""

from time import time


def timer(func):
    def wrapper(*args, **kwargs):
        start = time()
        print(f"{50 * '='}\nStart func {func.__name__} ...")
        func(*args, **kwargs)
        end = time()
        print(f"Func {func.__name__} execution time: {end - start:.2f}")
    return wrapper


@timer
def find_item_in_list(value, lst, num):
    for _ in range(num):
        if value in lst:
            pass


@timer
def find_item_in_set(value, sset, num):
    for _ in range(num):
        if value in sset:
            pass


value = -1
num = 20000
lst = ['a' * n for n in range(num)]    # ['a', 'aa', 'aaa', ...]
sset = set(lst)

find_item_in_list(value, lst, num)
find_item_in_set(value, sset, num)

Добавление элементов: add, update и объединение через | / union()

less_17__hash__set/theory_08_set_methods_add_items.py

Показывает разницу между `add()` (один элемент) и `update()` (сразу несколько элементов из любого iterable, включая строку — она разбивается на символы). Оба метода изменяют множество на месте и возвращают `None`. Во второй половине — два эквивалентных способа объединить два множества без изменения исходных: оператор `|` и метод `.union()`.

• my_set.add(4) — добавляет один элемент, возвращает None
• my_set.update([5, 6, 7]) — добавляет несколько элементов из списка
• my_set.update("abc") — строка при update() разбивается на символы 'a', 'b', 'c'
• set1 | set2 — объединение через оператор
• set1.union(set2) — объединение через метод, тот же результат

Что выводит: None (возврат add), {1, 2, 3, 4}; None (возврат update списком), {1, 2, 3, 4, 5, 6, 7}; None (возврат update строкой), {1, 2, 3, 4, 5, 6, 7, 'a', 'b', 'c'}; затем дважды {1, 2, 3, 4, 5} — результат `|` и `.union()` совпадает.

"""Методы множества"""


my_set = {1, 2, 3}

""" 1. ====================== add(value) ====================== """
print(my_set.add(4))    # None
print(my_set)           # {1, 2, 3, 4}


""" 2. ====================== update(iterable) ====================== """
print(my_set.update([5, 6, 7]))   # None
print(my_set)                     # {1, 2, 3, 4, 5, 6, 7}

"""Методы множества"""


my_set = {1, 2, 3}

""" 1. ====================== add(value) ====================== """
print(my_set.add(4))    # None
print(my_set)           # {1, 2, 3, 4}


""" 2. ====================== update(iterable) ====================== """
print(my_set.update([5, 6, 7]))   # None
print(my_set)                     # {1, 2, 3, 4, 5, 6, 7}

print(my_set.update("abc"))      # None
print(my_set)                    # {1, 2, 3, 4, 5, 6, 7, 'a', 'b', 'c'}


""" 3. ========= concatenation by | ======== """
set1 = {1, 2, 3}
set2 = {3, 4, 5}
print(set1 | set2)   # {1, 2, 3, 4, 5}


""" 4. ========= concatenation by .union() ======== """
set1 = {1, 2, 3}
set2 = {3, 4, 5}
print(set1.union(set2))    # {1, 2, 3, 4, 5}

Удаление элементов: remove, discard, pop, clear

less_17__hash__set/theory_09_set_methods_remove_items.py

Последовательно показывает четыре способа удаления из множества и их отличия в обработке отсутствующего элемента: `remove()` кидает `KeyError`, `discard()` — нет, `pop()` удаляет случайный элемент и не принимает аргументов (что тоже подсвечено ошибкой), `clear()` опустошает множество. Каждый вызов обёрнут так, чтобы показать и успешный, и ошибочный сценарий.

• my_set.remove(5) — удаляет, второй вызов на отсутствующем значении → KeyError
• my_set.discard(4) — удаляет; discard(100) на отсутствующем — без ошибки
• my_set.pop() — удаляет и возвращает случайный элемент
• my_set.pop(5) → TypeError: аргументы не принимаются
• my_set.clear() — опустошает множество до set()

Что выводит: remove(5) → None, множество {1, 2, 3, 4}; повторный remove(5) → KeyError: 5. discard(4) → None, {1, 2, 3}; discard(100) на отсутствующем элементе → None, множество не изменилось. pop() вернул 1 (в данном запуске), осталось {2, 3}; pop(5) → TypeError: set.pop() takes no arguments (1 given). clear() → None, множество стало set().

"""Методы множества"""


my_set = {1, 2, 3, 4, 5}

print(""" 1. ====================== remove(value) ====================== """)
print(my_set.remove(5))    # None
print(my_set)              # {1, 2, 3, 4}

try:
    my_set.remove(5)
except Exception as e:
    print(f"{e.__class__.__name__}: {e}")  # KeyError: 5

"""Методы множества"""


my_set = {1, 2, 3, 4, 5}

print(""" 1. ====================== remove(value) ====================== """)
print(my_set.remove(5))    # None
print(my_set)              # {1, 2, 3, 4}

try:
    my_set.remove(5)
except Exception as e:
    print(f"{e.__class__.__name__}: {e}")  # KeyError: 5


print(""" 2. ====================== discard(value) ====================== """)
print(my_set)               # {1, 2, 3, 4}
print(my_set.discard(4))    # None
print(my_set)               # {1, 2, 3}

print(my_set.discard(100))  # None
print(my_set)               # {1, 2, 3}


print(""" 3. ====================== pop() ====================== 
(удаление случайного элемента)
""")
print(my_set.pop())         # 1
print(my_set)               # {2, 3}

try:
    my_set.pop(5)
except Exception as e:
    print(f"{e.__class__.__name__}: {e}")  # TypeError: set.pop() takes no arguments (1 given)


print(""" 4. ====================== clear() ====================== """)
print(my_set)               # {2, 3}
print(my_set.clear())       # None
print(my_set)               # set()

Графики: обратимые функции против хэш-функции

less_17__hash__set/theory_98_function_graphs.py

Визуальное дополнение к теме односторонних функций из theory_01: строит графики y=x и y=x² (обратимые, хотя x² неоднозначно обратима без знака) и y=1/x (тоже обратимая), а затем — график y=hash(x) % 10000, чтобы показать, насколько «случайно» и непредсказуемо выглядит хэш-функция по сравнению с гладкими математическими функциями. Файл требует установки `numpy` и `matplotlib` (указано в первой строке файла).

• import numpy as np, import matplotlib.pyplot as plt
• x = np.linspace(-10, 10, 400) — диапазон значений для графиков
• Подграфики y=x, y=x² (с отмеченной точкой минимума), y=1/x
• y4 = [hash(xi) for xi in x] — хэш каждого значения x, нормализован через % 10000
• Отдельная фигура: scatter-график y = hash(x) % 10000 — «шум» без видимой закономерности

Что выводит: Скрипт не выполнился: `ModuleNotFoundError: No module named 'matplotlib'` — в текущем окружении установлен numpy, но matplotlib отсутствует (комментарий в файле явно просит `pip install numpy matplotlib PyQt5`). При наличии зависимостей скрипт откроет два окна с графиками.

"""pip install numpy matplotlib PyQt5"""

import numpy as np
import matplotlib.pyplot as plt

# Создаём диапазон значений x
x = np.linspace(-10, 10, 400)
x_nonzero = x[x != 0]  # Исключаем ноль для функции y = 1/x

# Вычисляем значения функций
y1 = x
y2 = x ** 2
y3 = 1 / x_nonzero
y4 = [hash(xi) for xi in x]  # Используем хеш-функцию

"""pip install numpy matplotlib PyQt5"""

import numpy as np
import matplotlib.pyplot as plt

# Создаём диапазон значений x
x = np.linspace(-10, 10, 400)
x_nonzero = x[x != 0]  # Исключаем ноль для функции y = 1/x

# Вычисляем значения функций
y1 = x
y2 = x ** 2
y3 = 1 / x_nonzero
y4 = [hash(xi) for xi in x]  # Используем хеш-функцию
y4_normalized = np.array(y4) % 10000  # Нормализуем значения хеша для визуализации

# Создаём фигуру и оси для трёх функций
plt.figure(figsize=(10, 8))

# График y = x
plt.subplot(3, 1, 1)
plt.plot(x, y1, label='y = x', color='blue')
plt.title('y = x')
plt.xlabel('x')
plt.ylabel('y')
plt.grid(True)
plt.legend()

# График y = x^2
plt.subplot(3, 1, 2)
plt.plot(x, y2, label='y = x^2', color='green')
plt.scatter(0, 0, color='red', zorder=5)  # Точка минимума
plt.title('y = x^2')
plt.xlabel('x')
plt.ylabel('y')
plt.grid(True)
plt.legend()

# График y = 1/x
plt.subplot(3, 1, 3)
plt.plot(x_nonzero, y3, label='y = 1/x', color='red')
plt.title('y = 1/x')
plt.xlabel('x')
plt.ylabel('y')
plt.grid(True)
plt.legend()

# Настраиваем макет и отображаем графики
plt.tight_layout()
plt.show()

# Создаём фигуру для функции y = hash(x)
plt.figure(figsize=(10, 4))
plt.scatter(x, y4_normalized, label='y = hash(x) % 10000', color='purple', s=10)
plt.title('y = hash(x)')
plt.xlabel('x')
plt.ylabel('y')
plt.grid(True)
plt.legend()
plt.show()

hashable ≠ immutable: два контрпримера

less_17__hash__set/theory_999_hashable_vs_mutable.py

Разрушает частое заблуждение «хэшируемое = неизменяемое» двумя контрпримерами. Первый: кортеж `(1, 2, [3])` формально неизменяем (нельзя переприсвоить элемент), но `hash()` на нём падает, потому что внутри лежит изменяемый список. Второй: пользовательский класс `Hashable`, у которого `__hash__` всегда возвращает константу 777 — объект спокойно хэшируется, хотя его атрибут `x` меняется после создания. Итоговый вывод в комментарии: Python гарантирует не абсолютную неизменяемость, а стабильность хэша.

• t = (1, 2, [3]) — неизменяемый кортеж с изменяемым элементом внутри
• hash(t) → TypeError: unhashable type: 'list' (ошибка из-за вложенного списка)
• class Hashable — __hash__() всегда возвращает 777
• h.x = 2 после создания — атрибут меняется, hash(h) остаётся 777
• Вывод: hashable — это про стабильность hash(), а не про абсолютную неизменяемость

Что выводит: Сообщение об ошибке из перехваченного TypeError: unhashable type: 'list'. Далее для объекта Hashable: 1 (h.x до изменения), 777 (hash(h)), 2 (h.x после изменения), 777 (hash(h) не изменился, несмотря на изменение атрибута).

# --- Не изменяемый, но не хэшируемый ---------------

t = (1, 2, [3])

try:
    hash(t)
except TypeError as e:
    print(e)


# --- Хэшируемый, но изменяемый --------------------

class Hashable:
    def __init__(self, x):

# --- Не изменяемый, но не хэшируемый ---------------

t = (1, 2, [3])

try:
    hash(t)
except TypeError as e:
    print(e)


# --- Хэшируемый, но изменяемый --------------------

class Hashable:
    def __init__(self, x):
        self.x = x

    def __hash__(self):
        return 777


h = Hashable(1)
print(h.x)      # 1
print(hash(h))  # 777

h.x = 2
print(h.x)      # 2
print(hash(h))  # 777


"""
Python гарантирует не “абсолютную неизменяемость”, а стабильность хэша и поведения.

В Python hashable ВСЕГО ЛИШЬ означает, 
что объект ведёт себя как неизменяемый в части, влияющей на hash.
"""

Хэш-таблица своими руками: имитация set вручную

less_17__hash__set/theory_99_hash_table.py

Ручная реализация упрощённой хэш-таблицы поверх обычного списка, чтобы показать, как под капотом устроен `set`. Функция `_hash()` вычисляет индекс ячейки через `hash(value) % hash_table_size`, `add_item()` кладёт значение в список по этому индексу (с разрешением коллизий через список-«корзину»), `is_item_in_set()` проверяет наличие. На восьми названиях фруктов/овощей видно, как несколько разных строк могут попасть в одну и ту же корзину (коллизия) — например, значения 'Date' и 'Grape' в одном run оказались в одной ячейке.

• _hash(value) — hash(value) % hash_table_size, вычисление индекса
• add_item(value) — кладёт значение в список-корзину по индексу, проверяя дубли
• is_item_in_set(value) — ищет значение в корзине по вычисленному индексу
• print_table(lst) — печатает таблицу «индекс → список значений»
• hash_table_size = len(items) — размер таблицы под 8 элементов
• Коллизия: 'Date' и 'Grape' попали в одну корзину (индекс 3)

Что выводит: Пустая таблица из 8 ячеек (все None). После добавления всех 8 элементов: ячейка 0 пуста, 1 → ['Apple'], 2 → ['Cherry'], 3 → ['Date', 'Grape'] (коллизия — обе строки попали в одну корзину), 4 пуста, 5 → ['Kiwi'], 6 → ['Fig'], 7 → ['Banana', 'Lemon'] (ещё одна коллизия). Конкретные индексы зависят от значения `hash()` строки, которое в Python рандомизировано между запусками процесса (PYTHONHASHSEED) — при другом запуске распределение по ячейкам может быть другим.

"""Дан список овощей и фруктов
items = ["Apple", "Banana", "Cherry", "Date", "Fig", "Grape", "Kiwi", "Lemon"]
Необходимо поместить его в хэш таблицу, имитирующую объект set
"""


def _hash(value: str) -> int:
    """Функция для вычисления индекса с помощью hash()"""
    return hash(value) % hash_table_size


def add_item(value):
    idx = _hash(value)

"""Дан список овощей и фруктов
items = ["Apple", "Banana", "Cherry", "Date", "Fig", "Grape", "Kiwi", "Lemon"]
Необходимо поместить его в хэш таблицу, имитирующую объект set
"""


def _hash(value: str) -> int:
    """Функция для вычисления индекса с помощью hash()"""
    return hash(value) % hash_table_size


def add_item(value):
    idx = _hash(value)

    if hash_table[idx] is None:
        hash_table[idx] = [value]
    else:
        if value not in hash_table[idx]:
            hash_table[idx].append(value)


def is_item_in_set(value):
    idx = _hash(value)

    if hash_table[idx] is None:
        return False
    else:
        return value in hash_table[idx]


def print_table(lst):
    print("Index | Items")
    print("------+----------------------")
    for i, value in enumerate(lst):
        print(f"{i:<5} | {value}")
    print("------+----------------------")
    print()


items = ["Apple", "Banana", "Cherry", "Date", "Fig", "Grape", "Kiwi", "Lemon"]

# Определяем размер и создаём по нему хэш таблицу
hash_table_size = len(items)
hash_table: list[None | list[str]] = [None] * hash_table_size
# [None, None, None, None, None, None, None, None]
print_table(hash_table)

for item in items:
    add_item(item)

print_table(hash_table)