在 java 中使用什么集合来存储具有相同哈希码的多个对象?

What collection to use in java for storing multiple objects that have the same hashcode?

假设我想存储每个 class 学生参加的记录。学生和 class 都有唯一的标识符,但是多个学生可以参加同一个 class,一个学生可以参加多个 class。

我想以这样的方式排列这些记录,这样我就不必搜索复杂度为 O(n) 的所有记录,但具有相同 class id 的所有对象都以相同的方式解析插槽,很像 hashtable 的工作方式,除了我发现 java HashSet 不支持重复。

所以我的下一个问题是...我想 return 其哈希码已解析到 table 中相同位置的所有记录的集合,但该数据结构必须当然支持重复,因为多个学生可以参加 class x。一个这样的插槽将是解析到同一插槽的所有记录的列表。

首先解决哈希码的一般问题。

Hash tables 在一般工作中仍然有效,如果你有许多不同的键映射到相同的 hashcode。然而,hash tables 是一对一的映射。他们将每个不同的键映射到一个(且唯一的)记录/条目。在 Java 上下文中,这适用于所有 Map 集合,也适用于所有 Set 集合……将集合建模为地图的退化形式。

如果你想要一个键映射到(可能)多个不同的记录/值,那么你需要一个多映射数据结构。这可以模拟(使用 Java 集合类型)作为 Map<K, List<V>>Map<K, Set<V>>.

总结一下:

  1. 重要的是键的独特性,而不是哈希码的独特性。 (哈希 table 可以处理哈希码冲突。)

  2. 如果你有非唯一键那么你需要一个多映射。


查看您的特定用例,您似乎拥有一组具有两个外部密钥的出勤记录;即 class id 和源 id。 (我假设每个出勤记录都包含一些代表 classes 学生出勤的数据。)

您在这里有两个键的事实意味着您希望在应用程序的不同位置通过这两个键进行查询;例如"find attendance records for student X", "find all attendence records for class Y".

这意味着您实际上需要 2 个多地图来支持这些查询;例如Map<StudentID, <Set<AttendanceRecord>>Map<CourseID, <Set<AttendanceRecord>>.

您需要维护几个不变量。这些集合必须(当然)只包含 AttendanceRecord 个属于相应学生或课程的对象。