Использование EnumSet или EnumMap для произвольных ключей

Question

Мы знаем, что EnumSet и EnumMap быстрее, чем HashSet/HashMap из-за мощности манипуляции бит. Но действительно ли мы используем истинную силу EnumSet/EnumMap, когда это действительно имеет значение? Если у нас есть набор миллионов записей, и мы хотим узнать, присутствует ли какой-либо объект в этом наборе или нет, можем ли мы использовать скорость EnumSet?

Я проверил, но ничего не нашел, обсуждая это. Везде обычные вещи найдены, потому что EnumSet и EnumMap использует предопределенный набор ключей для небольших коллекций очень быстро. Я знаю, что перечисления - это константы времени компиляции, но можем ли мы иметь лучшее из обоих миров - структуру данных, похожую на EnumSet, без необходимости перечисления в качестве ключей?

Answer 1

интересное понимание; короткий ответ - нет, но ваш вопрос исследует некоторые хорошие концепции проектирования структуры данных, которые я попытаюсь обсудить.

Во-первых, давайте поговорим о HashMap (HashSet использует внутреннее устройство HashMap, поэтому они делят больше всего поведения); хэш-структура данных является мощной, потому что она быстрая и общая. Это быстро (т. Е. Примерно O(1)), потому что мы можем найти ключ, который мы ищем, с очень небольшим количеством вычислений. Грубо мы имеем массив списков ключей, преобразуем ключ в целочисленный индекс в этот массив, а затем просматриваем связанный список для ключа. По мере того, как сопоставление становится больше, массив поддержки многократно изменяется, чтобы содержать больше списков. Предполагая, что списки распределены равномерно, этот поиск очень быстрый. И поскольку это работает для любого общего объекта (который имеет надлежащие .hashcode() и .equals()), он полезен практически для любого приложения.

В Enums есть несколько интересных свойств, но для эффективного поиска мы заботимся только о двух из них - они обычно малы и имеют фиксированное количество значений. Из-за этого мы можем сделать лучше, чем HashMap; в частности, мы можем сопоставить каждое возможное значение с уникальным целым числом, то есть нам не нужно вычислять хэш, и нам не нужно беспокоиться о столкновении хэшей. Так EnumMap просто хранит массив того же размера, что перечисление и смотрит прямо в него:

// From Java 7's EnumMap 
public V get(Object key) { 
    return (isValidKey(key) ? 
      unmaskNull(vals[((Enum)key).ordinal()]) : null); 
} 

отбрасывая некоторые из необходимых Map здравомыслие проверки, это просто:

return vals[key.ordinal()]; 

Обратите внимание, что это концептуально не отличается от стандарта HashMap, он просто избегает нескольких вычислений. EnumSet является немного более умным, используя биты в одном или более long s для представления индексов массива, но функционально он не отличается от случая EnumMap - мы выделяем достаточно слотов для покрытия всех возможных значений перечисления и можем использовать их целое число .ordinal(), а не вычислять хэш.

Итак, насколько быстрее, чем HashMap является EnumMap? Это явно быстрее, но на самом деле это не , что намного быстрее. HashMap - это уже очень эффективная структура данных, поэтому любая оптимизация на ней даст лишь незначительные результаты. В частности, как HashMap, так и EnumMap асимптотически имеют одинаковую скорость (O(1)), что означает, что они становятся больше, они ведут себя одинаково хорошо.Это основная причина, по которой нет более общей структуры данных, такой как EnumMap, потому что это не стоило бы усилий по сравнению с HashMap.

Вторая причина, по которой мы не хотим более общего «FiniteKeysMap», это сделает наши жизни более сложными пользователями, что было бы целесообразно, если бы это было заметное увеличение скорости, но поскольку это не просто хлопот , Нам нужно было бы определить интерфейс (и, вероятно, также factory pattern) для любого типа, который мог бы быть ключом на этой карте. Интерфейс должен обеспечить гарантию того, что каждый уникальный экземпляр вернет уникальный хэш-код в диапазоне [0-n), а также предоставит возможность для карты получить n и потенциально все элементы n. Эти две последние операции были бы лучше, чем статические методы, но поскольку мы не можем определять статические методы в интерфейсе, их нужно либо передать непосредственно каждой создаваемой карте, либо отдельный заводский объект с этой информацией будет иметь существовать и передаваться на карту/при построении. Поскольку перечисления являются частью языка, они получают все эти преимущества бесплатно, то есть нет таких затрат для программистов конечных пользователей, которым необходимо воспользоваться.

Кроме того, было бы очень легко совершить ошибки с этим интерфейсом; скажем, у вас есть тип, который имеет точно 100,000 уникальных значений. Должен ли он реализовывать наш интерфейс? Это может. Но вы, скорее всего, стреляете в ногу. Это съел бы много ненужной памяти, так как наш FiniteKeysMap выделил бы новый массив длины 100,000 для представления даже пустой карты. Вообще говоря, такое расходомерное пространство не стоит маргинального улучшения, которое обеспечила бы такая структура данных.

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

---

Для конкретного случая быстрее .contains() проверок, вы могли бы Bloom Filters. Это подобная набору структура данных, которая очень эффективно хранит очень большие наборы, при условии, что она иногда может неправильно сказать, что элемент находится в наборе, когда это не так (но не наоборот), если он говорит, что элемент не является в комплекте, это определенно нет). Guava обеспечивает приятную реализацию BloomFilter.