Ciencia de los datos - entrevistas

🤔 Как избегают коллизии в хеш мапе ? Это ситуации, когда два ключа имеют один и тот же хеш-код и, следовательно, претендуют на одно и то же место в структуре данных. Управление коллизиями — важная часть дизайна хеш-таблиц, поскольку эффективность хеш-таблицы сильно зависит от того, насколько эффективно решается проблема коллизий. 🚩Открытая адресация (Open Addressing) Открытая адресация решает проблемы коллизий путем поиска другого места в хеш-таблице для элемента, вызвавшего коллизию. Существуют различные методы открытой адресации: 🟠Линейное пробирование При коллизии проверяется следующая ячейка таблицы. Если она занята, проверяется следующая и т.д., пока не будет найдена свободная ячейка. 🟠Квадратичное пробирование Используется квадратичная функция для вычисления смещения от исходной позиции при каждом шаге пробирования (например, 1, 4, 9, 16 и т.д.). 🟠Двойное хеширование Используются две хеш-функции для вычисления начального индекса и шага пробирования, чтобы найти свободную ячейку. 🚩Сцепление (Chaining) Это метод, при котором каждая ячейка хеш-таблицы содержит указатель на связный список (или другую структуру данных, такую как дерево), содержащий все элементы, которые были отображены в эту ячейку. При коллизии новый элемент просто добавляется в конец списка. Сцепление может обрабатывать неограниченное количество коллизий, хотя производительность может снизиться, если списки становятся слишком длинными. 🚩Рехеширование (Rehashing) Рехеширование предполагает использование дополнительных хеш-функций при коллизиях. Если первичная хеш-функция приводит к коллизии, применяется вторая хеш-функция, и так далее, пока не будет найдена свободная ячейка или не будут использованы все доступные хеш-функции. class HashTable: def __init__(self, size=10): self.size = size self.table = [[] for _ in range(size)] def hash_function(self, key): return hash(key) % self.size def insert(self, key, value): index = self.hash_function(key) for item in self.table[index]: if item[0] == key: item[1] = value return self.table[index].append([key, value]) def get(self, key): index = self.hash_function(key) for item in self.table[index]: if item[0] == key: return item[1] raise KeyError('Key not found') def remove(self, key): index = self.hash_function(key) for i, item in enumerate(self.table[index]): if item[0] == key: del self.table[index][i] return raise KeyError('Key not found') # Пример использования ht = HashTable() ht.insert("key1", "value1") ht.insert("key2", "value2") print(ht.get("key1")) # выводит "value1" ht.remove("key1") Ставь 👍 и забирай 📚 Базу знаний