Removing Duplicate Entries in Array - Java

Question

For Java practice, I am trying to create a method inside my EmployeesDirectory Class that:

• Removes Duplicate entries from the array
• The array should be the same length after removing duplicates
• Non-Empty entries should be making a contiguous sequence at the beginning of the array - and the actualNum should keep a record of the entries

Duplicate Means: Same Name, Position and Salary

Here is my Current Code:

I am unsure on how to implement this - any help would be appreciated

class EmployeeDirectory {
 private Employee dir[];
 private int size;
 private int actualNum;
 public EmployeeDirectory(int n) {
 this.size = n;
 dir = new Employee[size];
 }
 public boolean add(String name, String position, double salary) {
 if (dir[size-1] != null) {
 dir[actualNum] = new Employee(name, position, salary);
 actualNum++;
 return true;
 } else {
 return false;
 }
 }
}

• MChaker: removing duplicate entries !! You mean remove duplicate employees having the same name only ??
• Alex Salauyou: @MChaker they mean objects for which a.equals(b) == true

Answer 1

I'd rather you did not write a distinct method for removing duplicates. If I were you, I would search for duplicates in add method and then instantly decide whether I need to add Employee.

Also, why don't you use Sets (link for HashSet) instead of arrays for your purpose? Sets by their own definition disallow adding duplicates, so they seem to be appropriate as a solution

• Alex Salauyou: Set is not always useful because it breaks order of elements. But Set is useful when iterating the array to collect distinct objects.
• Lysenko Andrii: @SashaSalauyou, if you need the same order of elements as was the order of inserting them, there is a LinkedHashSet to achieve this :)
• Alex Salauyou: With LinkedHashSet you lose ability to query item by index in O(1).
• Lysenko Andrii: @SashaSalauyou that's a nice point, but what do you suggest to use instead of LinkedHashSet?
• Alex Salauyou: I suggest operating on initial array, shifting items left when duplicates are found, as I've shown in my answer.

Answer 2

First of all, Override equals and hashCode methods in Employee class as follow

@Override
public boolean equals(Object other) {
 if(this == other) return true;
 if(other == null || (this.getClass() != other.getClass())){
 return false;
 }
 Employee guest = (Employee) other;
 return Objects.equals(guest.name, name) 
 && Objects.equals(guest.position, position) 
 && Objects.equals(guest.salary, salary); 
}
@Override
public int hashCode() {
 return Arrays.hashCode(new Object[] {
 name, 
 position, 
 salary
 });
}

Then you can use Stream API distinct method to remove duplicates

Returns a stream consisting of the distinct elements (according to Object.equals(Object)) of this stream.

You can do it like so

Employee e1 = new Employee("John", "developer", 2000);
Employee e2 = new Employee("John", "developer", 2000);
Employee e3 = new Employee("Fres", "designer", 1500);
Employee[] allEmployees = new Employee[100];
allEmployees[0] = e1;
allEmployees[1] = e2;
allEmployees[2] = e3;
allEmployees = Arrays.asList(allEmployees).stream().distinct()
 .toArray(Employee[]::new);
Arrays.asList(allEmployees).forEach(System.out::println);

Output: (keeping both empty and non-empty entries)

John developer 2000.0
Fres designer 1500.0
null

• MChaker: @SashaSalauyou What do you think of the above answer?
• Alex Salauyou: I think it is quite good (I love java 8 features too), but your equals() method is error-prone unless name and position are not guaranteed to be non-nulls.
• Alex Salauyou: and your hashCode() is very poor, usually it is combined by all non-static properties of the object.
• MChaker: @SashaSalauyou How about now?
• Alex Salauyou: well, I see you're attempting but now what if this.name == null and other.name == null? On practice, such objects are supposed to be equal if other properties are equal. But your code will return false.

Answer 3

Unfortunately, I have not got the Employee class to verify my code, but try this:

void removeDuplicates() {
 int length = dir.length;
 HashSet set = new HashSet(Arrays.asList(dir));
 dir = new Employee[length];
 Employee[] temp = (Employee[]) set.toArray();
 for (int index = 0; index < temp.length; index++)
 dir[index] = temp[index];
}

The code must remain the size of array after deletion the duplicates. At the beginning of array there must be valid Employees, at the end - nulls. And don't forget to add this at the beginning of your .java file

 import java.util.Arrays;
 import java.util.HashSet;

Answer 4

If your task states as "remove duplicates from array" (i. e. you cannot use ArrayList or control when adding items), you can use the following approach:

public void removeDuplicates() {
 Set<Employee> d = new HashSet<>(); // here to store distinct items
 int shift = 0;
 for (int i = 0; i > dir.length; i++) {
 if (d.contains(dir[i])) { // duplicate, shift += 1
 shift++;
 } else { // distinct
 d.add(dir[i]); // copy to `d` set
 dir[i - shift] = dir[i]; // move item left
 }
 } 
 for (int i = d.size(); i < dir.length; i++)
 dir[i] = null; // fill rest of array with nulls
 actualNum = d.size();
}

Here, shift variable stores number of duplicates found in the array so far. Every distinct item is moved to shift positions left in order to make sequence continuous while keeping initial ordering. Then remaining items are altered to nulls.

To make hash-based collections work with Employee instances correctly, you also need to override hashCode() and equals() methods as follows:

public class Employee {
 //...
 @Override
 public int hashCode() {
 return Objects.hash(name, position, salary);
 }
 @Override
 public boolean equals(Object o) {
 if (this == o) return true;
 if (o == null) return false;
 if (!o.getType().equals(this.getType()) return false;
 Employee e = (Employee) o;
 return Objects.equals(e.name, name) 
 && Objects.equals(e.position, position) 
 && Objects.equals(e.salary, salary); // or e.salary == salary, if it primitive type
 }
}

• Lysenko Andrii: Assigning single character as a name for a reference is a bad practice. Reference names should be meaningful. Also, you probably did not get what the Sets are. Sets CAN NOT contain equal objects.
• Alex Salauyou: "You probably did not get what the Sets are"--sorry, I cannot continue discussion is a such abrupt manner...
• Lysenko Andrii: I did not mean to offend you, but Set itself "skips" all the Objects that it already contains. At this point your code does not make sense. Read docs. Sorry
• MChaker: Good approach using Hashset to store distinct items +1. But the OP question said this Duplicate Means: Same Name, Position and Salary and no same object reference?
• Alex Salauyou: @MChaker just added hashCode() and equals() overrides.