Quickly access exact element instance within List java

Question

I have a list that will be filled with many points (x, y, z) - about 3000. Each point is unique within the list (no repeated points).

At some point my program needs to recover the instance of a point stored in the list, because each point has properties like "visited", etc..

Is there any way to recover a certain point (the exact instance) faster than by going through the list sequentially? My attempt was to use a Map that stores the point value as P(x, y, z) and the point instance. Only it didn’t work (gives Stackoverflow error) - because I need to access the point within a recursive function.

for (int x = 0; x < dimension; x++) {
        for (int y = 0; y < dimension; y++) {
            for (int z = 0; z < dimension; z++) {
                Point p = new Point(x, y, z);
                if (indexesBlocked.contains(i)) {
                    p.setBlocked(true);
                }
                points.add(p);
                map.put(p.getKey(), p);
                i++;
            }
        }
    }

Any ideas? Thank you

Answer 1

Your solution meets the requirements, but it will not get satisfactory performance the more your list of elements grow.

Some structures provide us algorithms (remember that structures do not have complexity, algorithms have :) that have standard search time, I recommend you take a look on this website where I will get some information for the answer.

Let’s take a look at the existing complexities (Big O notation):

We can see the relationship between time (t) and quantity of elements (n) in the above table.

Currently your access to the elements being sequential, the complexity would be O(n), and you may be lucky enough to find the item at the beginning of the search or not, anyway the time grows according to the size of your collection.

The recommended structure for this search would be a scatter table, alias Hashtable, Hashmap and Hashset in Java.

The idea is that the key of the element is the index of accurate access to the object you seek, in your case the key would be the points (x, y, z), to access the information contained in the value of Bucket:

public class Point {

    private final int x;
    private final int y;
    private final int z;

    public Point(int x, int y, int z) {
        this.x = x;
        this.y = y;
        this.z = z;
    }

    @Override
    public String toString() {
        return new StringBuilder()
                    .append(x)
                    .append(y)
                    .append(z)
                    .toString();
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + x;
        result = prime * result + y;
        result = prime * result + z;
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Point other = (Point) obj;
        if (x != other.x)
            return false;
        if (y != other.y)
            return false;
        if (z != other.z)
            return false;
        return true;
    }
}

For the access test we can create the following mass:

import java.util.HashMap;
import java.util.Map;

public class Main {

    public static void main(String[] args) {
        Map<Point, String> pointMap = new HashMap<>();

        for (int x = 0; x < 100; x++) {
            for (int y = 0; y < 100; y++) {
                for (int z = 0; z < 100; z++) {
                    Point point = new Point(x, y, z);
                    pointMap.put(point, point.toString());
                }
            }
        }

        long tempoInicial = System.currentTimeMillis();

        System.out.println(pointMap.get(new Point(54, 99, 45)));
        System.out.println(pointMap.get(new Point(65, 99, 45)));
        System.out.println(pointMap.get(new Point(65, 1, 46)));
        System.out.println(pointMap.get(new Point(2, 99, 45)));
        System.out.println(pointMap.get(new Point(99, 99, 99)));

        long tempoFinal = System.currentTimeMillis();

        System.out.println(tempoFinal - tempoInicial);
    }

}

I am representing 100 x elements, 100 y elements and 100 z elements, totaling 1,000,000 elements.

When executing the code you will see that the access times are equal for both the first element and the last element, so we are accessing the elements in O(1).

It is important to remember that the method get Hashmap uses the method containsKey to recover the value of the key through the operation (key==null ? k==null : key.equals(k)), thus the equals class Point was superscripted.