Šta je hash i kako se koristi u rečnicima u Pythonu…

Хеш (или хеш-вредност) је бројчана вредност фиксне дужине која се израчунава на основу садржаја објекта помоћу хеш-функције. Добра хеш-функција обезбеђује детерминисаност (односно исти објекат увек даје исти хеш) и тежи ка равномерном распореду хешева за различите објекте.

У Python-у, речници (тип dict) користе хешовање за ефикасно чување и претрагу парова "кључ-вредност". Кључеви у речнику морају бити хешибилни, односно да имају метод __hash__() и да буду имутабилни или да имају имплементацију __eq__() и __hash__() која гарантује да равни објекти имају исти хеш.

Процес рада речника са хешевима:

Уметање: При додавању пара (кључ, вредност), израчунава се хеш кључа. На основу хеша одређује се приближно место (кошница или "bucket") за чување тог пара у меморији. Ако више кључева има исти хеш (колизије), парови се чувају у тој кошници, често у виду повезане листе или другог механизма за решавање колизија.
Претрага: При претрази вредности по кључу, израчунава се хеш датог кључа. Помоћу хеша, речник брзо налази одговарајућу кошницу. Затим унутар те кошнице се пореде кључеви (__eq__()), да би се пронашао жељени кључ и добила везана вредност.

Предности хеширања:

Ефективност: У просеку, операције уметања, брисања и претраге у речнику се извршавају са константном временском сложеношћу O(1), без обзира на величину речника.
Брз приступ: Хеш омогућава брз приступ подацима, прескачући преглед свих елемената.

Ограничења и карактеристике:

Хешибилни кључеви: Као што је поменуто, кључеви морају бити хешибилни. Модификовани типови као што су листе (list) и скупови (set) по подразумеваним вредностима нису хешибилни и не могу се користити као кључеви.
Колизије: Иако хеш-функције настоје да минимизирају колизије, оне могу настати, што може мало успорити операције у најгорем случају (утиче на константу у O(1)).
Ред: До Python 3.7, ред елемената у речнику зависио је од реда уметања и хешева кључева. Од Python 3.7, речници задржавају ред уметања као споредни ефекат имплементације, али то није део механизма хеширања.

Пример хешибилног и нехешибилног објекта:

# Хешибилни објекат (непроменљив)
string_key = "hello"
int_key = 123
tuple_key = (1, 2)

print(hash(string_key))
print(hash(int_key))
print(hash(tuple_key))

# Нехешибилни објекат (променљив)
list_key = [1, 2]
# print(hash(list_key)) # Ово ће изазвати TypeError

# Пример коришћења у речнику
my_dict = {
    string_key: "world",
    int_key: 456,
    tuple_key: "тупле"
}

print(my_dict[string_key])
print(my_dict[int_key])
print(my_dict[tuple_key])

Дакле, хеш је основни механизам који омогућава речницима у Python-у да постигну високу перформансу операција заснованих на брзом израчунавању бројчане репрезентације кључа.

Šta je hash i kako se koristi u rečnicima u Pythonu?