При построении решений в качестве программиста всегда следует учитывать временную сложность; необходимость оптимизации - это простой жизненный факт. Этот процесс может быть невероятно разочаровывающим, особенно для тех, кто только начинает задумываться о скорости вычислений. Однако существуют структуры для организации и обработки данных, которые значительно более эффективны, чем доступные альтернативы. Эти структуры представляют собой необходимый инструмент для успешных разработчиков, один из которых мы будем изучать вместе: хеш-таблицы.
Поиск в массиве имеет линейную временную сложность, так как поиск конкретного элемента в худшем случае требует циклического перебора каждого элемента. Если вы не знакомы с временной сложностью и вам интересно, прочтите это. Представьте, что пользователем нашей программы была фирма по управлению данными, обрабатывающая внутреннюю информацию, чтобы лучше понять взаимосвязь между уровнем заболеваемости раком и близостью к большому водоему с пресной водой. Они планируют запустить несколько миллионов входных данных с помощью нашей функции, сохраняя профиль для каждого человека с информацией об их состоянии здоровья и количестве миль от озера. Как можно сохранить эти профили таким образом, чтобы их получение происходило мгновенно (O (1): постоянное время)? Мы можем реализовать хеш-таблицу, особую структуру данных, которая использует объекты javascript для создания структуры с числовым индексом для хранения пар ключ-значение (известных как кортежи). Я повторю это еще раз: в хэш-таблицах хранятся пары ключ-значение и числовые индексы, сгенерированные при запуске ключа с помощью функции хеширования.
Функция хеширования - это часть программы, которая принимает ключ и преобразует его в число, которое будет индексом для его сохранения. Визуализируйте поле, в которое вы опустошаете контейнер кортежей или пар ключ-значение. Выходные данные - это массив, в котором пара ключ-значение хранится под числовым индексом. Способ присвоения индекса зависит от реализации хэш-функции. Не все функции хеширования равны, некоторые лучше справляются с равномерным распределением пар ключ-значение. Если каждый кортеж помещен в один и тот же индекс, то временная сложность будет сопоставима со сложностью простого массива, линейного.
Здесь мы инициализируем класс HashTable:
Пример реализации функции хеширования ниже, изначально размещенный здесь:
Вторая часть реализации хеш-таблицы - это логика, предназначенная для обработки коллизий или экземпляров, в которых есть несколько значений в определенном индексе, называемых бакетом. Это достигается путем перебора всех кортежей в интересующем индексе хэш-таблицы для поиска нужного кортежа.
При сравнении объектов и хеш-таблиц возникает большая путаница. Это очень похоже на попытку сравнения между яблоками и яблоками Гренни Смит, одно является подмножеством другого с определенными качествами. Преимущества, предлагаемые хэш-таблицами, включают возможность обрабатывать случаи, когда ключ соответствует атрибуту собственного объекта и обеспечивает постоянный поиск по времени. Ниже приведен метод получения, добавленный к прототипу нашего класса HashTable с постоянным в среднем временем поиска:
Разработчикам чрезвычайно важно понимать, что происходит в черных ящиках, используемых в нашем коде, чтобы развивать и реализовывать идеи новыми и творческими способами. Однако есть структура данных, голые объекты, которая предлагает те же преимущества, что и хеш-таблица в javascript, без утомительной необходимости ее сложной реализации. Обходной путь для этого - создать экземпляр объекта без какого-либо выхода из контекста, используя простые объекты, представленные в ES5. По сути, метод create в прототипе Object позволяет создать экземпляр нового объекта с указанной цепочкой делегирования. Отсюда следует, что передача null создаст экземпляр объекта без собственных атрибутов . Подробнее о голых объектах здесь.
Активно обсуждается вопрос о том, все ли объекты javascript реализованы в виде хеш-таблиц. Хорошая новость в том, что вам не о чем беспокоиться! Javascript абстрагирует ненужные детали, позволяя проектировать более сложные системы.
Продолжайте кодировать!
Иаков
