JDK-4155149 : (coll) Need a Map class to support one-to-many relationship
  • Type: Enhancement
  • Component: core-libs
  • Sub-Component: java.util:collections
  • Affected Version: 1.2.0
  • Priority: P5
  • Status: Resolved
  • Resolution: Won't Fix
  • OS: generic,windows_95
  • CPU: generic,x86
  • Submitted: 1998-07-07
  • Updated: 2014-07-22
  • Resolved: 2014-07-22
Related Reports
Duplicate :  
JDK-4189329 - Add a MultiMap interface
Description

Name: rm29839			Date: 07/07/98


I would like to move over to the JDK 1.2 collection
classes from JGL, but there doesn't seem to be a way
to easily implement a Map in which there can be
duplicate keys (i.e., more than one value associated
with a key).

In addition to "put(Object key, Object value)"
there needs to be a "add(Object key, Object value)"
which will add a new Key/Value pair without
replacing a previous occurrance of the Key.
"put" would be redefined to replace only the
first instance of the key, if any.

Likewise an "addAll(Map map)" needs to be defined
that is analogous to "putAll(Map map)".

Then you need to add "Collection getAll(Object key)"
that will return all values associated with key. (Or else
have it return an Iterator instance).

Implementation-wise, this is not difficult.
Merely have the duplicate keys be consecutive
in the hash buckets, then it is easy to form
a Collection of values for a single key.

If you choose not to add this functionality, do
you have any ideas on how to efficiently
implement a one-to-many Map with the current
facilities? I've considered defining a HashMap of
Set objects, but this is not very acceptable if
most of the keys have just one value.
(Review ID: 34548)
======================================================================
Comments
With the addition of Map.computeIfAbsent() this is even less necessary.
22-07-2014
EVALUATION This functionality was intentionally omitted from the initial (JDK1.2) release of the Collections framework, as the need for multimaps (and multisets) was thought to be relatively rare. If we receive many requests for this functionality, we can add it in the future. One difficulty is that it's not clear where to draw the line: do we also need to add sortedMultiMap and sortedMultiSet? In the meantime, the customer can implement this functionality on top of HashMap without too much difficulty. To avoid the inefficiency in the author's suggested implementation, I'd have the (private) backing HashMap Map the key directly to the value if there was only a single value associated with the key. The first time that a second value was associated with the key, I'd associate the key with a package private (inner) Set class, containing all of the associated values. Because this Set class was private there would be no ambiguity: if a value mapped to an instance of this class, the MultiMap class would *know* that the actual values were the elements of the Set. joshua.bloch@Eng 1998-07-21
21-07-1998