Блог

Главная - Вопросы по программированию - Хэш-карта, когда использовать какой метод?

Хэш-карта, когда использовать какой метод?

#python #data-structures #hashmap #hashtable

Вопрос:

Я изучал хэш-карты и их лучшие практики. Одной из вещей, на которую я наткнулся, было разрешение столкновений.

Эти методы включают в себя:

  • Прямая Цепочка,
  • Линейное Зондирование,
  • Квадратичное Зондирование,
  • Двойное Перемешивание.

До сих пор я обнаружил, что прямая цепочка была намного проще в реализации и имела наибольший смысл. Я не уверен, на чем мне следует сосредоточиться с точки зрения подготовки к техническим собеседованиям.

Комментарии:

1. Любой технический интервьюер, который просит вас сравнить методы хеширования, ищет не то, что нужно. Ни один профессиональный программист не пишет хэш-алгоритмы. Мы все слишком заняты, пытаясь закончить работу. Мы будем использовать Python dict или C std::map , мы не будем писать свои собственные.

2. Цепочка впала в немилость. Во всяком случае, это тот вариант, на котором вы можете сосредоточиться меньше всего. Кстати std::map , это не хэш-карта, смотрите std::unordered_map .

3. ФУ, я не понимаю, почему вы включили тег «python». Ваш вопрос не зависит от языка. Если Python имеет отношение к делу, то ваш вопрос не имеет никакого смысла.

4. @TimRoberts: как руководитель отдела разработки SW в фирме HFT, я возражаю против ваших обобщений. Мы не только пишем хэш — таблицы и функции и выбираем подходы к управлению конфликтами, такие как перечисленные (часто, чтобы мы могли сопоставить реализацию на ПЛИС) — еще чаще нам нужно понимать такие варианты реализации, чтобы сделать обоснованный выбор из внешних предложений (robin_hood, Google absl, Facebook folly f14 и т. Д.) И настроить их использование.

Ответ №1:

Для технических интервью я бы предложил получить представление о плюсах/минусах этих подходов на высоком уровне, в частности:

  • прямая цепочка медленно ухудшается по мере увеличения коэффициента загрузки, в то время как подходы к закрытому хэшированию/открытой адресации (все остальные, которые вы перечисляете) экспоненциально ухудшаются по мере увеличения коэффициента загрузки 1.0, поскольку становится все труднее и труднее найти пустое ведро
  • линейное зондирование может быть удобным для кэширования ЦП с помощью небольших ключей (по сравнению с любым другим методом): если вы можете поместить несколько ключей в одну и ту же строку кэша, это означает, что ЦП, скорее всего, потратит меньше времени на поиск в памяти после столкновений (и инструкции SIMD иногда могут помочь сравнить с ключами нескольких блоков одновременно).
  • линейное зондирование и хэширование идентификаторов могут привести к более низким, чем при криптографическом хэшировании, коэффициентам коллизий для ключей, которые имели хорошее распределение по сегментам, например идентификаторы, которые имеют тенденцию к увеличению, но могут иметь разрывы здесь и там
  • линейное зондирование гораздо более подвержено кластерам столкновений, чем квадратичное зондирование, особенно с плохими хэш-функциями / ключами с трудными для хэширования колодцами и более высокими коэффициентами нагрузки (например, > = 0,8), поскольку столкновения в одной части таблицы (даже если случайно больше, чем ошибочное хэширование), как правило, усугубляют использование этой части таблицы в будущем
  • квадратичное зондирование может иметь пару смещений в одной строке кэша, которые могут попадать в одну и ту же строку кэша, поэтому вы можете получить полезную вероятность того, что вторая и даже третья строка будут находиться в той же строке кэша, что и первая, но после нескольких сбоев вы будете прыгать с большим шагом, уменьшая проблемы с кластеризацией за счет большего количества пропусков в кэше
  • двойное хеширование — это своего рода компромисс; если второй хеш выдает 1, то это эквивалентно линейному зондированию, но вы можете попробовать каждое 2-е ведро или каждое 3-е и т. Д.-До некоторого предела. Все еще есть много места для кластеризации (например, если h2(k) вернул 6 для одного ключа и 3 для другого ключа, который был привязан к ведру 3 дальше в таблице, чем первый ключ, тогда они посетят многие из тех же ведер во время своих поисков.

Я бы не рекомендовал сосредотачиваться на каком-либо из них с большой глубиной или игнорировать их, потому что контрасты усиливают ваше понимание любого из других.

Метки: ,