Java ArrayList's and Collections

[timsweb]

Hi All,

I was wondering if I could get some advise on ArrayList's and Collections,

I currently have an ArrayList which becomes big in size, roughly 100,000 - 1,000,000 items, which are of a type I have created, Customers,

When searching the ArrayList, which I currently do with a for loop, I am searching for a match on 2 string items in the Customer object,

My question is how can I make this more efficient as from what I have seen, maps use numerical indexes, when the data I need a match on are Strings,

Also so you know, it is safe to assume the 2 string items in the Customer object are unique when put together,

Any ideas or advise on the best route to go would be great :)

Thanks, Tim

[Ambroos]

A HashMap would work fine, it provides a constant-time search. Just use the 2 strings put together (or separated by some divider) as the key, map it to the Customer object.

[+Fahim S. MVC]

OP: Are you searching for an exact match between the two strings or is there some level of partial mapping needed?

[timsweb]

A HashMap would work fine, it provides a constant-time search. Just use the 2 strings put together (or separated by some divider) as the key, map it to the Customer object.

Thanks, just had a look into HashMaps, what sort speed different should I expect for finding a match when compared to a for loop through an ArrayList?

OP: Are you searching for an exact match between the two strings or is there some level of partial mapping needed?

Exact match

[Ambroos]

Thanks, just had a look into HashMaps, what sort speed different should I expect for finding a match when compared to a for loop through an ArrayList?

I don't have that much experience, but with a HashMap search should always be pretty much instant and almost non-variable in speed (except for some very, very rare cases that get handled automatically). With an ArrayList looking for something at the beginning of your list is extremely fast, but something near the end will be really extremely slow. But I can assure you HashMap is the best you can get when it comes to speed (as long as things don't have to be sorted).

I can help you with the implementation if you want me to. It's good practice for me during the holidays (just finished my first year of software development, we did a lot of hashmapping the last semester :p)

[Andre S. Veteran]

Thanks, just had a look into HashMaps, what sort speed different should I expect for finding a match when compared to a for loop through an ArrayList?

HashMap lookup is O(1 + n/k) (where n = number of elements, k = some constant) while what you were doing is O(N). So for large sets you're looking at several orders of magnitude of improvement. The larger the set the better a hash map becomes compared to a linear search.

http://en.wikipedia....wiki/Hash_table

[timsweb]

Thanks for all the help, have gone with HashMaps and its working perfectly :)

Tim