Duplicate entry and rename check

Question

I wrote a program that prompts users to enter one string per line and stores it into an array. It also checks for duplicate entries as data are fed and renames those to become distinct by appending an incrementing number. Imagine that it will be used by a large number of people in some name registration event. I am concerned about how slow it will run because of all the comparisons as more and more strings are put.

About the code below, the first line scans how many times inputs will be scanned. I have yet to finish the input validation part as I noticed the above performance issue halfway through writing it.

How can I reduce the number of comparisons and make the program run faster?

import java.util.*;

public class Temp {
    public static void main (String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        String[] names = new String[n];
        int namesPoint = 0;
        for(int i=0;i<n;i++) {
            String name = scanner.next();
            int k=0;
            boolean dupe = false;
            for(int j=0;j<namesPoint;j++) {
                if(names[j].equals(name)) {
                    dupe=true;
                    break;
                }
            }
            if(dupe) {
                String newname="";
                while(dupe){
                    dupe=false;
                    k++;
                    StringBuilder sb = new StringBuilder();
                    sb.append(name);
                    sb.append(k);
                    newname = sb.toString();
                    for(int j=0;j<namesPoint;j++) {
                        if(names[j].equals(newname)) {
                            dupe=true;
                            break;
                        }
                    }
                }
                System.out.printf("%s\n",newname);
                names[namesPoint]=newname;
                namesPoint++;
                k=0;
            }else {
                names[namesPoint]=name;
                namesPoint++;
                System.out.printf("OK\n");
            }
        }
        scanner.close();
    }
}

Answer 1

You have the right instinct / deduction that this takes longer than it needs to. This is because each check for duplicates does a 'full scan' over your data. To improve this, you need a way to store / sort your data so that you can quickly ask: "Does this entry already exist?"

Enter the HashSet. A hash set is a data structure that allows for very fast lookups. It does this by mapping entries to an integer (the hash) and then using that to quickly get the right index in an array.

Using a hash set, your program will perform better and have fewer lines of code. The following example code uses the Set.add function that returns true on success (element was added) and false on failure (element was not added, because it already exists).

int n = scanner.nextInt();
Set<String> names = new HashSet<>(n); // expected capacity
while ( n-- > 0 ) {
  String name = scanner.next();
  if ( !names.add(name) ) { // returns false if already present
    // very short but a bit opaque:
    for ( int suffix = 0; !names.add(name + suffix); suffix++ );

    // alternatively, written out:
    for ( int suffix = 0; ; suffix++ ) {
      if ( names.add(name + suffix) ) {
        break;
      }
    }
  }
}

---

for ( int suffix = 0; !names.add(name + suffix); suffix++ ); still scans from 0 every time till an unclaimed name is found... Is there perhaps a quicker way?

Indeed, there is—good catch! We can speed up the duplicate counting by using a Map instead, mapping a name to the number of times we've found it. (This is essentially a multi-set, but our standard libaries don't carry such a data structure, so we 'fake' it.)

Our printing code will look quite different, though:

int n = scanner.nextInt();
Map<String, Integer> names = new HashMap<>(n); // expected capacity
while ( n-- > 0 ) {
  String name = scanner.next();
  int count = names.getOrDefault(name, 0);
  names.put(name, count + 1);
  // alternatively:
  // names.merge(name, 1, Integer::sum);
}

// print results
for ( Map.Entry<String, Integer> entry : names.entrySet() ) {
  String name = entry.getKey();
  int count = entry.getValue();
  System.out.println(name); // plain name
  for ( int i = 0; i < count - 1; i++ ) {
    System.out.println(name + i); // number from 0
  }
}

If you're wondering about the performance of HashMap : it is the same as HashSet. In fact, HashSet uses a HashMap under the hood.