CODEWITHSUNDEEP
javaarrayssearch
dsb
dsb

Reputation: 2517

efficiently find element in array of objects

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).

Upvotes: 0

Views: 290

Answers (4)

fge
fge

Reputation: 121712

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.

Upvotes: 0

betteroutthanin
betteroutthanin

Reputation: 7546

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.

Upvotes: 2

Brian
Brian

Reputation: 7326

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

Upvotes: 0

Dylan Meeus
Dylan Meeus

Reputation: 5802

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?

Upvotes: 0

Related Questions