Solved

Which Java collection to use

Posted on 2004-08-27
14
249 Views
Last Modified: 2010-04-16
Hi,

I seem to have a good idea of Java Collections  but the implementation is the problem.

My question is, which collection should I be using when I want a sorted collection sorted by key ie.  String date,  which is a member of the test object.

ie.
Public class Test {
   String date; // YYMMDD
 ...
}

my instance of Test is what has to be stored. I also need to be able to have duplicate dates in my collection.

I'm just not sure where to start.

Thanks Dan
0
Comment
Question by:dgooderi
  • 6
  • 4
  • 3
  • +1
14 Comments
 
LVL 1

Accepted Solution

by:
talvio earned 80 total points
ID: 11919540
Hi,

to definetly say which collection you should use more info is needed. I would select my collection according to how I need to access items in the collection -by index, by a certain key, just plain iterating, etc. Also I would think if I need to dynamically change the size of the collection and also the size -huge or small- might make a difference. Thread safetiness must also be considered! This is of course only if multiple threads are used to access the container.

Anyway, you should take a look at Comparable and Comparator interfaces. Those will provide you the answer. Two example solutions:

1. Using an array (unflexible in adding and removing items):
Test[] test_array = [your array elements];
TestComparator comp = new Comparator() {
    [your implementation of compare and equals]
}
Arrays.sort(test_array, comp);
// now items are ordered in the array

2. More "Java Collections"-kind of solution:
Collection my_test_objects = [any Java Collection that implements Collection interface,
                                           ListArray, LinkedList, Vector....or TreeSet used in ordering]
TestComparator comp = new Comparator() {
    [your implementation of compare and equals]
}
TreeSet tree_orderer = new TreeSet(comp);
tree_orderer.addAll(my_test_objects);
Iterator iter = tree_order.iterator();
// now the items are ordered and can be
// easily accessed with an iterator.

If you need help with Comparator or Comparable just ask, and help will be provided. ;-). Using Comparable was not in my examples, but it is somewhat similar to using Comparator. Difference is that by implementing Comparable interface you specify the logic that is always used to compare your objects. Using Comparator you can specify different logics for ordering objects. Both should really aply to your problem.

Hope this helps.
-jT


0
 
LVL 14

Expert Comment

by:sudhakar_koundinya
ID: 11919613
i agree with you
0
 
LVL 86

Assisted Solution

by:CEHJ
CEHJ earned 20 total points
ID: 11920087
You should consider storing the date as Date rather than String - it will be more versatile and make time-related operations easier.

>>I also need to be able to have duplicate dates in my collection

What would uniquely identify one object from another with the same date (if anything)?
0
 

Author Comment

by:dgooderi
ID: 11923491
Great answer guys,

I was looking into iterating through the list of objects in the collection.

with date format yymmdd the collection order for inputing these object

Public class Transactions {
   String date; // YYMMDD
   String description;
   double amount;
 ...
}


Object1 - 040506    payment 1         $23.00
Object2 - 040406    donation            $2.00
Object3 - 040506    petrol                $45.55
Object4 - 040507    magazine           $12.99
Object5 - 040506    petrol                $45.55

collection for iterating would contain

Object2 - 040406    donation            $2.00
Object1 - 040506    payment 1         $23.00
Object3 - 040506    petrol                $45.55
Object5 - 040506    petrol                $45.55
Object4 - 040507    petrol                $45.55

I was thinking Linked List so I can iterate through it easily but if I add 1000000 objects to the list, resorting would be an issue?
0
 

Author Comment

by:dgooderi
ID: 11924737
I am about to implement a linked list.
Before inserting a transaction, I was going to iterate through the collection to locate the correct position to insert my transaction

What do you guys think?

Thanks Dan
0
 
LVL 86

Expert Comment

by:CEHJ
ID: 11924989
>>I was going to iterate through the collection to locate the correct position to insert my transaction

If you use a collection such as TreeSet, that is ordered, there is no need to do that as it'll be put in the right place automatically. When using collections, you need to override hashCode and equals in your contained class to ensure they work correctly

http://www.javaworld.com/javaworld/jw-01-1999/jw-01-object.html
0
 
LVL 86

Expert Comment

by:CEHJ
ID: 11924990
Actually the material in question is on page two of that article:
http://www.javaworld.com/javaworld/jw-01-1999/jw-01-object-p2.html
0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 

Author Comment

by:dgooderi
ID: 11925290
problem with treeset is I want to order by date allowing duplicate dates. Sets by definition do not allow duplicate items.

Or am I on the wrong track?
0
 
LVL 1

Expert Comment

by:talvio
ID: 11929046
Hello,

yes, you are correct. Having duplicate items in the set is not possible. To overcome this issue I'd really need to know a few things. First, are you always going to sort the values using the same key, or do you have a need to sort items by other attributes such as item id or name also? Secondly, is item count going to be around millions as you suggested?

