CODEWITHSUNDEEP
javadata-structures
Joe
Joe

Reputation: 4928

Java Data Structure

I'm looking for a data structure that will act like a Queue so that I can hava First In First Out behaviour, but ideally I would also be able to see if an element exists in that Queue in constant time as you can do with a HashMap, rather than the linear time that you get with a LinkedList.

I thought a LinkedHashMap might do the job, but although I could make an iterator and just take and then remove the first element of the iteration to produce a sort of poll() method, I'm wondering if there is a better way.

Many thanks in advance

Upvotes: 1

Views: 292

Answers (2)

Peter Lawrey
Peter Lawrey

Reputation: 533930

Often when you want the behaviour of two collections you need to maintain two collections. A simple approach is to have a Queue and a HashSet, and always perform an add to both and remove from the HashMap when you remove from the Queue.

An alternative is to use a LinkedHashSet. This retains the order elements were added and you can remove the first/oldest element each time.

A third option is to use just a Queue. While you might like O(1) lookup time, you may find it is fast enough to meet your requirements by just searching every element. This might be much faster than you expect. i.e. 1000 elements should be less than 10 micro-seconds.

EDIT: I agree that two collections is best when you don't know the length.

However to show you a brute force search can be fast too. The slowest object to look for is one which is not there. (As it has to compare every element)

Queue<Point> points = new ArrayBlockingQueue<Point>(1024);
for(int i=0;i<1000;i++)
  points.add(new Point(i,i));
Point missing = new Point(-1, -1);
int runs = 100 * 1000;
long start = System.nanoTime();
for(int i=0;i< runs;i++)
    points.contains(missing);
long time = System.nanoTime() - start;
System.out.printf("Average contains() took %.1f us%n", time/runs/1000.0);

Prints 

Average contains() took 5.1 us

You may need to test this for your data type as times of equals() and sizes of queue can vary, but you may be surprise what you can do in 10 micro-seconds and that may be fast enough.

Upvotes: 2

musiKk
musiKk

Reputation: 15189

I don't know if there is something out there but you could easily create a compound object that consists of a Queue and a HashSet. All modifying operations need to occur on both collections at the same time to keep them in sync. You can then use the set for lookup which should be very fast.

Upvotes: 3

Related Questions