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?

Solution 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).

Solution 2

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

Solution 3

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.

Solution 4

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.

Solution 5

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

The Google Collections (update: Guava) 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.

View more solutions

Comments

[Josh]

Awseome 6 people all basically copying and pasting the same answer. sigh

[palantus]

Awesome, 6 people independently came up with the same answer. Yay!

[Brett]

I bet it's a dupe question if anyone could be bothered to look rather than just banging in an obvious post.

[palantus]

I did look, but I didn't see any obvious duplicates. Does anyone else want to try?

[Jonik]

I searched too; didn't find. I'd say if a duplicate exists, it is named/tagged in some pretty obscure way

[Steve Kuo]

Related question stackoverflow.com/questions/1010879

[Jonik]

Strangely, now there exists an exact duplicate: stackoverflow.com/questions/1052120/dictionary-class. Also posted by someone called Raji, but as different unregistered user, some 12 hours after this.

[mnuzzo]

Yes you can store a list, but you can't just add an item to it, you'd have to get a reference to the list, then add it to the list.

[akarnokd]

Just a small remark: HashMap is not synchronized by default so why use Vector in it instead of a List implementation?

[akarnokd]

Could you please post at least a small sample code for the usage?

[matt b]

Interesting that it seems like Multimap basically just does Map<YourKeyObject, List<YourValueObject>> under the covers

[palantus]

Yes, it's basically just abstracting away the umimportant details.

[bendin]

after reading through other people's answers, I'm forced to conclude that my advocacy for the google collections api wasn't very original. (It's a good piece of work, no?)

[palantus]

Well, the original question was about HashTables, not HashMaps.

[Josh]

I linked to commons-collections just to be different :-P (Actually it was the first search hit and I was feeling lazy).

[palantus]

+1 for looking at the big picture. I keep forgetting to do that.

[palantus]

I prefer Google Collections because Apache Commons doesn't support generics.

[Jonik]

For more about Google Collections vs. Apache Commons Collections, see javalobby.org/articles/google-collections (search for "Apache Commons")

[Jonik]

Yes, that's why it's curious that this answer uses HashMap & Vector (instead of Hashtable & Vector or HashMap & ArrayList, etc.) IMO, pedagogically it would be best to use Map & List. :)

[Jonik]

+1, not for originality, but the clarity and thoroughness of the examples :)

[Jonik]

With no external libs, this is the way to go. But this is exactly the boilerplate I mentioned in my answer; using Google Collections, addition would be one line, simply: multiMap.put(key, o)