• 0

Java ArrayList's and Collections


Question

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

Link to comment
https://www.neowin.net/forum/topic/1097901-java-arraylists-and-collections/
Share on other sites

6 answers to this question

Recommended Posts

  • 0
  On 12/08/2012 at 10:31, Ambroos said:

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?

  On 12/08/2012 at 10:55, .fahim said:

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

Exact match

  • 0
  On 12/08/2012 at 12:20, timsweb said:

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)

  • 0
  On 12/08/2012 at 12:20, timsweb said:

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

This topic is now closed to further replies.
  • Posts

    • Clear Linux is open source, indeed, so its source code is available for anyone. They're just shutting down its support from them, they're not forbidding anyone else from taking over.
    • Linux Mint is also my favorite distro, but I fear what will happen with it if Clem were to disappear tomorrow, to be honest.
    • Yeah, I totally get your point, which is possible it could happen. I just hope there is a few people around him who are similar to where if they took over things would run pretty much the same. if not, then yeah, it could start to decline rapidly etc. but I figure something that's been around for a longer period of time with a decent backing, and probably more users than most Linux distro's (which I would 'imagine' Mint is one of the more used Linux desktop distro's by volume of people who use it), is less likely to just disappear. but like you said, nothing is guaranteed. but I do think you are probably right in that Clem is probably the core of what keeps Mint, Mint. I like how it tends to stay pretty much the same with some slight tweaks here and there (but is largely the same) instead of that crap some people go for with change for the sake of change trying to create a overly fancy interface and other unnecessary stuff etc. I also feel Mint keeps a nice balance of things out-of-the-box where it's not too bloated, nor too striped down. p.s. but I see Mint as a better Ubuntu basically. but I get your point like if it was more of a really serious choice of needing a 'safe bet' to use long term, then yeah something like official Ubuntu would be one of the better choices for sure given what you said with it being backed by an actual company which makes it a safer bet than Mint which is smaller and 'could' potentially be more fragile.
    • It’s in development so hopefully it’s improved upon before release.
    • For the 10th iteration they could have bothered with some design changes rather than just carrying over the 9's
  • Recent Achievements

    • First Post
      leoniDAM earned a badge
      First Post
    • Reacting Well
      Ian_ earned a badge
      Reacting Well
    • One Month Later
      Ian_ earned a badge
      One Month Later
    • Dedicated
      MacDaddyAz earned a badge
      Dedicated
    • Explorer
      cekicen went up a rank
      Explorer
  • Popular Contributors

    1. 1
      +primortal
      506
    2. 2
      ATLien_0
      209
    3. 3
      Michael Scrip
      202
    4. 4
      Xenon
      146
    5. 5
      +FloatingFatMan
      121
  • Tell a friend

    Love Neowin? Tell a friend!