How to communicate that insertion order matters in a map?

Question

I'm fetching a set of tuples from the database, and putting it into a map. The database query is costly.

There is no obvious natural ordering of the elements in the map, but insertion order matters nonetheless. Sorting the map would be a heavy operation, so I want to avoid doing that, given that the query result is already sorted the way I want it. Therefore, I just store the query result into a LinkedHashMap, and return the map from a DAO method:

public LinkedHashMap<Key, Value> fetchData()

I have a method processData that should do some processing on the map - modifying some values, adding some new key/values. It is defined as

public void processData(LinkedHashMap<Key, Value> data) {...}

However, several linters (Sonar etc) complain that The type of 'data' should be an interface such as 'Map' rather than the implementation "LinkedHashMap" (squid S1319).
So basically it is saying that I should have

public void processData(Map<Key, Value> data) {...}

But I want the method signature to say that map order matters - it matters to the algorithm in processData - so that my method is not passed just any random map.

I don't want to use SortedMap, because it (from the javadoc of java.util.SortedMap) "is ordered according to the natural ordering of its keys, or by a Comparator typically provided at sorted map creation time."

My keys don't have a natural ordering, and creating a Comparator to do nothing seems verbose.

And I would still want it to be a map, to take advantage of put to avoid duplicate keys etc. If not, data could have been a List<Map.Entry<Key, Value>>.

So how do I say that my method wants a map that is already sorted? Sadly, there is no java.util.LinkedMap interface, or I would have used that.

Answer 1

So use LinkedHashMap.

Yes, you should use Map over a specific implementation whenever possible, and yes, this is best practice.

That said, this is an oddly specific situation where the implementation of Map actually matters. This won't be true for 99.9% of cases in your code when you use Map, and yet here you are, in this 0.1% situation. Sonar can't know this and so Sonar simply tells you to avoid using the specific implementation because it would be correct in most cases.

I would argue that if you can make a case for using a specific implementation, don't try to put lipstick on a pig. You need a LinkedHashMap, not a Map.

This said, if you are new to programming and stumble upon this answer, don't think this allows you to go against best practice because it doesn't. But when replacing one implementation for another isn't acceptable, the only thing you can do is use that specific implementation, and be damned to Sonar.

Answer 2

You're fighting three things:

First is Java's container library. Nothing in its taxonomy gives you a way to determine whether or not the class iterates in a predictable order. There's no IteratesInInsertedOrderMap interface that could be implemented by LinkedHashMap, which renders type checking (and the use of alternate implementations that behave the same way) impossible. That's probably by design, because the spirit of it is that you're really supposed to be able to deal with objects that behave like the abstract Map.

Second is a belief that what your linter says must be treated as gospel and that ignoring anything it says is bad. Contrary to what passes for good practice these days, linter warnings aren't supposed to be barriers to calling your code good. They're prompts to reason about the code you've written and use your experience and judgment to determine whether or not the warning is justified. Unjustified warnings are why almost every static analysis tool provides a mechanism to tell it that you've examined the code, you think what you're doing is okay and that they shouldn't complain about it in the future.

Third, and this is probably the meat of it, LinkedHashMap may be the wrong tool for the job. Maps are intended for random, not ordered access. If processData() simply iterates over the records in order and doesn't need to find other records by key, you're forcing a specific implementation of Map to do the job of a List. On the other hand, if you do require both, LinkedHashMap is the right tool because it's known to do what you want and you're more than justified in requiring it.

Answer 3

If all you're getting from LinkedHashMap is the ability to overwrite duplicates, but you're really using it as a List, then I'd suggest it's better to communicate that usage with your own custom List implementation. You can base it on an existing Java collections class and simply override any add and remove methods to update your backing store and keep track of the key to ensure uniqueness. Giving this a distinctive name like ProcessingList will make it clear that arguments presented to your processData method need to be handled in a particular way.

Answer 4

I'm hearing you say "I have one part of my system that produces a LinkedHashMap, and in another part of my system I need to accept only LinkedHashMap objects that were produced by the first part, since ones produced by some other process won't work correctly."

That makes me think that the problem here is actually that you're trying to use LinkedHashMap since it mostly fits the data you're looking for, but in fact it can't be substituted for with any other instance than the ones you create. What you actually want to do is create your own interface/class which is what your first part creates and your second part consumes. It can wrap the "real" LinkedHashMap, and provide a Map getter or implement the Map interface.

