Встречается на собеседованиях • сегодня

Как сделать хэш-таблицу

В Python хэш-таблицы реализованы через встроенный тип dict. Для создания:

python
hash_table = {}  # или dict()
hash_table['key'] = 'value'  # добавление
value = hash_table.get('key')  # получение
del hash_table['key']  # удаление

Особенности:

  • Ключи должны быть хешируемыми (неизменяемые типы: str, int, tuple).
  • Коллизии обрабатываются автоматически.
  • Время доступа ~O(1) в среднем случае.

Кастомная реализация (упрощенная):

python
class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]  # Чейнинг для коллизий

    def _hash(self, key):
        return hash(key) % self.size

    def set(self, key, value):
        h = self._hash(key)
        for i, (k, v) in enumerate(self.table[h]):
            if k == key:
                self.table[h][i] = (key, value)
                return
        self.table[h].append((key, value))

    def get(self, key):
        h = self._hash(key)
        for k, v in self.table[h]:
            if k == key:
                return v
        raise KeyError(key)
Sophi
Софи собрала все вопросы. Тренируйся и получай
офферы быстрее!
Попробовать бесплатноArrow

Следующий вопрос

Это единственный вопрос по вашему фильтру

как отвечать на вопрос
пример собеседования
фреймворки на собеседовании
типичные вопросы junior
интервью вопросы и ответы