Get object from collection without loop in java

Question

I need to extract an element (each time each time) from Collectionwhich contains tens of thousands of objects several times (hundreds of thousands of times) .

What is the fastest way to perform this search operation? At the moment, mine Collectionis List, and I repeat it until I find the element, but is there a faster way? Perhaps with help Map? I thought:

• Putting objects in Map, the key being the id field of the object, and the object itself is the value.
• Then execution get(id)in Mapshould be much faster than looping through List.
• If this is the right way to do this, should I use HashMapor TreeMap? - my objects do not have a special order.

Any advice on this would be appreciated!

Last note: if an external library provides a tool for an answer, I would gladly accept it!

Answer 1

According to the documentation Tree Map(highlighting my own):

The card is sorted in accordance with the natural order of its keys , or by the comparator provided at the time the card was created, depending on which designer.

, , , - , .

HashMaps , , , HashMaps:

; , , . (get put), - .

, , , , , .

Answer 2

, BinarySearch, TreeMap HashMap .

, , HashMap ( Object hashCode()!), sort + array , TreeMap (- ).

proc array: 2395
proc tree : 4413
proc hash : 1325

, HashMap , , TreeMap , , .

proc array: 506
proc tree : 561
proc hash : 122

:

public class SearchSpeedTest {

    private List<DataObject> data;
    private List<Long> ids;
    private Map<Long, DataObject> hashMap;
    private Map<Long, DataObject> treeMap;
    private int numRep;
    private int dataAmount;
    private boolean rebuildEachTime;

    static class DataObject implements Comparable<DataObject>{
        Long id;

        public DataObject(Long id) {
            super();
            this.id = id;
        }

        public DataObject() {
            // TODO Auto-generated constructor stub
        }

        @Override
        public final int compareTo(DataObject o) {
            return Long.compare(id, o.id);
        }

        public Long getId() {
            return id;
        }

        public void setId(Long id) {
            this.id = id;
        }

        public void dummyCode() {

        }

    }

    @FunctionalInterface
    public interface Procedure {
        void execute();
    }

        public void testSpeeds() {

            rebuildEachTime = true;
            numRep = 100;
            dataAmount = 60_000;

            data = new ArrayList<>(dataAmount);
            ids = new ArrayList<>(dataAmount);
            Random gen = new Random();

            for (int i=0; i< dataAmount; i++) {
                long id = i*7+gen.nextInt(7);
                ids.add(id);
                data.add(new DataObject(id));
            }
            Collections.sort(data);


            treeMap = new TreeMap<Long, DataObject>();
            populateMap(treeMap);


            hashMap = new HashMap<Long, SearchSpeedTest.DataObject>();
            populateMap(hashMap);


            Procedure[] procedures = new Procedure[] {this::testArray, this::testTreeMap, this::testHashMap}; 
            String[] names = new String[]                {"array",       "tree ",            "hash "};


            for (int n=0; n<procedures.length; n++) {
                Procedure proc = procedures[n];
                long startTime = System.nanoTime();
                for (int i=0; i<numRep; i++) {
                    if (rebuildEachTime) {
                        Collections.shuffle(data);
                    }
                    proc.execute();
                }
                long endTime = System.nanoTime();
                long diff = endTime - startTime;

                System.out.println("proc "+names[n]+":\t"+(diff/1_000_000));
            }

        }

        void testHashMap() {
            if (rebuildEachTime) {
                hashMap = new HashMap<Long, SearchSpeedTest.DataObject>();
                populateMap(hashMap);
            }

            testMap(hashMap);
        }

        void testTreeMap() {

            if (rebuildEachTime) {
                treeMap = new TreeMap<Long, SearchSpeedTest.DataObject>();
                populateMap(treeMap);
            }

            testMap(treeMap);
        }

        void testMap(Map<Long, DataObject> map) {

            for (Long id: ids) {
                DataObject ret = map.get(id);
                ret.dummyCode();
            }

        }

        void populateMap(Map<Long, DataObject> map) {
            for (DataObject dataObj : data) {
                map.put(dataObj.getId(), dataObj);
            }
        }

        void testArray() {
            if (rebuildEachTime) {
                Collections.sort(data);
            }
            DataObject key = new DataObject();
            for (Long id: ids) {
                key.setId(id);
                DataObject ret = data.get(Collections.binarySearch(data, key));
                ret.dummyCode();
            }
        }

        public static void main(String[] args) {
            new SearchSpeedTest().testSpeeds();
        }
    }

Answer 3

HashMap , , .

Map, , TreeMap, , - .

Answer 4

, . .

Since order doesn't matter, use HashMap. To maintain order in TreeMap, adding an item adds extra costs, since it must be added to the correct position.