[트러블 슈팅] 잘못된 Comparable을 구현한 클래스의 HashSet, HashMap 사용 시 중복 삽입이 되는 문제

문제 상황

HashMap의 동작방식은 <Key,Value>를 넣을 때, 이미 Key가 존재한다면 기존 Value를 대체하게 됩니다. 하지만 삽입한 Value가 아닌 이전의 Value가 조회되는 문제가 발생했고 왜 이런 문제가 생겼는지 고민해보고 찾아본 과정을 작성하게 되었습니다.

 

상황 재연

사과는 id와  version을 가진다. 사과 별로 서로 다른 id를 가진다고 가정

static class Apple{

    public int id;
    public int version;

    @Override
    public int hashCode() {
        return 1;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null) return false;
        if (getClass() != obj.getClass()) return false;
        Apple other = (Apple) obj;
        if (id != other.id) return false;
        return true;
    }
    
   // ... getter, setter, toString, 생성자 생략
}

참고
문제 상황 재연을 위해 의도적으로 해시 충돌이 많이 이뤄지도록 hashcode를 작성했습니다.
HashSet은 hashcode가 같은 경우 equals로 추가 비교를 합니다.
따라서 위 코드는 HashSet의 성능을 저하시킬 뿐 부정확한 동작을 하지는 않습니다.

 

 

Apple을 생성하고 HashSet에 저장하는 코드입니다.

for(int i=0;i<100;i++) {
    Apple apple = new Apple(i,0); // Apple(id, version)
    appleSet.add(apple);
}

for(int i=0;i<100;i++) {
    Apple apple = new Apple(i,100);
    if(!appleSet.contains(apple)) {
        appleSet.add(apple);
    }
}

System.out.println("appleSet에 저장된 사과의 개수 : " + appleSet.size());

첫 번째 for문에서 사과들은 고유한 번호 0~99를 받아서 appleSet에 저장되고,
두 번째 for문에서 사과들은 이미 appleSet에 존재하기 때문에 저장되지 않는다.

출력 결과

 

 

 

version 순으로 오름차순 정렬을 하고 싶어서 Comparable을 구현했다고 가정

static class Apple implements Comparable<Apple>{

    public int id;
    public int version;

    // Comparable 구현
    @Override
    public int compareTo(Apple o) {
        return this.version - o.version;
    }

    @Override
    public int hashCode() {
        return 1;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null) return false;
        if (getClass() != obj.getClass()) return false;
        Apple other = (Apple) obj;
        if (id != other.id) return false;
        return true;
    }

}

for(int i=0;i<100;i++) {
    Apple apple = new Apple(i,0);
    appleSet.add(apple);
}

for(int i=0;i<100;i++) {
    Apple apple = new Apple(i,100);
    if(!appleSet.contains(apple)) {
        appleSet.add(apple);
    }
}


System.out.println("appleSet에 저장된 사과의 개수 : " + appleSet.size());

for(Apple apple : appleSet) {
    if(apple.id == 0) {
        System.out.println(apple);
    }
}

Comparable을 구현한 뒤 똑같은 코드를 실행하니 사과의 개수가 195개가 존재하고,
중복될 수 없는 Apple이 중복으로 appleSet에 존재하는 것을 확인할 수 있습니다.

출력 결과

 

 

 

 

이런 문제가 발생한 이유

 

HashSet(HashMap)의 동작 구조 

add()메서드의 동작 과정

1. hashcode() 로 자신이 찾아갈 빈을 찾는다.

2. 이때 해시 충돌이 발생한다면, equals()로 같은 객체가 있는지 비교하고, 끝까지 비교해도 없다면 노드를 추가한다.

 

만약 1번 빈에 노드가 N개가 있다면, 1번 빈에 해당 노드가 존재하는지 찾는 시간은 O(N)이다.

이때 해시 함수의 성능이 좋지 않아 모든 노드가 동일한 빈에 들어가게 된다면, O(1)에 가까운 시간복잡도를 제공하는 HashSet이 O(N)의 시간복잡도를 가지게 되는 문제가 있다.

따라서 java에서는 최적화 과정을 수행한다.

 

HashSet(HashMap)의 treeify 최적화

1. 기존 방식은 동일한 객체가 존재하는지 확인하기 위해 연결리스트의 길이만큼 순회해야하는 단점이 존재했다.

2. Java 8에서는 HashMap(HashSet은 내부적으로 HashMap을 사용한다)에서 특정 버킷의 길이가 길어지는 경우 성능 향상을 위해 이진 트리로 변경한다.  (Comparable을 구현한 클래스의 경우에만 동작)

시간 복잡도 O ( log N )

 

 

treeify 최적화 조건

