Multi-valued hashtable in Java

Question

Is it possible to have multiple values for the same key in a hash table? If not, can you suggest any such class or interface which could be used?

Answer 1

No. That's kind of the idea of hash tables.

However, you could either roll your own with a Map<YourKeyObject, List<YourValueObject>> and some utility methods for creating the list if it's not present, or use something like the Multimap from Google Collections.

Example:

String key = "hello";
Multimap<String, Integer> myMap = HashMultimap.create();
myMap.put(key, 1);
myMap.put(key, 5000);
System.out.println(myMap.get(key)); // prints either "[1, 5000]" or "[5000, 1]"
myMap = ArrayListMultimap.create();
myMap.put(key, 1);
myMap.put(key, 5000);
System.out.println(myMap.get(key)); // always prints "[1, 5000]"

Note that Multimap is not an exact equivalent of the home-baked solution; Hashtable synchronizes all its methods, while Multimap makes no such guarantee. This means that using a Multimap may cause you problems if you are using it on multiple threads. If your map is used only on one thread, it will make no difference (and you should have been using HashMap instead of Hashtable anyway).

Answer 2

Values of a hash table is Object so you can store a List

Answer 3

You need to use something called a MultiMap. This is not strictly a Map however, it's a different API. It's roughly the same as a Map<K, List<V>>, but you wont have methods like entrySet() or values().

Answer 4

Simple. Instead of Hashtable<Key, Value>, use Hashtable<Key, Vector<Value>>.

Answer 5

See the Google Collections Library for multimaps and similar such collections. The built-in collections don't have direct support for this.

Answer 6

As others pointed out, no. Instead, consider using a Multimap which can map many values for the same key.

The Google Collections library contains one implementation, and is probably your best bet.

Edit: of course you can do as Eric suggests, and store a Collection as a value in your Hashtable (or Map, more generally), but that means writing unnecessary boilerplate code yourself. When using a library like Google Collections, it would take care of the low-level "plumbing" for you. Check out this nice example of how your code would be simplified by using Multimap instead of vanilla Java Collections classes.

Answer 7

Rather than give yet another multipmap answer, I'll ask why you want to do this?

Are the multiple values related? If yes, then it's probably better that you create a data structure to hold them. If no, then perhaps it's more appropriate to use separate maps.

Are you keeping them together so that you can iterate them based on the key? You might want to look for an alternative indexing data structure, like a SkipList.

Answer 8

What you're looking for is a Multimap. The google collections api provides a nice implementation of this and much else that's worth learning to use. Highly recommended!

Answer 9

None of the answers indicated what I would do first off.

The biggest jump I ever made in my OO abilities was when I decided to ALWAYS make another class when it seemed like it might be even slightly useful--and this is one of the things I've learned from following that pattern.

Nearly all the time, I find there is a relationship between the objects I'm trying to place into a hash table. More often than not, there is room for a class--even a method or two.

In fact, I often find that I don't even want a HashMap type structure--a simple HashSet does fine.

The item you are storing as the primary key can become the identity of a new object--so you might create equals and hash methods that reference only that one object (eclipse can make your equals and hash methods for you easily). that way the new object will save, sort & retrieve exactly as your original one did, then use properties to store the rest of the items.

Most of the time when I do that, I find there are a few methods that go there as well and before I know it I have a full-fledged object that should have been there all along but I never recognized, and a bunch of garbage factors out of my code.

In order to make it more of a "Baby step", I often create the new class contained in my original class--sometimes I even contain the class within a method if it makes sense to scope it that way--then I move it around as it becomes more clear that it should be a first-class class.

Answer 10

In a hashtable, one would use a key/value pair to store information.

In Java, the Hashtable class accepts a single value for a single key. The following is an example of an attempt to associate multiple values to a single key:

Hashtable<String, String> ht = new Hashtable<String, String>();

ht.put("Answer", "42");
ht.put("Hello", "World");    // First value association for "Hello" key.
ht.put("Hello", "Mom");      // Second value association for "Hello" key.

for (Map.Entry<String, String> e : ht.entrySet()) {
  System.out.println(e);
}

In an attempt to include multiple values ("World", "Mom") to a single key ("Hello"), we end up with the following result for printing the entries in the Hashtable:

Answer=42
Hello=Mom

The key/value pair of "Hello" and "World" is not in the Hashtable -- only the second "Hello" and "Mom" entry is in the Hashtable. This shows that one cannot have multiple values associate with a single key in a Hashtable.

---

What is really needed here is a multimap, which allows an association of multiple values to a single key.

One implementation of the multimap is Multimap from Google Collections:

Multimap<String, String> mm = HashMultimap.create();

mm.put("Answer", "42");
mm.put("Hello", "World");
mm.put("Hello", "Mom");

for (Map.Entry<String, String> e : mm.entries()) {
  System.out.println(e);
}

This is similar to the example above which used Hashtable, but the behavior is quite different -- a Multimap allows the association of multiple values to a single key. The result of executing the above code is as follows:

Answer=42
Hello=Mom
Hello=World

As can be seen, for the "Hello" key, the values of "Mom" and "World" associated with it. Unlike Hashtable, it does not discard one of the values and replace it with another. The Multimap is able to hold on to multiple values for each key.

Answer 11

Just make your own:

Map<Object, List<Object>> multiMap = new HashMap<Object, List<Object>>();

To add:

  public void add(String key, Object o) {
    List<Object> list;
    if (multiMap.containsKey(key)) {
      list = multiMap.get(key);
      list.add(o);
    } else {
      list = new ArrayList<Object>();
      list.add(o);
      multiMap.put(key, list);
    }
  }

Answer 12

Apart from the Google Collections there is a apache Commons Collection object for MultiMap