Интервью Вопрос: Что такое хэш-карта?

Меня спросили в интервью: "Расскажите мне все, что вы знаете о хэшмапах".

Я продолжал делать именно это: это структура данных с парами ключ-значение; для нахождения элемента используется хеш-функция; как хэш-коллизии могут быть разрешены и т.д.

После того, как я закончил, они спросили: "Хорошо, теперь объясняйте все, что вы только что сказали 5-летнему. Вы не можете использовать технические термины, особенно хэширование и картографирование".

Я должен сказать, что это застало меня врасплох, и я не дал хорошего ответа. Как бы вы ответили?

Ответ 1

Давайте возьмем большую книгу слов или словарь и попытаемся найти слово зебра. Мы можем легко догадаться, что зебры будут ближе к концу книги, точно так же, как буква "Z" находится в конце алфавита. Теперь скажем, что мы всегда можем найти, где зебра внутри большой книги слов. Именно так мы можем быстро найти зебры, слоны или любые другие вещи, о которых мы можем думать в большой книге слов. Иногда два слова будут на одной странице, например apple и ant. Мы уверены, на какой странице мы хотим посмотреть, но мы не знаем, насколько близко Apple и ant друг к другу, пока мы не перейдем на страницу. Иногда apple и ant могут находиться на одной странице, а иногда они могут и не быть, в некоторых больших словарных книгах есть большие слова.

Как бы я это сделал.

Ответ 2

Правила. Дети знают правила. Дети знают, что некоторые предметы принадлежат определенным местам. HashMap похож на набор правил, которые говорят, учитывая предмет (ваша обувь, ваша любимая книга или ваша одежда), что есть определенное место, куда они должны идти (стойка для обуви, книжная полка или шкаф).

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

Но подождите: что произойдет, если стойка для обуви уже заполнена? Есть несколько вариантов.

1) Для каждого элемента есть список мест, которые вы можете попробовать. Попробуйте поставить их рядом с дверью. Но подождите, там что-то уже есть: где еще мы можем их поместить? Попробуйте шкаф. Если нам нужно найти обувь, мы будем следовать тому же списку, пока не найдем их. (зондирующие последовательности)

2) Купите большой дом с более большой стойкой для обуви. (динамическое изменение размера)

3) Наденьте обувь поверх стойки, игнорируя тот факт, что это создает реальную боль, чтобы найти правильную пару, потому что мы должны пройти все ботинки в куче, чтобы найти их. (Цепочки).

Ответ 3

Говоря как родитель, если бы мне пришлось объяснить хэш-карту 5-летнему ребенку, я бы точно сказал, что вы сказали, размахивая шоколадным кексом.

Серьезно, такие вопросы, как это, должны означать "можете ли вы объяснить концепцию на простом английском", хорошая эвристика, насколько хорошо вы усвоили свое понимание этого. Поскольку кажется, что вы это понимаете, вопрос кажется немного глупым.

Ответ 4

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

Ключевым преимуществом использования HashMap является то, что, как индекс в книге, гораздо быстрее искать страницу в индексе включено слово в индекс, чем было бы начать поиск по страницам для этого слова.

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

Ответ 5

У вас есть книга пустых, но пронумерованных страниц и специальное кольцо декодера, которое генерирует номер страницы, когда в нее что-то вводится.

Чтобы назначить значение:

Вы получаете идентификатор (ключ) и сообщение (значение).

Вы помещаете идентификатор в специальное кольцо декодера и выливаете номер страницы.

Откройте свою книгу на этой странице. Если идентификатор находится на странице, вычеркните ID/сообщение.

Теперь напишите ID и сообщение на странице. Если уже есть один или несколько других идентификаторов с сообщениями, просто напишите новый под ним.

Чтобы получить значение:

Вам предоставляется только идентификатор (ключ).

Вы помещаете идентификатор в специальное кольцо декодера и выливаете номер страницы.

Откройте свою книгу на этой странице. Если идентификатор находится на странице, прочитайте сообщение (значение), которое следует за ним.