This is a bit different from CandiedOrange's answer, in that I would recommend encapsulating the real Map (and delegating calls to it as needed) rather than extending it. It's sometimes one of those style holy wars, but it sure sounds to me that it's not "A Map with some additional stuff", it's "My bag of useful state information, which I may internally represent with a Map".

If you had two variables that you'd needed to pass around like this, you'd probably have made a class for it without thinking much about it. But sometimes it's useful to have a class even if it's just one member variable, just because it's logically the same thing, not a "value" but "the result of my operation that I need to do things with later".

Answer 5

LinkedHashMap is the only java map that has the insertion order feature that you're looking for. So discarding the Dependency Inversion Principle is tempting and maybe even practical. First though, consider what it would take to follow it. Here's what SOLID would ask you to do.

Note: replace the name Ramdal with a descriptive name that communicates that the consumer of this interface is the owner of this interface. Which makes it the authority that decides if insertion order is important. If you just call this InsertionOrderMap you've really missed the point.

public interface Ramdal {
    //ISP asks for just the methods that processData() actually uses.
    ...
}

public class RamdalLinkedHashMap extends LinkedHashMap implements Ramdal{} 

Ramdal<Key, Value> ramdal = new RamdalLinkedHashMap<>();

ramdal.put(key1, value1);
ramdal.put(key2, value2);

processData(ramdal);

Is this a big design up front? Maybe, depends on how likely you think it is that you'll ever need an implementation besides LinkedHashMap. But if you're not following DIP only because it would be a huge pain, I don't think the boiler plate is any more painful than this. This is the pattern I use when I wish untouchable code implemented an interface that it doesn't. The most painful part really is thinking of good names.

Answer 6

Thanks for lots of good suggestion and food for thought.

I ended up extending creating a new map class, making processData an instance method:

class DataMap extends LinkedHashMap<Key, Value> {

   processData();

}

Then I refactored the DAO method so that it does not return a map, but instead takes a target map as parameter:

public void fetchData(Map<Key, Value> target) {
  ...
  // for each result row
  target.put(key, value);
}

So populating a DataMap and processing the data is now a two-step process, which is fine, since there are some other variables that is part of the algorithm, which comes from other places.

public DataMap fetchDataMap() {
  var dataMap = new DataMap();
  dao.fetchData(dataMap);
  return dataMap;
}

This allows my Map implementation to control how entries are inserted into it, and hides away the ordering requirement - it is now an implementation detail of DataMap.

Answer 7

If you want to communicate that the data structure you used is there for a reason, add a comment above the method's signature. If another developer in the future comes across this line of code and notices a tool warning, they might notice the comment as well and refrain from "fixing" the issue. If there is no comment, then nothing will stop them from changing the signature.

Suppressing warnings is inferior than commenting in my opinion, because the suppression itself doesn't state the reason why the warning was suppressed. A combination of warning suppression and comment will be fine as well.

Answer 8

So, let me try to understand your context here:

... insertion order matters ... Sorting the map would be a heavy operation...

... query result is already sorted the way I want it

Now, what you're currently already doing:

I'm fetching a set of tuples from the database, and putting it into a map...

And here's your current code:

public void processData(LinkedHashMap<Key, Value> data) {...}

My suggestion is to do the following:

• Use dependency injection and inject some MyTupleRepository into the processing method (MyTupleRepository is an interface implemented by objects that retrieve your tuple objects, usually from DB);
• internally to the processing method, put data from the repository (aka DB, which already returns ordered data) in the specific LinkedHashMap collection, because this is internal detail of the processing algorithm (because it depends on how the data is arranged in the data structure);
• Note that, this is pretty much what you're already doing, but in this case this would be done within the processing method. Your repository is instantiated somewhere else (you already have a class that returns data, this is the repository in this example)

Code Example

public interface MyTupleRepository {
    Collection<MyTuple> GetAll();
}

//Concrete implementation of data access object, that retrieves 
//your tuples from DB; this data is already ordered by the query
public class DbMyTupleRepository implements MyTupleRepository { }

//Injects some abstraction of repository into the processing method,
//but make it clear that some exception might be thrown if data is not
//arranged in some specific way you need
public void processData(MyTupleRepository tupleRepo) throws DataNotOrderedException {
    
    LinkedHashMap<Key, Value> data = new LinkedHashMap<Key, Value>();
    
    //Represents the query to DB, that already returns ordered data
    Collection<MyTuple> myTuples = tupleRepo.GetAll();
    
    //Optional: this would throw some exception if data is not ordered 
    Validate(myTuples);
    
    for (MyTupleData t : myTuples) {
        data.put(t.key, t.value);
    }
    
    //Perform the processing using LinkedHashMap...
    ...
}

