Is there a more efficient way of validating whether duplicate values exist (Java)?

Question

I need to validate that a list of ID's given doesn't contain any duplicate values. My attempt to do this can be shown here:

public void validate(RecordCollection collection)
        throws BusinessException {

    LinkedHashMap<Long, Long> existingIds = new LinkedHashMap<Long, Long>();

    for (Record record : collection.getArrayList()) {

        // check that you don't have two records with the same id
        if (existingIds.containsKey(record.getID())) {
            throw new BusinessException("records must be unique.",
                    ExceptionCodes.RECORDS_MUST_BE_UNIQUE);
        }

        //add the id to the map of existing ids
        existingIds.put(record.getID(), vo.getID());

    }

Is there a more efficient way of implementing this validation?

Answer 1

Yes, there is, with only a slight modification:

for (Record record : collection.getArrayList())
    if (existingIds.put(record.getID(), vo.getID()) != null)
        throw new BusinessException("records must be unique.",
            ExceptionCodes.RECORDS_MUST_BE_UNIQUE);

A Map's .put() operation returns the previous value for the key. If there was no entry, null will be returned. And here, as you don't have null values, it means that if the return code is NOT null, you have a duplicate.

(also, why a LinkedHashMap? Your method returns void, so insertion order does not matter; just use a HashMap)

(also also, as suggested, when building the map, initialize its size to that of the collection you are checking)

Answer 2

In this case I would think about a Set of the id's. The add-method returns a boolean, if the value already existed or not.

So you can use the collection whereever you want and if the add returns a "false" you throw the exception.

About the implementation: The RecordCollection should be a Set and checks the ids on it's own. So the validation-method is a private part of the RecordCollection and when an element is added, the exception will be thrown if needed. The validation-loop is avoided at all.

An if you can't add the validation to the collection, then there is a subclass "IdenticalIDRecordCollection"