Встречается на собеседованиях • сегодня
Как устроена хеш-таблица (HashMap)
Хеш-таблица — это структура данных, которая хранит пары ключ-значение. Она использует хеш-функцию для вычисления индекса (хеша) ключа, по которому значение сохраняется в массиве (бакетах).
Основные принципы:
- Хеш-функция преобразует ключ в индекс массива.
- Коллизии (когда разные ключи дают одинаковый хеш) решаются:
- Методом цепочек (списки в бакетах).
- Открытой адресацией (поиск следующего свободного слота).
Пример на Python (упрощённый):
python
class HashMap:
def __init__(self, size=10):
self.size = size
self.buckets = [[] for _ in range(size)]
def _hash(self, key):
return hash(key) % self.size
def put(self, key, value):
index = self._hash(key)
for i, (k, v) in enumerate(self.buckets[index]):
if k == key:
self.buckets[index][i] = (key, value)
return
self.buckets[index].append((key, value))
def get(self, key):
index = self._hash(key)
for k, v in self.buckets[index]:
if k == key:
return v
raise KeyError(key)
Софи собрала все вопросы. Тренируйся и получай
офферы быстрее!
офферы быстрее!
Попробовать бесплатно
Следующий вопрос
Это единственный вопрос по вашему фильтру
как отвечать на вопрос
пример собеседования
фреймворки на собеседовании
типичные вопросы junior
интервью вопросы и ответы