I guess this would get rid of the Sonar warning, and also specify in the signature specific layout of data required by the processing method.

Answer 9

This question is actually a bunch of issues with your data model rolled up into one. You need to start untangling them, one at a time. More natural, intuitive solutions will drop out as you try to simplify each piece of the puzzle.

Problem 1: You can't depend on DB Order

Your descriptions of sorting your data is not clear.

• The biggest potential problem is that you're not specifying an explicit sort in your database, via an ORDER BY clause. If you're not because it seems too expensive, your program has a bug. Databases are allowed to return results in any order if you don't specify one; you can't depend on it coincidentally returning data in the order just because you ran the query a few times and it looks that way. The order might change because rows get rearranged on disk, or some are deleted and new ones take their place, or an index is added. You must specify an ORDER BY clause of some kind. Speed is worthless without correctness.
• It's also not clear what you mean by insertion order mattering. If you're talking about the database itself, you must have a column that actually tracks this, and it must be included in your ORDER BY clause. Otherwise, you have bugs. If such a column doesn't exist yet, then you need to add one. Typical options for columns like this would be an insertion timestamp column or an auto-incrementing key. The auto-incrementing key is more reliable.

Problem 2: Making in memory sort efficient

Once you make sure it's guaranteed to be returning data in the order you expect, you can leverage this fact to make in memory sorts much more efficient. Just add a row_number() or dense_rank() column (or your database's equivalent) to your query's result set. Now each row has an index that will give you a direct indication of what the order is supposed to be, and you can sort by this in memory trivially. Just make sure you give the index a meaningful name (like sortedBySomethingIndex).

Viola. Now you don't have to depend on the database result set order anymore.

Problem 3: Do you even need to do this processing in code?

SQL is actually really powerful. It's an amazing declarative language that lets you do a lot of transformations and aggregations on your data. Most DBs even support cross row operations nowadays. They're called window or analytic functions:

• PostgreSQL Window Functions
• SQL Server OVER clause for window functions
• Oracle Analytic Functions
• MySQL Window Functions

Do you even need to pull your data into memory like this? Or could you do all the work in the SQL query by using window functions? If you can do all (or maybe even just a significant part) of the work in the DB, fantastic! Your code problem goes away (or gets a lot simpler)!

Problem 4: You're doing what to that data?

Assuming you can't do it all in the DB, let me get this straight. You're taking the data as map (which is keyed by things you don't want to sort by), then you're iterating over it in insertion order, and modifying the map in place by replacing the value of some keys and adding new ones?

I'm sorry, but what the heck?

Callers should not have to worry about all this. The system you've created is extremely fragile. It only takes one dumb mistake (maybe even made by yourself, like we have all done) to make one little wrong change and the whole thing collapses like a deck of cards.

Here's maybe a better idea:

• Have your function accept a List.
• There are a couple ways you can handle the ordering problem.
  1. Apply Fail Fast. Throw an error if the list in not in the order the function requires. (Note: You can use the sort index from Problem 2 to tell if it is.)
  2. Create a sorted copy yourself (again using the index from problem 2).
  3. Figure out a way to build up the map itself in order.
• Construct the map you need internally to the function, so the caller doesn't have to care about it.
• Now iterate over whatever in order representation you have and do what you have to.
• Return the map, or transform it into an appropriate return value

A possible variation could be to construct a sorted representation and then create a map of key to index. This would let you modify your sorted copy in place, without accidentally creating duplicates.

Or maybe this makes more sense: get rid of the data parameter and make processData actually fetch its own data. You can then document that you're doing this because it has very specific requirements on the way in which the data is fetched. In other words, make the function own the entire process, not just one piece of it; the inter-dependencies are too strong to split the logic into smaller chunks. (Change the name of the function in the process.)

Maybe these won't work for your situation. I don't know without full details of the problem. But I do know a fragile and confusing design when I hear one.

Summary

I think the problem here is ultimately that the devil is in the details. When I start running into trouble like this, it's usually because I have an inappropriate representation of my data for the problem I'm trying to actually solve. The best solution is find a better representation, and then my problem becomes simple (maybe not easy, but straightforward) to solve.

Find someone who gets that point: your job is to reduce your problem to a set of simple, straightforward ones. Then you can build robust, intuitive code. Talk to them. Good code and good design make you think that any idiot could have thought them up, because they're simple and straightforward. Maybe there's a senior developer who has that mindset you can talk to.