Другая функция, которая вам быстро понадобится, - это возможность использовать произвольные объекты в качестве ключей в хэш-карте. В языках, которые не поддерживают это (до недавнего времени Perl, Python, Go, JavaScript), вы можете использовать строки в качестве ключей, создавая уникальную строку для каждого ключевого объекта. Это не очень элегантно, и ваша программа создает множество строк, которые на самом деле не должны существовать.
Более продвинутым является возможность указать функцию равенства для ключей на карте. В Java и Toit, например, вы можете указать собственный метод equals для класса ключей в коллекции. Напротив, реализация карты в JavaScript использует только идентичность объекта. Вы не можете создать новый объект, а затем узнать, есть ли на карте эквивалентный ключ. Опять же, неэлегантный обходной путь состоит в том, чтобы каждый из них генерировал строки и использовал их в качестве ключей.
Идя еще дальше, иногда необходимо указывать функцию равенства для каждой карты, а не для каждого типа ключа. Это доступно в C ++ в виде параметров шаблона Hash и Pred на unordered_map. (Но, как указывает название unordered_map, стандартные коллекции C ++ вас ненавидят, поэтому эта расширенная функция не очень удобна.) В настоящее время мы не поддерживаем функции равенства для каждой карты в Toit, но это скоро появится! В Java вам придется заключить ключи в карту или использовать Trove.
Ложка дегтя и как ее удалить
Даже если в вашем языке есть компактные словари, все равно есть крошечная ложка дегтя. При определенных обстоятельствах ваши хеш-карты по-прежнему будут вести себя так, как будто они вас ненавидят, но по-новому! Некоторым людям нравится использовать хэш-карты (и наборы, которые имеют одинаковую реализацию) как своего рода дедуплицирующую рабочую очередь. Вы можете добавлять задачи в набор, и он автоматически игнорирует дубликаты, потому что это набор. Очередь задач (также называемая FIFO) требует операции добавления до конца и операции удаления с начала. Операция добавления в конец у нас уже есть, и ее легко выполнить, посмотрев на начало резервного массива. Если в Toit language еще не было этой функции, вы можете добавить ее следующим образом:
Проблема возникает через некоторое время при использовании такого набора или карты. Ближе к началу подложки будет много надгробий, и внезапно операция удаления с начала будет не такой быстрой. Необходимо пропускать все больше и больше надгробий, и время выполнения вставки и удаления n элементов становится квадратичным. Эту проблему нельзя решить, перестраивая хэш-карту чаще, потому что, если вы сделаете это, вы потеряете свойство амортизированных операций с постоянным временем.
Специальным решением было бы записывать для каждой хэш-карты, где первая запись находится в резервном массиве. Хотя это похоже на пластырь. Что, если пользователи захотят многократно удалить последнюю запись, используя набор как своего рода дедуплицирующий стек (или LIFO)? Вернется ненавистная проблема квадратичной хеш-карты. Что, если они захотят несколько раз удалить вторую запись в наборе? Одна вещь, которую я узнал о V8, заключается в том, что трудно предсказать, что будут делать ваши пользователи с помощью созданной вами реализации языка программирования.
И мы создали Toit для работы на крошечных устройствах. Неужели мы действительно хотим потратить лишнее слово на хеш-карту, чтобы записать количество ведущих надгробий? Решение, которое мы придумали, - это надгробия с указателями расстояния. Каждое надгробие дополнительно записывает расстояние до следующей реальной записи слева или справа. Мы лениво обновляем это при сканировании через подложку, поэтому это не требует затрат времени на другие операции, но позволяет пропускать длинные участки надгробий, где бы они ни появлялись.
В общем случае, когда нет никаких удалений или удаления распределены случайным образом, ничего не меняется, но для проблемных случаев мы сохраняем желаемое свойство амортизированной вставки и удаления с постоянным временем.
Языки тестирования на эту ошибку
Я написал крошечную программу, чтобы проверить, есть ли у языковых реализаций квадратичное замедление при использовании набора в качестве FIFO. Я тестирую только те языки, у которых есть упорядоченный по вставке набор. Для JavaScript я использую новый (иш) Set, а не злоупотребляю обычными объектами в качестве хэш-карт. В Java я использовал LinkedHashMap, у которого совершенно другое внутреннее представление. Я подозреваю, что LinkedHashMap довольно расточителен в использовании памяти (я скоро буду писать об этой проблеме), но это самый быстрый набор упорядоченных вставок, который я тестировал, особенно когда срабатывает адаптивный JIT.
Итак, вот, для вашего удовольствия, график для разных языков. В настоящее время все реализации на основе компактных словарей (кроме Toit) имеют эту проблему. Надеюсь, эта запись в блоге вдохновит разработчиков исправить это.
