основные отличия между наборами и массивами

1656582615 osnovnye otlichiya mezhdu naborami i massivami

Энтони Систилли

7o1xXfQuKhqwU3ckJa3GHk57DbE9lVSEibHH

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

Чтобы ответить на этот вопрос, мы должны понять фундаментальные отличия между набором и массивом.

Если вы учитесь наглядно и предпочитаете видео-объяснение, вот 3-минутное видео, объясняющее ответ (хотя и менее глубоко).

Массивы были одной из первых структур данных, которые я научился использовать.

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

Лишь позже в моей программной карьере я познакомился со странным, но очаровательным двоюродным братом массива:

Набор.

Наборы похожи на массивы… за исключением того, что это не так.

Давайте быстро напомним себе, как работает массив

Массивы:

  • Заказываются
  • Иметь индексы, начиная с 0
  • Может содержать повторяющиеся элементы
  • Иметь время поиска O(n), когда вы ищете элемент

Однако наборы ведут себя несколько иначе

Наборы:

  • Есть неупорядоченный (почти на всех языках)
  • Иметь хешированные индексы
  • Может НЕ содержать повторяющихся элементов
  • Есть O(1) время поиска при поиске элемента

Давайте рассмотрим поглубже.

1. Устанавливает Insert By Hashing

Элементы в наборе хранятся совсем по другому, чем в массиве.

Способ хранения элементов набора зависит от Хеширование.

Скажем, вы хотите сохранить символ А в наборе и массиве.

Массив просто найдет следующий доступный индекс, если не указано иное, и поместить элемент в этот индекс.

FwFrdUKwMFGwt5B01MWujBfopRwiSCap8Wcn
Наша А получает индекс 0, поскольку она является первым элементом.

Однако с хешированием все обстоит несколько иначе.

Как работает хеширование

Хеширование является актом принятия входных данных (x), их искажения посредством конкретной хэш-функции (h) и получения конечного результата (y).

В основном h(x) = (y)

Выглядит немного запутано, верно?

Не волнуйся! Это должно прояснить ситуацию.

Простым примером функции хеширования (h) может быть добавление «asdf» в конец вашего ввода (x).

Если (x) равно «A», а добавление «asdf» — это (h), выход (y) будет просто таким:

«A» + «asdf» → «Aasdf»

Итак, «Aasdf» будет нашим (y).

Итак, как набор использует хеширование?

Набор использует хеширование, чтобы решить, где хранить введенные данные (x).

Короче говоря, набор принимает входные данные, хеширует их и хранит в индексе, соответствующем хешированному вводу, то есть выходу (y).

mX-gjXZ-UBKN-KrZtS-D5TrPeWs6RMJpUzk-
Aasdf – это индекс нашего элемента «А».

Это причина, почему множество не упорядочены в большинстве языков.

Индексация массива проста, от 0 до n, так что вы можете легко запомнить, что будет дальше.

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

2. Наборы не могут содержать копии

Это верно!

Набор может содержать только уникальные элементы.

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

Почему это делаете, спросите вы?

Ну из-за хеширования!

Поскольку моя функция хеширования (h) будет оставаться последовательной во время выполнения моей программы, ввод одинакового (x) всегда даст вам то же самое (y).

Это означает, что если я попытаюсь вставить вторую «А», моя хэш-функция выведет тот же адрес, что и первая «А», и это просто перезапишет его!

IyMXWH3PLwT0wcCwoRflRpnwCgIVLQSFIQnS

С массивом он просто добавит вторую «А» к следующему доступному индексу.

3. Наборы имеют O(1) время поиска

Скажем, у вас есть массив п элементов, где п — большое число, и вы хотели проверить, существует ли A в этом массиве.

Ну, в худшем случае, «А» не существует.

И чтобы это выяснить, вам придется все перебирать п этих элементов!

KwkpUKEYPgs4TdrbGRCgfqdSayyFRCJ33eWC
МАССИВ. OF. FORTUNE!

Это придает массиву временную сложность O(n), когда дело доходит до поиска элемента.

Мы можем сэкономить много времени с помощью набора

Если мы хотим узнать, существует ли элемент в нашем наборе, все, что нам нужно сделать, это хешировать этот элемент и проверить индекс!

Помните: индекс, в котором хранится элемент, связанный с элементом.

Поэтому если мы хотим проверить, существует ли «A» в нашем наборе, нам просто нужно было бы хешировать его (+ «asdf») и проверить этот индекс!

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

Это означает, что набор имеет временную сложность O(1), когда дело доходит до поиска элемента… Что огромное улучшение!

Можете ли вы припомнить ситуации, когда это полезно?

Если вы не можете, просмотрите этот вопрос для интервью Google, где набор имеет значение!

Спасибо, что прочли!

.a

PS — Чтобы получить дополнительные руководства по структуре данных и алгоритмов, а также подготовку к собеседованию, просмотрите www.TheForge.ca!

Мы помогаем студентам и новым выпускникам получить работу в программном обеспечении мечты!

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *