Java: Is there a data structure that works like a multimap but accepts duplicate keys?

Question

I'm having a bit of a hard time. Essentially I need a data structure that would work a bit like a database. I need to be able to have multiple bits of data for each key and have the possibility of having multiple keys with the same name. Then I need to be able to search that data structure and pull the correct keyword and check it against other possible data. Here is an example:

Keys   |   Name   |  Price

Airplane | Boeing | 10000
Airplane | LearJet | 4000
Airplane | Airbus | 20000
Car | Honda | 500
Car | Ford | 450
Car | Chevy | 600

So I need to be able to specifically be able to search for Airplanes and Airplanes that are Boeing's. For a lot of reasons I cannot use an actual database, it'd be complete overkill, since I don't have many records, but I do need to be able to pull these values. I found a multimap implementation in Java but it didn't allow me to insert multiple keys with the same name nor did it allow me to do search not only keys but keys with a corresponding value.

Anyone have an idea of how this might be implemented? Thanks

Edit: Okay I looked over all the answers. I for some reason just cannot understand any situation where you need keys to be unique but you are using maps. There are many answers that feature this solution and I take all fault for not being able to understand them. Ultimately I needed to have multiple unique keys and I know these solutions were workaround for that but I just couldn't make sense of it.

While it's far from being a perfect solution, I used Apache's MultiKey Class and since I only need to pull one possible value it works okay. I appreciate everyone's effort unfortunately I just couldn't get it work otherwise. Sorry

Answer 1

In that case, why not just use a java.util.List.

Answer 2

Why not a Set<Entry> where

public class Entry {
   String key;
   List<Item>  items;
}
public class Item {
    String name;
    int  price;
}

Answer 3

You could use Map of Maps.

Answer 4

You need a nested Map. Here's a kickoff example:

Map<String, Map<String, Integer>> vehicles = new HashMap<String, Map<String,Integer>>();
Map<String, Integer> airplanes = new HashMap<String, Integer>();
vehicles.put("Airplane", airplanes);
airplanes.put("Boeing", 10000);
airplanes.put("LearJet", 4000);
airplanes.put("Airbus", 20000);
Map<String, Integer> cars = new HashMap<String, Integer>();
vehicles.put("Car", cars);
cars.put("Honda", 500);
cars.put("Ford", 450);
cars.put("Chevy", 600);

// To get price of Airplane - Airbus, just do:
Integer price = vehicles.get("Airplane").get("Airbus");

Answer 5

Why not use MultiKey from Apache Commons collections

http://commons.apache.org/collections/api-3.1/org/apache/commons/collections/keyvalue/MultiKey.html

// populate map with data mapping key+name to price
Map map = new HashMap();
MultiKey multiKey = new MultiKey(key, name);
map.put(multiKey, price);

// later retireve the price
MultiKey multiKey = new MultiKey(key, name);
<Number> price = (String) map.get(price);

Answer 6

You could certainly do this using Java's Collections, but this is really, really a task for a database.

Have you considered using an embedded databases? They allow you all the luxury of a DBMS without actually requiring one (they're just a library). Look e.g. at SQLite, or HSQLDb.

Answer 7

Why not just use an embedded DB like H2. You can then execute your searches in SQL using some simple wrapper like SimpleJDBCTemplate in Spring. Alternatively you could create an ORM mapping for your objects and use HQL or search by example on your mapped objects.

Answer 8

the element in your hashmap could be an arraylist or another hashmap. that way one key maps to multiple integers. to search you would lookup the first key, then lookup the second key in the result. Check out BalusC's excellent example. Per your comment, dynamic insertion (if it doesn't know when the key was already added) would be something like:

Map<String,Integer> x = m.get("vehicle");
if (x == null) {
  x = new HashMap<String,Integer>();
  m.put("vehicle", x);
}
x.put("mfg", 20000);

a KeyPathMap class could be created that returns a map when you request it (getMap("vehicle")) and returns a value when you request a path that contains one (get({"vehicle", "mfg", "key 3", "key 4", "key 5"})), similar to a filetree.

another way is to make your key contain both strings. the key could be a simple concatenation ("Vehicle:Manufacturer") or a List as below:

List<String> k = Arrays.asList("vehicle", "manufacturer");
map.put(k, 10000);
...
map.get(k);

you could also use a custom key object with 2 fields that hashes based on the concatenation of the 2 (done by overriding hashCode and equals; your object can just delegate to internalString.hashCode and internalString.equals).

[moved from comments]

Answer 9

Another multikey implementation could be found in Google's Collection Framework. Take a look at the javadoc. It is Apache V2 licensed, also.