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

Question

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

Answer 1

От Wikipedia,

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

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

1. Асимптотической эффективность операции: Хэш таблица имеет быстрее средний поиск и вставок времени, O (1), по сравнению с & thetas бинарного дерева (Log п), в то время как сбалансированные деревья имеют более быстрый наихудший поиск и время вставки, O (log n) по сравнению с Θ (n). Пропущенные списки имеют наихудший вариант O (n) и O (log n), но с меньшим количеством вставки и удаления Накладные расходы на практике, чем сбалансированные Бинарные деревья.

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

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

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

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

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

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

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

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

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

Answer 2

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

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

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

Answer 3

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

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

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