10

in the project I am currently working on we had three different types of prices depending on the age of the user (adult, child, etc...). So we had on the DB a table looking like this:

PRICES
type     Amount
A         20
B         15
C         ..
D         ..

At first we only had 4 different types of prices, so in the code, we had something like this:

Map<String, BigDecimal> prices = new HashMap<String, BigDecimal>();

Where the keys were the price type.

Recently, they added a new business rule that adds 3 subtypes to every price type, so now we have something like this:

PRICES
type   subtype  Amount
A          1      20
A          2      15
A          3      ..
B          1      ..
B          2      ..
...        ..     ..

Which of the following two options do you think is better and why?

Nested Maps

Map<String, Map<String, BigDecimal>> prices;

where the keys are the price type and subtype:

prices.get(type).get(subtype);

Combined Keys

The same map than originally:

Map<String, BigDecimal> prices;

And concatenate the keys to index the different prices:

prices.get(type+"_"+subtype);
2
  • This is more of a design question, and there is insufficient code for Code Review. Jul 16 '14 at 17:28
  • A small note: your proposed combined key can lead to problems down the road, e.g. needing a '_' in one price type. Consider instead having a class PriceKey{ PriceType type; PriceSubtype subtype; } key. This can then be easily further extended
    – Caleth
    Sep 28 '16 at 9:43
11

Both nested and combined keys have their places. bowmore gives a pro argument for composite keys, and a con argument for nested maps. Let me provide the loyal opposition:

Composite map keys work great when you're looking up a specific known item.

Nested maps work well when you need to rapidly find all the variations, kinds, and subtypes of type A. For example, choosing A (vs. B, C, ...) might be the first step in a decision tree. Once the user or algorithm or whatever picks A, then you need to know only about A's subtypes, and B..Z or B..ZZZZZ no longer matter.

Now you're dealing with a very tight and efficient lookup structure for the subsearch. If you try to do that with composite keys, you end up doing a full table scan a la [ (key, value) for (key, value) in prices.items() if key.startswith('A') ]. That's not an efficient operation, and will be slow if the map is at all large.

Nested maps also work well when the number of nesting levels may grow. The problem structure already extended from type to (type, subtype). Is there any chance the next rev will need (type, subtype, variation) or (type, subtype, version)? If so, a nested mapping approach can be cleanly extended. This, however, is a stylistic, second-order advantage, especially compared to the "easy subsearch" advantage above.

7
  • truth be told, incremental search for composite keys can avoid a 'table scan' by using a SortedMap.
    – bowmore
    Jul 18 '14 at 10:37
  • 1
    You can improve search characteristics for composite keys by sorting the map. But you cannot avoid all scanning that way. Finding key "RXR_1_a" in a table or sorted mapping of 10,000 keys, say, still requires finding the table index where "RXR_*" begins and ends. Even with binary search, this is not zero time. It also requires the same key.startswith('RXR') tests I mentioned. Nested maps are always O(1) operations, and do not require the overhead of pre-sorting the map, or string comparisons. Jul 20 '14 at 22:12
  • That is right, I just said you could avoid a 'table scan' style operation. In my answer I also point out that for this kind of search it is easier to query the DB directly. Both approaches will have trouble with a search for a partial key that does not start at the first field, and a DB can alleviate this with additional indices.
    – bowmore
    Jul 21 '14 at 7:07
  • A SortedMap can avoid a full linear search, but not a high-cost search. I don't see how pawning the operation off on a database helps; that may simplify client code, perhaps, but at the cost of slow external requests and extra data structures (the indices needed to make the operation even reasonably efficient). A nested structure has some drawbacks, sure, but it's self-contained and highly efficient, either with or without backup database support. Jul 21 '14 at 20:34
  • How is a binary search is a high cost search?
    – bowmore
    Jul 22 '14 at 4:17
6

Avoid nested Maps. They're harder to scale and lead to code that is very verbose and hard to read with all the nested generics declarations going on.

More importantly, Maps in Java tend to consume a lot of memory. Populating a Map with even more Maps will only aggravate the memory consumption issue.

Lastly, a Map that uses composite keys is easier to reason about.

Using composite keys will make your life easier in the most typical cases, yet some things will be harder. Getting all prices for a specific key component for instance, but you're more likely to query that result straight from the database rather than distilling it from the Map.

1
  • I agree with your statement, however sometimes nested maps are unavoidable, and in that scenario I have not found a good way to manipulate them in Java. Whenever we need to read/manipulate something generic in Java, particularely JSON files, you'd need nested maps, unless you want to hard code the structure of your file in your application. Feb 15 '16 at 9:17
1

This is less to do with "what implementation is best" and more to do with "what abstraction should I be working with".

Both the composite key and the map of maps have their strengths and their weaknesses, all of which reside within the domain of performance (ie, speed/memory usage). They do not differ in their functionality: They both take two values and return the previously "put" value.

As they are functionally equivalent, the first thing you should do is to abstract over them. Don't worry about which one is better. Create a DoubleKeyedMap interface with all the methods you need on it and use that in your code. Then write whatever implementation you can write the fastest and just move on.

ONLY once you have written your application and you have found that your composite key implementation does not filter on the first key very fast, or that the map of maps is taking too much memory should you go and optimise.

Premature optimisation is the root of all evil. Not abstracting is worse.

1
  • Well said. Not abstracting is worse! I love that Apr 22 '19 at 22:38
0

Both options are not good in my opinion. Say what if the business logic changes again so that you have another subtype?

What I suggest you do is the following:

  1. Use a surrogate key for a table call Type this table would look like Type(INT auto_inc id, VARCHAR(255) name, VARCHAR(255) desc, INT status, etc)
  2. In your Price table use foreign key to the Type table above so it would look like Price(INT type_id, INT price)
  3. Make sure you do NOT support deleting a type. You simply mark a type as inactive because of the dangling references would make deletion a real headache

Now, user and business logic can add whatever type subtype combination into the schema. What they would need to do is simply creating new row in the Type table and changing name and/or desc in the old table.

In your case, user would rename type A to type A_1, add a new type called A_2 and set new price for A_2 as 15

Not the answer you're looking for? Browse other questions tagged or ask your own question.