Java: внутренняя структура данных в Map

Question

Я пытаюсь создать класс, который реализует интерфейс Map. Поэтому я пишу код, который проверит, является ли вызывающий объект пустым или нет. Однако меня немного смущает вопрос о том, какую структуру данных мне следует использовать внутри страны. В настоящее время я использую хэш-таблицу. Заранее спасибо

Answer 1

Из Википедия ,

Ассоциативные массивы обычно используются, когда поиск является наиболее частой операцией.По этой причине реализации обычно разрабатываются для обеспечения быстрого поиска за счет более медленной вставки и большего объема памяти, чем другие структуры данных (например, списки ассоциаций).

Эффективные представления:
Существует две основные эффективные структуры данных, используемые для представления ассоциативных массивов: хеш-таблица и самобалансирующееся двоичное дерево поиска (например, красно-черное дерево или дерево AVL).Пропуск списков также является альтернативой, хотя и относительно новым и не так широко используется.B-деревья (и варианты) также могут использоваться и обычно используются, когда ассоциативный массив слишком велик, чтобы полностью находиться в памяти, например в простой базе данных.Относительные преимущества и недостатки включают:

1. Производительность асимптотической операции: хэш-таблицы имеют более быстрое среднее время поиска и вставки, O (1), по сравнению с сбалансированным двоичным деревом поиска log (log n),в то время как сбалансированные деревья имеют наименьшее время поиска и вставки в худшем случае, O (log n) по сравнению с Θ (n).Списки пропусков имеют O (n) наихудшего случая и O (log n) среднего времени работы, но с меньшими накладными расходами на вставку и удаление на практике, чем для сбалансированных двоичных деревьев.

2. Сохранение порядкаСбалансированные двоичные деревья и списки пропусков сохраняют порядок - позволяя эффективно перебирать ключи по порядку или эффективно находить ассоциацию, ключ которой ближе всего к данному значению.Хеш-таблицы не сохраняют порядок и, следовательно, не могут выполнять эти операции так эффективно (они требуют, чтобы данные сортировались на отдельном шаге).

3. Запросы диапазона: сбалансированные двоичные деревья могут быть легко адаптированыэффективно назначать одно значение большому упорядоченному диапазону ключей или подсчитывать количество ключей в упорядоченном диапазоне.(При наличии n элементов в массиве и выполнении операции в непрерывном диапазоне m ключей для сбалансированного двоичного дерева потребуется время O (log (n) + m), в то время как для хэш-таблицы потребуется время Θ (n), так какпоиск по всей таблице.)

4. Поведение размещения: хеш-таблицы с открытой адресацией хранят все данные в большом непрерывном блоке памяти, который редко перераспределяется, тогда как выделение дерева выполняет много небольших, частых распределений,В результате хеш-таблицы могут быть трудно разместить в фрагментированной куче, и наоборот, деревья могут вызвать фрагментацию кучи.Деревья также более уязвимы к неэффективности в распределителях.

5. Компактность: Хеш-таблицы могут иметь более компактное хранилище для небольших типов значений, особенно когда значения являются битами.

6. Постоянство. Существуют простые постоянные версии сбалансированных бинарных деревьев, которые особенно заметны в функциональных языках.

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

Иногда простые реализации одной структуры данных илидругие имеют недостатки, которые можно преодолеть с помощью лучшего дизайна.Например:

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

• Простые сбалансированные деревья тратят пространство на указатели и метаданные распределения;эти проблемы могут бытьiged хранением нескольких элементы в каждом узле и с помощью пулы памяти.

Answer 2

Я пробовал разные методы, но в итоге расширил некоторую структуру данных, которая сама по себе была настолько сильной, что для нее не требовались навыки кодирования. Поэтому я решил использовать обычные строковые массивы (2) для создания виртуальной хеш-карты, подобной структуре, которая будет расширяться при увеличении потребности в пространстве.

Ниже приведена ссылка на полный код.

http://code.google.com/p/rohan-oopconcept-assignment/source/browse/trunk/src/EmployeeMap.java

Answer 3

В дополнение к самой таблице вы также можете поддерживать целочисленную переменную-член для отслеживания размера коллекции, увеличивая ее каждый раз, когда создается новое отображение, и уменьшая ее каждый раз, когда удаляется одна.Таким образом, вы можете упростить методы интерфейса size и isEmpty:

public int size() {
    return this.size;
}

public boolean isEmpty() {
    return this.size == 0;
}