Finding Duplicate Algorithm - Java

I have set of values, an arraylist, and i have to find duplicate keys. One approach is to use 2 loops. and iterate through the list for each value resutling O(n2).

the other thing, That i can do is to put the values as keys in HashTable. I believed, that hashtable would throw an exception if there is already same key in it. But it is not throwing an exception

    Hashtable<String, String> ht = new Hashtable&开发者_StackOverflow社区lt;String, String>();

    for (int i = 0; i<20; i++){
        ht.put(String.valueOf(i%10), String.valueOf(i%10));
    }

do i understand it wrong? Doesn't hastable/hashmap throw exception if there is already same key in it?

My suggestion is you want a HashSet instead of a Hashtable:

Set<String> ht = new HashSet<String>();

for (int i = 0; i<20; i++){
    if ( !ht.add(String.valueOf(i%10)) ) {
       //it already existed, throw an exception or whatever
    }
}

If you don't care about the values that you add to a map, you almost certainly want a Set and not a Map/table.

No, it doesn't throw an exception, it simply replaces the old value. You can check if a value already exists by calling get:

if (ht.get(key) != null) {
  // value already exists
}

Edit: As @Mark Peters suggested, containsKey is a simpler and sometimes better solution.

You can see in the API docs that put returns null if there was nothing in the table before for that key, and the key's previous value if there was one. (It doesn't throw an exception in either case.)

You may want to read up on the performance characteristics of hashes.

For example, hashes will make answering the question "does this key exist?" fast, which might help with your algorithm.

According to Java Docs, the only exceptions that put may raise is NullPointerException, if key or value is null. You can change your loop to something like:

for(int i = 0 ; i < 20 ; i++) {
    if (ht.containsKey(String.valueOf(i%10)))
        throw new Something();

    ht.put(String.valueOf(i%20), True);
}

From the JavaDoc:

put public Object put(Object key, Object value) Maps the specified key to the specified value in this hashtable. Neither the key nor the value can be null. The value can be retrieved by calling the get method with a key that is equal to the original key. Specified by: put in interface Map Specified by: put in class Dictionary Parameters: key - the hashtable key. value - the value. Returns: the previous value of the specified key in this hashtable, or null if it did not have one. Throws: NullPointerException - if the key or value is null. See Also: Object.equals(Object), get(Object)

It looks like it will let you overwrite the value, but then it gives you the old value as a return Object.

Here's the easiest way to do it:

List yourList;
HashSet noDuplicates = new HashSet(yourList);
HashSet duplicates = new HashSet(yourList).removeAll(noDuplicates);

Depending on your memory vs runtime constraints, I would recommend something if you are space constrained:

You can sort the array (worst case of O(nlog_n) if you use something of the likes of quicksort), and then traverse it to find duplicates in adjacent elements.

Hope this helps