24

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.

56

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.

  • 1
    Pragmatic approach, which I like. – Vidar S. Ramdal Oct 31 '17 at 13:35
  • 20
    I agree almost completely with the answer. I would just say that you are not damned to Sonar. You can always configure it to ignore that particular error/warning. See stackoverflow.com/questions/10971968/… – Vladimir Stokic Oct 31 '17 at 13:36
  • 11
    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. -- Good advice, if there were such a thing as "best practice." Better advice: learn how to make the right decisions. Follow the practice if it makes sense, but let tools and authorities guide your thinking process, not dictate it. – Robert Harvey Oct 31 '17 at 14:55
  • 13
    Note : when sonar report you something, you can close it as "won't be resolve" and leave a note as why you won't. As such not only sonar will stop to bother you, but you wil have a tracer of why you did that. – Walfrat Oct 31 '17 at 15:44
  • 2
    I think the aspect that makes this an exception to the general principle is that LinkedHashMap has a contract which is specific to that implementation and not expressed in any interface. This is not the usual case. So the only way to express the reliance on that contract is to use the implementation type. – Dana Nov 2 '17 at 20:31
21

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.

  • 2
    "LinkedHashMap may be the wrong tool for the job". Yes, maybe. When I say I need an OrderedMap, I could just as well say UniqueList. As long as it is some kind of collection with a defined iteration order, that overwrites duplicates on insert. – Vidar S. Ramdal Oct 31 '17 at 13:47
  • 2
    @VidarS.Ramdal The database query would be the ideal place to weed out the duplicates. If your database can't do that, you could always keep a temporary Set of just the keys while you're building the list a as a way to spot them. – Blrfl Oct 31 '17 at 14:09
  • Oh, I see I have caused confusion. Yes, the database query result does not contain duplicates. But processData modifies the map, replacing some values, introducing some new key/values. So processData could introduce duplicates if it was operating on something other than a Map. – Vidar S. Ramdal Oct 31 '17 at 14:26
  • 7
    @VidarS.Ramdal: It sounds like you need to write your own UniqueList (or OrderedUniqueList) and use that. It's pretty easy, and makes your intended use clearer. – TMN Oct 31 '17 at 15:13
  • 2
    @TMN Yes, I have started thinking in that direction. If you want to post your suggestion as an answer, it will certainly get my upvote. – Vidar S. Ramdal Oct 31 '17 at 15:14
15

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.

  • 5
    This may be a good idea anyway. Heck, you can even have a one-line file that creates ProcessingList as an alias for LinkedHashMap - you can always decide to replace it with something else later, as long as you keep the public interface intact. – CompuChip Oct 31 '17 at 21:28
11

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".

  • I like this thinking - I have been there :) MyBagOfUsefulInformation would need a method (or constructor) to populate it: MyBagOfUsefulInformation.populate(SomeType data). But data would need to be the sorted query result. So what would SomeType be, if not LinkedHashMap? I'm not sure I'm able to break this Catch 22. – Vidar S. Ramdal Nov 1 '17 at 8:37
  • Why can't MyBagOfUsefulInformation be created by the DAO or whatever's generating the data in your system? Why do you need to expose the underlying map at all to the rest of your code outside of the producer and consumer of the Bag? – user101289 Nov 1 '17 at 12:44
  • Depending on your architecture, you may be able to use a private/protected/package-only constructor to enforce that the object can only be created by the producer you want it to. Or you may just need to do it as a convention, that it can only be created by the right "factory". – user101289 Nov 1 '17 at 13:02
  • Yes, I ended up doing something a bit similar, by passing MyBagOfUsefulInformation as a parameter to the DAO method: softwareengineering.stackexchange.com/a/360079/52573 – Vidar S. Ramdal Nov 1 '17 at 14:13
4

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.

1

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.

0

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.

0

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.

  • Hmm, but how would the repository be instantiated? Wouldn't this just be moving the problem somewhere else (to where MyTupleRepository is created?) – Vidar S. Ramdal Nov 1 '17 at 8:23
  • I think I'll run into the same problem as with Peter Cooper's answer. – Vidar S. Ramdal Nov 1 '17 at 8:39
  • My suggestion involves applying Dependency Injection Principle; in this example; MyTupleRepository is an interface that defines capability of retrieving the tuples you mentioned (which queries DB). Here, you inject this object into the processing method. You already have some class that return the data; this only abstracts it in an interface, and you inject the object into the 'processData' method, which internally uses the LinkedHashMap because this is intrinsically part of the processing. – Emerson Cardoso Nov 1 '17 at 9:19
  • I edited my answer, trying to be more clear about what I'm suggesting. – Emerson Cardoso Nov 1 '17 at 9:37
-1

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:

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.

  • "What do you mean there's no natural order but insertion order matters? Are you saying that it matters what order the data was inserted into the DB table, but you have no column that can tell you what order things were inserted?" -- the question states this: "Sorting the map would be a heavy operation, so I want to avoid doing that, given that the query result is already sorted". This clearly means that there is a calculatable definite order to the data, because otherwise sorting it would be impossible rather than heavy, but that defined order is different to the natural order of the keys. – Jules Nov 1 '17 at 4:42
  • 2
    In other words, OP is working on the results of a query like select key, value from table where ... order by othercolumn, and needs to maintain the ordering in their processing. The insertion order they're referring to is the insertion order into their map, defined by the order used in their query, not the insertion order into the database. This is made clear by their use of LinkedHashMap, which is a data structure that has the characteristics both of a Map and of a List of key-value pairs. – Jules Nov 1 '17 at 4:55
  • @Jules I'll clean up that section a bit, thanks. (I actually remembered reading that, but when I was checking things while writing the question, I couldn't find it. lol. Got too in the weeds.) But the question isn't clear on what they're doing with the DB query and whether they have an explicit sort or not. They also say that "insertion order matters." The point is that even if sorting is heavy, you can't rely on the DB to just magically order things correctly if you don't tell it to explicitly. And if you are doing it in the DB, then you can use an "index" to make it efficient in code. – jpmc26 Nov 1 '17 at 5:55
  • *writing the answer (Methinks I should go to bed soon.) – jpmc26 Nov 1 '17 at 6:03
  • Yes, @Jules is right. There is an order by clause in the query, but it is non-trivial (not just order by column), so I want to avoid reimplementing the sorting in Java. Although SQL is powerful (and we're talking about an Oracle 11g database here), the nature of the processData algorithm makes it much easier to express in Java. And yes, "insertion order" means "map insertion order", i.e. query result order. – Vidar S. Ramdal Nov 1 '17 at 8:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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