Java HashMap поиск

Question

В рамках продолжающегося проекта класса нас попросили внедрить Карты для лучшей привязки объектов.

Короче говоря, в настоящее время у нас есть четыре массива, которые содержат объекты

// Array Lists used for sorting.
private static ArrayList<Party> partyList = new ArrayList<Party>();
private static ArrayList<Creature> creatureList = new ArrayList<Creature>();
private static ArrayList<Treasure> treasureList = new ArrayList<Treasure>();
private static ArrayList<Artifact> artifactList = new ArrayList<Artifact>();

У каждого класса есть свои поля (т. Е. У партии есть «индекс», «имя», у существа «индекс», «имя», «возраст», рост »и т. Д.), Но все они имеют уникальный индекс )

На этой неделе мы должны реализовать хеш-карты, где ключом объекта является его индекс.

Итак, в качестве примера:

creatureMap.put(creature.index, creature)
...

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

Однако наша программа также позволяет пользователю выполнять поиск по имени, росту, весу и т. Д. Итак, как эффективно использовать здесь хэш-карты, если это помогает только при поиске по индексу? Что произойдет, если я захочу найти существо по имени? Мне нужно было бы пройтись по каждому значению в хэш-карте, посмотреть на его поле 'name'. Что именно я делаю с массивом.

Наш профессор сказал это, когда кто-то задал похожий вопрос:

Идея состоит в том, что в первом проекте простой подход заключался в вставьте все элементы в списки массивов и когда нужно связать существо для вечеринки или предмет для существа, ищите ArrayList линейно, пока не будет найден индекс элемента. Это операция O (n), если ArrayList не отсортирован, и O (log n) операция, если список отсортирован, но сортировка обычно O (n * n) или O (n log n) в зависимости от используемой операции сортировки.

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

Таким образом, я не уверен, что правильно понимаю концепцию карт / пар ключ-значение.

Answer 1

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

Я не совсем уверен, что твой профессор имел в виду под этим:

Таким образом, мы должны использовать индекс элемента в качестве его ключа для генерации ссылок.

(я думаю, что он ссылается на связывание объектов по индексу, как в «связать существо с группой» - возможно, он не имел в виду использование хеш-карт для поиска)

Кроме того, рекомендуется объявлять переменные на основе интерфейсов, а не конкретных типов. В вашем примере вы должны определить поля списка как List вместо ArrayList:

private static List<Party> partyList = new ArrayList<Party>();

Answer 2

Выполнение ваших вопросов (и заявлений) по порядку ....

Итак, я понимаю, что теперь, когда мы ищем по индексу, мы просто ищем соответствующая хэш-карта для индекса, который мы хотим, и работать с объект, который является его значением.

Это правильно.

Однако наша программа также позволяет пользователю осуществлять поиск по имени, росту, весу и т. Д. Итак, как эффективно использовать здесь хеш-карты, если это помогает только при поиске по индексу?

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

Что произойдет, если я захочу найти существо по имени? Мне нужно было бы перебрать все значения в хэш-карте, посмотреть на поле «имя» ... что именно я и делаю с массивом.

Да, если вам нужно выполнить поиск по имени, вы должны использовать метод values() и проходить по нему, проверяя каждый элемент.

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

Это наводит меня на мысль, что есть другая часть задания - что-то, что связано с чтением ввода из файла и связыванием сторон, существ и предметов вместе.

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

(Очевидно, это предположение, поскольку я не знаю, что на самом деле говорит это задание)