Какую коллекцию использовать в java для хранения нескольких объектов, имеющих один и тот же хэш-код?

Question

Предположим, я хочу хранить записи для каждого класса, на котором студент посещает. У ученика и класса есть уникальные идентификаторы, но несколько учеников могут посещать один и тот же класс, и учащийся может посещать несколько классов.

Я хочу упорядочить эти записи таким образом, что мне не нужно искать все записи со сложностью O (n), но все объекты, имеющие одинаковый идентификатор класса, разрешаются в одном слоте, hashtable works, за исключением того, что я нахожу, что java HashSet не поддерживает дубликаты.

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

Answer 1

Сначала обращается к общей проблеме хэш-кодов.

Хэш-таблицы в общей работе по-прежнему будут работать, если у вас много разных ключей, которые сопоставляются с одним и тем же хэш-кодом. Однако хэш-таблицы являются картами 1 к 1. Они сопоставляют каждый отдельный ключ с одной (и только) записью/записью. В контексте Java это относится ко всем коллекциям Map, а также ко всем сборкам Set ... моделирование набора как вырожденной формы карты.

Если вы хотите, чтобы один ключ отображал (потенциально) несколько разных записей/значений, вам нужна структура данных с несколькими картами. Это можно моделировать (используя типы коллекции Java) в виде Map<K, List<V>> или Map<K, Set<V>>.

Резюмируя:

1. Это отчетливость ключей, которые имеют значение, а не отчетливостью hashcodes. (Хэш-таблица может иметь дело с столкновениями хэш-кодов.)

2. Если у вас есть неявные ключи, вам понадобится мульти-карта.

---

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

Тот факт, что у вас есть два ключа, означает, что вы хотите запросить обе в разных местах приложения; например «найти записи посещаемости для ученика X», «найти все записи посещаемости для класса Y».

Это означает, что вам действительно нужны 2 мульти-карты для поддержки этих запросов; например Map<StudentID, <Set<AttendanceRecord>> и Map<CourseID, <Set<AttendanceRecord>>.

Существует несколько инвариантов, которые вам нужно будет поддерживать. Наборы должны (конечно) содержать только AttendanceRecord объекты, относящиеся к соответствующему ученику или курсу.