HashMap.class     이진 트리로 변경되기 위한 조건 (참고)

    /**
     * The bin count threshold for using a tree rather than list for a
     * bin.  Bins are converted to trees when adding an element to a
     * bin with at least this many nodes. The value must be greater
     * than 2 and should be at least 8 to mesh with assumptions in
     * tree removal about conversion back to plain bins upon
     * shrinkage.
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * The bin count threshold for untreeifying a (split) bin during a
     * resize operation. Should be less than TREEIFY_THRESHOLD, and at
     * most 6 to mesh with shrinkage detection under removal.
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     * The smallest table capacity for which bins may be treeified.
     * (Otherwise the table is resized if too many nodes in a bin.)
     * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
     * between resizing and treeification thresholds.
     */
    static final int MIN_TREEIFY_CAPACITY = 64;

연결 리스트의 길이가 8 이상인 경우
빈(버킷)의 개수가 64개 이상인지 확인한다.
64개 이상이라면 해당 빈(버킷)의 연결리스트를 이진트리로 변경한다. (64개가 안된다면 빈의 개수를 2배로 늘린다.)

연결 리스트의 길이가 6 이하인 경우
트리로 된 노드들을 연결리스트로 다시 변경한다.

※ 트리화 조건과 리스트화 조건이 2 차이가 나는 이유
하나의 노드가 삽입되고 제거되는 과정이 반복될 경우 트리화 하는 과정과 리스트화 하는 과정이 반복되어 성능이 좋지 않기 때문

 

 

 

 

 

트리화 된 경우 빈(버킷)에 노드가 존재하는 지 확인하기 위해서 O( log N )의 시간 밖에 걸리지 않는다.

 

모든 HashMap에서 이 최적화를 사용할 수 있으면 좋겠지만, Comparable을 구현한 클래스에 대해서만 해당 최적화를 진행한다. hashcode()와 equals() 만으로는 대소구분을 할 수 없기 때문

 

 

 

 

 

 

 

 

Comparable을 구현하지 않은 People

static class People{	
    int id;
    public People(int id) {
        this.id = id;
    }
    @Override
    public int hashCode() {
        return 1;
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj)return true;
        if (obj == null)return false;
        if (getClass() != obj.getClass())return false;
        People other = (People) obj;
        if (id != other.id)return false;
        return true;
    }
}



// ... main 
HashSet<People> set = new HashSet<>();
		
long start = System.currentTimeMillis();
for(int i=0;i<20000;i++) {
    set.add(new People(i));
}
long end = System.currentTimeMillis();

System.out.println(end - start + "mills 걸림.");

※ 참고
수행 시간의 정확한 측정이 아닌 최적화가 수행된다는 것을 보여주기 위해 hashcode가 1만 리턴하고 있다.
실제로 잘 만들어진 hashcode라면 실행시간에 큰 차이가 나지 않는다. 

 

Comparable을 구현하지 않은 실행 시간

 

Comparable을 구현한 People

static class People implements Comparable<People>{	
		
    // Comparable 구현
    @Override
    public int compareTo(People o) {
         return this.id - o.id;
    }

    int id;
    public People(int id) {
        this.id = id;
    }
    @Override
    public int hashCode() {
        return 1;
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null)return false;
        if (getClass() != obj.getClass()) return false;
        People other = (People) obj;
        if (id != other.id)return false;
        return true;
    }
}

 

Comparable을 구현한 실행 시간

 

 

 

잘못된 Comparable 구현

Comparable의 구현 권고사항에는 "equals()의 결과가 true인 경우 compareTo()의 결과는 0이어야 한다." 가 존재한다.

 

이전에 구현했던 Apple 코드에서 equals()에 사용한 멤버변수와 compareTo()에 사용한 멤버가 다름을 확인할 수 있다. (compareTo의 구현 권고사항을 지키지 못함)

static class Apple implements Comparable<Apple>{

    public int id;
    public int version;

// compareTo에서는 version으로 비교
    @Override
    public int compareTo(Apple o) {
        return this.version - o.version;
    }

    @Override
    public int hashCode() {
        return 1;
    }

// equals 에서는 id를 통해 비교
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null) return false;
        if (getClass() != obj.getClass()) return false;
        Apple other = (Apple) obj;
        if (id != other.id) return false;
        return true;
    }

}

 

 

트리화하는 최적화 과정에서 객체들을 구분하기 위해 compareTo를 사용하지만, 객체를 제대로 구분할 수 없는 잘못된 compareTo를 구현해서 문제가 발생한 것이다. 

 

 

 

 

3. 해결 방법

객체들을 구분하는 것과 상관없는 정렬 조건이 필요한 경우 Comparator을 이용해서 정렬을 한다.

 

4. 끝으로

정렬 조건이 필요할 때 Comparable을 아무 생각 없이 구현해서 사용한 적이 많았다.

이 문제를 겪고 보니 구현 규칙을 준수하여 작성하거나, Comparator를 만들어서 사용하는 것이 좋을 것 같다.

 

※ 추가
잘 만든 hashcode의 경우 트리화하는 최적화가 자주 실행되지는 않는다. 빈의 연결리스트가 8개 이상이 될 확률이 낮기 때문이다.

이 때문에 Comparable을 잘못 구현해도 문제를 일으킬 확률은 낮지만, 문제가 발생한다면 원인을 찾기가 매우 어려울 수 있다.

 

 

참고

https://camel-context.tistory.com/65

https://d2.naver.com/helloworld/831311