Таблиғи хеш аз кадом компонентҳо иборат аст?

Ҳеш таблица асосан икки компонентдан иборат:

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 # Калит топилмади