Skip to content

Хэш-карты на других языках

Прежде чем мы поговорим о том, как Go реализует хэш-карту, рассмотрим, как два популярных языка реализуют хэш-карту. Эти языки выбраны, потому что оба предлагают один тип карты, который работает с различными ключами и значениями.

С++

Первый язык, который мы обсудим — это C++. Стандартная библиотека template C++ (STL) предоставляет std::unordered_map то, что обычно реализуется в виде хэш-карты.

Это декларация для std::unordered_map. Это шаблон, поэтому фактические значения параметров зависят от того, как создается экземпляр шаблона.

Здесь много всего, но главное, что нужно понять;

  • Шаблон принимает тип ключа и значения в качестве параметров, поэтому он знает их размер.

  • Шаблон принимает std::hash функцию, специализирующуюся на типе ключа, поэтому он знает, как хэшировать переданный ему ключ.

  • И шаблон принимает std::equal_to функцию, также специализирующуюся на типе ключа, поэтому он знает, как сравнивать два ключа.

Теперь, когда мы знаем, как четыре свойства хэш-карты передаются компилятору в C++ std::unordered_map, давай посмотрим, как они работают на практике.

Сначала берем ключ, передаем его функции std::hash для получения хеш-значения ключа. Мы маскируем и индексируем массив корзины (buckets — можно называть бакетс), затем просматриваем записи в этом бакете, сравнивая ключи с помощью функции std::equal_to.

Java

Второй язык, который мы обсудим — Java. Неудивительно, что в java тип hashmap называется java.util.Hashmap.

В Java java.util.Hashmap тип может работать только с объектами, и это нормально, потому что в Java почти все является подклассом java.lang.Object. Поскольку каждый объект в Java происходит от java.lang.Object, эти объекты наследуют или переопределяют методы hashCode и equals.

Однако мы не можем напрямую хранить восемь типов примитивов: boolean, int, short, long, byte, char, float, и double — поскольку они не являются подклассами java.lang.Object. Мы не можем использовать их как ключ и хранить их как значение. Чтобы обойти ограничение, эти типы автоматически преобразуются в объекты, представляющие их примитивные значения. Эта часть известна как боксинг__, так же как и контейнеры в слайсах_._

Отложим пока это ограничени и посмотрим, как будет работать поиск в хэш-карте Java.

Сначала мы берем ключ и вызываем его метод hashCode для получения хеш-значения ключа. Мы маскируем и индексируем массив бакета. Этот бакет в Java является указателем на Entry, который содержит ключ и значение, а также  указателем на следующее Entry в бакете, формирующим связанный список записей.

Tradeoffs (компромиссы)

Теперь, когда мы увидели, как C++ и Java реализуют Hashmap, давай сравним их относительные преимущества и недостатки.

C++templated std::unordered_map

Преимущества

  • Размер типов ключей и значений известен во время компиляции.

  • Структура данных всегда имеет правильный размер, нет необходимости в боксе или косвенности.

  • Поскольку код специализируется во время компиляции, в игру могут вступить другие оптимизации времени компиляции, такие как встраивание, свертывание констант и устранение мертвого кода.

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

Недостатки:

  • Раздувание кода. Каждая отдельная карта — это разные типы. Для N типов карт в исходном коде у тебя будет N копий кода карты в двоичном коде.

  • Раздувание времени компиляции. Из-за того, как работают заголовочные файлы и шаблоны, каждый файл, в котором упоминается исходный код std::unordered_map для этой реализации, должен быть сгенерирован, скомпилирован и оптимизирован.

Java с использованием Hashmap

Преимущества:

  • Одна реализация карты, которая работает для любого подкласса java.util.Object. Компилируется только одна копия java.util.HashMap, и на нее ссылается каждый отдельный класс.

Недостатки:

  • Все должно быть объектом, даже то, что им не является. Это означает, что карты примитивных значений должны быть преобразованы в объекты через упаковку в контейнер. Это добавляет нагрузку gc (garbage collector) для объектов-оболочек и нагрузку на кэш из-за дополнительных косвенных указателей. Каждый объект эффективен для другого поиска указателя.

  • Сегменты хранятся в виде связанных списков, а не последовательных массивов. Это приводит к большому количеству перебора указателей при сравнении объектов.

  • Хэш-функции и функции равенства оставлены автору hash map в качестве упражнения. Неверные хэш-функции и функции равенства могут замедлить карты, использующие эти типы, или, что еще хуже, не реализовать поведение карты.