Один из ключевых инструментов, который должен знать программист, — это какие структуры данных существуют и как их использовать. Я собираюсь дать краткий обзор некоторых ключевых структур данных, которые я определенно нашел полезными.
Хеш-таблицы. Хэш-таблицы — это таблицы поиска, обеспечивающие быстрый доступ. В мире программирования (и вообще) мы хотим, чтобы все было максимально эффективно, и поскольку хэш-таблицы требуют только постоянного времени O (1) для поиска, они являются хорошим вариантом!
Мы создаем таблицу с «ключом» и «значением» для каждого элемента в таблице. Ключ используется для целей индексации, а значение — это то, что вы действительно хотите сохранить/получить/удалить.
Давайте рассмотрим пример:
Пример:
Предположим, у меня есть большой объем данных, к которым я хочу быстро получить доступ. Обычно я мог бы использовать массив для хранения данных и просто искать его, если бы у меня был разумный размер данных. Но напомню, поиск по всем элементам массива занимает довольно много времени.
Итак, мы используем хеш-функцию для индексации элементов, где мы можем легко получить к ним доступ позже.
Скажем, у нас есть элементы:
И, например, у нас есть следующее хеш-уравнение:
Таким образом, мы соответственно подставляем каждое число в хэш-уравнение и получаем:
Работая в обратном направлении от значений, мы можем увидеть, каким ключам должны быть назначены значения в таблице. Используя ключи в качестве индексов, мы можем заполнить нашу таблицу:
Мы видим, что каждый элемент теперь занимает свое место в таблице в соответствии с хэш-функцией. И мы знаем, например, что если кто-то захочет добавить в таблицу значение 1049, оно будет иметь индекс 6.
Таким образом, мы можем получить доступ/добавить/изменить/удалить любой элемент.
Теперь возникает очевидный вопрос: что, если мы попадем в один и тот же индекс более одного раза? Это то, что произошло выше, когда оба значения 400 и 567 были хешированы до индекса 3. Это называется коллизией.
Один изспособов борьбы с коллизиями называется цепочкой. Цепочка — это когда вы просто добавляете каждый элемент в связанный список по этому индексу и продолжаете увеличивать список каждый раз, когда значение оказывается там.
Как выбрать хеш-функцию?
Стремитесь уменьшить количество столкновений и выберите функцию, которая может обеспечить быстрое вычисление.
Общая структура в C++:неупорядоченные карты из STL — это хэш-таблицы C++. Документацию можно найти здесь: https://en.cppreference.com/w/cpp/container/unordered_map.
Общая структура в Python. Словари — замечательная функция Python. По сути, это хеш-таблицы, в которых для хранения элементов используется система «ключ-значение», где ключ и значение не обязательно должны быть целыми числами!