efficiently find element in array of objects

Question

I have this very long array of objects:

public static class __Location {
    public __Location(int locationId, String locationDesc) {
        this.LocationId = locationId;
        this.LocationDesc = locationDesc;
    }

    public int LocationId;
    public String LocationDesc;
}


public static __Location[] LOCATIONS = { new __Location(100, "Afghanistan"), new __Location(110, "Albania"), new __Location(120, "Algeria"),
        new __Location(130, "American Samoa"), new __Location(140, "Andorra"), new __Location(150, "Angola"), new __Location(160, "Anguilla"),
        new __Location(170, "Antarctica"), new __Location(180, "Antigua And Barbuda"), new __Location(190, "Argentina"), new __Location(200, "Armenia"),
        new __Location(210, "Aruba"), new __Location(220, "Australia"), new __Location(230, "Austria"), new __Location(240, "Azerbaijan"),
        new __Location(250, "Bahamas"), new __Location(260, "Bahrain"), new __Location(270, "Bangladesh"), new __Location(280, "Barbados"),
        new __Location(290, "Belarus"), new __Location(300, "Belgium"), new __Location(310, "Belize"), new __Location(320, "Benin"),
        new __Location(330, "Bermuda"), new __Location(340, "Bhutan"), new __Location(350, "Bolivia"), new __Location(360, "Bosnia And Herzegovina"),
        new __Location(370, "Botswana"), new __Location(380, "Bouvet Island"), new __Location(390, "Brazil"),
        new __Location(400, "British Indian Ocean Territory"), ...

My question is how can I efficiently search for an item in this long array (according to its key value, i.e., LocationId).

If all locations in your array are unique, you should consider implementing .equals()/.hashCode() and using a HashSet. — fge
– fge, Commented Mar 9, 2014 at 18:45
@Solace good point, however this requires __Location to implement Comparable<__Location>, or use a Comparator<__Location> — fge
– fge, Commented Mar 9, 2014 at 18:51
Please use Java naming conventions - classes should be named in PascalCase. __Location should be Location. — Boris the Spider
– Boris the Spider, Commented Mar 9, 2014 at 18:57

betteroutthanin · Accepted Answer · 2014-03-09 19:34:12Z

2

With HashMap you can access the item efficiently, the time complexity is O(1):

Map<Integer, __Location> map = new HashMap<Integer, __Location>();

The key of this HashMap is LocationId, the value is the corresponding __Location object.

edited Mar 9, 2014 at 19:34

answered Mar 9, 2014 at 18:57

betteroutthanin

7,6569 gold badges31 silver badges48 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

fge Over a year ago

That requires a bit of work to do that... Where does that Integer key come from, for instance?

Ned Over a year ago

@fge The Integer is the "autoboxed" location ID from the object. No real work at all.

fge · Accepted Answer · 2014-03-09 19:58:07Z

0

First of all: rename __Location to Location.

Second: you talk about "efficient search", fine. Now answer these two questions:

where does this location you want to search for come from? Is it a result of a new Location()? The id of this location? The string of this location?
in the container you want to lookup from, are the existing locations sorted? If yes, what against? The id? The string?

Without a clear answer to this question, it is impossible to answer your question.

Let us assume, since that is the most simple case, that a Location is identified by its locationId; you know that for a given locationId, the locationString will be unique.

For maximum efficiency, you should then implement the .equals()/.hashCode() contract in Location and use a HashSet:

public static class Location {
    private final int locationId;
    private final String locationDesc;

    public Location(final int locationId, final String locationDesc)
    {
        this.locationId = locationId;
        this.locationDesc = locationDesc;
    }

    @Override
    public int hashCode()
    {
        return locationId;
    }

    @Override
    public boolean equals(final Object obj)
    {
        if (obj == null)
            return false;
        if (this == obj)
            return true;
        if (getClass() != obj.getClass())
            return false;
        final Location other = (Location) obj;
        return locationId == other.locationId;
    }
}

Then use a HashSet<Location> to insert Locations and use this Set's .contains() method.

answered Mar 9, 2014 at 19:58

fge

122k35 gold badges266 silver badges340 bronze badges

28 Comments

Boris the Spider Over a year ago

+1 for a comprehensive breakdown of the missing information. Think I would still prefer a Map here however.

fge Over a year ago

But what would be the key?

Boris the Spider Over a year ago

I would say the id - just because this makes the intention of the code clear. It also allows lookup by id which a Set doesn't. The OP uses the word search which gives me the impression that the OP wants to find a Location given an id.

fge Over a year ago

Well, anoter solution would probably be to use Guava's Equivalence<Location> depending on the criterion ;)

fge Over a year ago

@NedNowotny none of your remarks make sense; if you really want the fine points of it, look at HashMap's implementation.

|

Dylan Meeus · Accepted Answer · 2014-03-09 18:58:26Z

0

If you use keys, why don't you try using a map?

http://docs.oracle.com/javase/7/docs/api/java/util/Map.html

That way, you can look up a value by it's key, from the context I assume that's what you want to do?

answered Mar 9, 2014 at 18:58

Dylan Meeus

5,8303 gold badges33 silver badges49 bronze badges

1 Comment

Ned Over a year ago

Map is an appropriate interface, but it still matters which implementation is used. For example, I strongly recommend hashMap with immutable keys over a hashSet of any class of objects other than the primitive value wrapper objects.

Brian · Accepted Answer · 2014-03-09 18:59:32Z

0

Consider using a HashSet

Set<_location> locationSet = new HashSet<_location>();
locationSet.add(new __Location(130, "American Samoa"));
...
_location searchLocation = //some _location instance;
if (locationSet.contains(searchLocation)) {
  //found it
}

You will need to override the hashcode and equals methods for your _location class such that equality is determined by locationID.

This is much more efficient then array search which requires traversal. You have O(1) search for HashSet vs O(n) for array

answered Mar 9, 2014 at 18:59

Brian

7,34616 gold badges60 silver badges74 bronze badges

2 Comments

Boris the Spider Over a year ago

Not sure what you mean by You have O(1) search for HashSet vs O(n) for array. A HashSet has an O(1) contains method but this doesn't help with searching given an index. Care to elaborate?

Brian Over a year ago

@BoristheSpider I just assumed the OP wanted to search and evaluate whether a given _location was contained in the set. In reflection, if the OP is actually interested in retrieving the value locationDesc then a HashMap is the better implementation.

Collectives™ on Stack Overflow

efficiently find element in array of objects

4 Answers 4

2 Comments

28 Comments

1 Comment

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

28 Comments

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related