If you answered yes to both, then you should definetly start thinking about deploying a database to you application. Having millions of items in memory and then trying to sort them will make your computer beg for mercy. With database doing what you are requesting is simple, trouble for sorting is pretty much left to the database implementation.

If 1000000 was a very worst case scenario then I would probably start to think about having one or multiple supporting collections to do the job. For example, I would probably create a TreeSet for different sorting parameters so that actual items stored in TreeSet are pairs of "sort keys" and collections of items with that sort value. This would again free you from doing the actual sorting yourself and even let you sort items by different attributes. Note that this is just an example how you might want to do, not necessarily the most efficient as I don't know enough about your applicaion. Anyway, using sorting provided by TreeSet is quite a bit faster than doing it yourself by iterating through a list!

You should also provide us info on the general behaviour of your collection usage. Are you adding a large amount of items at once and do it only a few times or are you constantly adding single items to the collection. Also, are you removing items often from your collection. Frequency of different queries to the colleciton is an issue also. All this info is needed because every approach will have its down side. We need to know should we make inserting or searching efficient.

When lots of comparisons are done issues such as having dates rather as Dates that String -as CEHJ suggested- have a major impact on sorting also.

br,
-jT
0
 

Author Comment

by:dgooderi
ID: 11929621
ok 100000 items was a bit extream but 1000 would not be uncommon.

The jist of what I am trying to acheive is a linked list which is sorted by a string ie 20040830. It must be able to handle duplicate dates.

The idea is to be able to iterate through the collection and extract information from a specific date or delete all objects for a spesific date. I hope this helps?
0
 

Author Comment

by:dgooderi
ID: 11929631
a database seems to be too much of a hassel for this type of problem.

I have been thinking of creating a map of dates linking to a linked list of transaction objects. I think this will solve the problem but it will add another level of complexity.
0
 

Author Comment

by:dgooderi
ID: 11929641
-Jt, your first comments realy hit the nail on the head.

Everyone seems to have helped alot in that it took a bit of everyone for it to click.

Thanks guys.
0
 
LVL 86

Expert Comment

by:CEHJ
ID: 11930924
>>problem with treeset is I want to order by date allowing duplicate dates.

That's not a problem. It depends on how you implement the comparision

>>yes, you are correct. Having duplicate items in the set is not possible.

This depends on how you define 'duplicate'. If you define duplicate as all three fields being the same, then you can do what you want. Try running the following:

            Set transactions = new TreeSet();
            transactions.add(new Transaction("040506", "payment1", 23.00));
            transactions.add(new Transaction("040406", "donation", 2.00));
            transactions.add(new Transaction("040506", "petrol", 45.55));
            transactions.add(new Transaction("040507", "magazine", 12.99));
            // Deliberate duplicate
            transactions.add(new Transaction("040506", "petrol", 45.55));
            // NOT a duplicate (amount 1 cent higher)
            transactions.add(new Transaction("040506", "payment1", 23.01));
            System.out.println(transactions);

//-------------------------------------------------------------------

class Transaction implements Comparable {


      final static double EQUALITY_THRESHOLD = 0.000001;
      final static DecimalFormat format = new DecimalFormat("0.00");
      String date;
      String description;
      double amount;
      


      public Transaction(String date, String description, double amount) {
            this.date = date;
            this.description = description;
            this.amount = amount;
      }


      public int compareTo(Object other) {
            Transaction otherTransaction = (Transaction) other;
            int comparison = this.date.compareTo(otherTransaction.date);
            if (comparison == 0) {
                  comparison = this.description.compareTo(otherTransaction.description);
            }
            if (comparison == 0) {
            }
            return comparison;
      }


      public boolean equals(Object other) {
            Transaction otherTransaction = (Transaction) other;
            return (otherTransaction.date + otherTransaction.description).equals(this.date + this.description) &&
                        ((otherTransaction.amount - this.amount) < EQUALITY_THRESHOLD);
      }


      public int hashCode() {
            return (int) amount * date.hashCode() * description.hashCode();
      }
      
      public String toString() {
            return date + " " + description + " " + format.format(amount);
      }
}
0
 
LVL 1

Expert Comment

by:talvio
ID: 11938785
Thanks for the points,
I'm glad to have helped you!

-jT

PS. Yes, I agree that db adds an extra unnecessary dependency if handling items around thousands. Millions on the other hand calls for a db.
0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
count8 challlenge 13 85
topping3 challenge 14 49
backtracking recursion  code 19 40
maven project error 5 20
Introduction This article is the first of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article explains our test automation goals. Then rationale is given for the tools we use to a…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
Viewers learn about the “while” loop and how to utilize it correctly in Java. Additionally, viewers begin exploring how to include conditional statements within a while loop and avoid an endless loop. Define While Loop: Basic Example: Explanatio…
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …

707 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now