[Collection] Java의 Set과 hashCode()

Set

---

Set란 유일한 요소들의 컬렉션이다.

• 중복된 요소를 허용하지 않으며, 요소를 추가할 때 이미 존재하는 요소는 무시된다.
• 그리고 순서를 보장하지 않기 때문에 출력시 입력 순서와 다를 수 있다.
• 셋은 요소의 유무를 빠르게 확인할 수 있도록 최적화 되어있다. 이는 데이터의 중복을 방지하고 빠른 조회를 가능케한다.

add()로 데이터를 추가할 때 Set에 중복되어있는 데이터가 있는지 항상 확인해야한다. 따라서 처음에 데이터를 추가할 때는 O(1)이지만 그 이후로는 중복된 데이터가 있는지 찾기 때문에 O(n)이다.

 

중복 데이터 검색 O(n) + 데이터 입력 O(1)= O(n).

contains() 로 데이터를 찾을 때는 배열에 있는 모든 데이터를 찾고 비교해야 하므로 평균 O(n)이 걸린다.

 

즉 데이터를 추가할 때마다 중복 데이터가 존재하는지, 체크하기 위해 셋의 전체 데이터를 확인해야한다. 이 때 O(n)으로 성능이 떨어진다.
결국 중복데이터를 찾는 부분의 성능이 않좋다는 것이다. 해당 부분을 개선해보기 위해서는 해시 인덱스를 사용하면 데이터를 찾는 검색 성능을 평균 O(1)로 비약적으로 끌어올릴 수 있다.

 

해시 인덱스

---

모든 숫자를 입력할 수 있다고 가정하면 입력값의 범위가 너무 넓어지며, 데이터의 값을 인덱스로 사용하기는 어렵다. 하지만 입력값의 범위가 넓어도 해당 범위의 값을 모두 다 입력하는 것은 아니다.

 

공간 절약 + 넓은 범위의 값을 사용할 수 있는 방법이 있다 나머지 연산을 활용하면 된다.

• 나머지 연산
  • 1 % 10 = 1
  • 2 % 10 = 2
  • 5 % 10 = 5
  • 8 % 10 = 8
  • 14 % 10 = 4
  • 99 % 10 = 9

크기가 10인 배열이 있다고 가정할 시에, 나머지 연산의 결과를 사용하면 크기가 10인 배열의 인덱스로 사용이 가능하다. 나머지 연산의 결과는 절대로 배열의 크기를 넘지 않는다.

 

이렇게 배열의 인덱스로 사용할 수 있도록 원래의 값을 계산한 인덱스를 해시 인덱스라 한다.

 

14의 나머지 연산은 4, 여기서 4인 값이 해시 인덱스이다. 99의 해시 인덱스는 9이다.

나머지 연산을 통해 해시 인덱스를 구하고, 해시 인덱스를 배열의 인덱스로 사용할 수 있다.

public class HashStart4 {  

    static final int CAPACITY = 10;  

    public static void main(String[] args) {  
        //{1, 2, 5, 8, 14, 99} -> 해쉬 인덱스 구하기  
        System.out.println("hashIndex(1) = " + hashIndex(1));  
        System.out.println("hashIndex(2) = " + hashIndex(2));  
        System.out.println("hashIndex(5) = " + hashIndex(5));  
        System.out.println("hashIndex(8) = " + hashIndex(8));  
        System.out.println("hashIndex(14) = " + hashIndex(14));  
        System.out.println("hashIndex(99) = " + hashIndex(99));  

        Integer[] inputArray = new Integer[CAPACITY];  
        add(inputArray, 1);  
        add(inputArray, 2);  
        add(inputArray, 5);  
        add(inputArray, 8);  
        add(inputArray, 14);  
        add(inputArray, 99);  
        System.out.println("inputArray = " + Arrays.toString(inputArray));  

        //검색  
        int searchValue = 14;  
        int hashIndex = hashIndex(searchValue);  
        System.out.println("searchValue hashIndex = " + hashIndex);  
        Integer result = inputArray[hashIndex]; // O(1)  
        System.out.println(result);  
    }  
    //해쉬 인덱스의 값에 데이터를 넣어야함  
    private static void add(Integer[] inputArray, int value) {  
        int hashIndex = hashIndex(value);  
        inputArray[hashIndex] = value;  
    }  
    // 해쉬 인덱스 구하기  
    static int hashIndex(int value) {  
        return value % CAPACITY;  
    }  
}

• 조회할 값에 나머지 연산자를 사용해서 해시 인덱스를 구한다.
  • 2 % 10 = 2
  • 14 % 10 = 4
  • 99 % 10 = 9
• 해시 인덱스를 배열의 인덱스로 사용해서 데이터를 조회한다.
  • 예) int value = inputArray[hashIndex]
  • 인덱스만 해시 인덱스를 사용하고, 값은 원래 값을 조회한다.
• 배열의 인덱스를 사용하기 때문에 하나의 값을 찾는데 O(1)로 빠른 성능을 제공한다.
  • 해시 인덱스 생성 O(1) + 해시 인덱스를 사용해 배열에서 값 조회O(1) O(1)

hashIndex() : 입력 값을 계산해서 인덱스로 사용하는 것을 뜻한다. 여기서는 입력값을 배열의 크기로 나머지 연산을 통해 해시 인덱스를 구한다.

 

해시 충돌

---

hashCode로 구한 인덱스 값인 hashIndex를 통해 입력한 값이 그대로 해당 인덱스에 저장이 되도록 하였다. 그런데 위의 코드에서는 저장할 위치가 충돌할 수 있다는 한계가 있다. 예를 들어 1, 11의 두 값은 모두 해시 인덱스의 값이 1이 된다.

 

이 경우 둘다 같은 인덱스를 사용하는점에서 해시 충돌이라 한다.

 

위의 예제 코드에서 해시 충돌이 발생할 경우, 가장 나중에 추가한 99의 값이 9를 덮어씌워버린다.

해시 충돌은 낮은 확률로 일어날 수 있다고 가정하는 것이다. 해결방안으로는 값을 덮어 씌워버리는게 아닌 그냥 같은 인덱스에 함께 값을 저장해버리는 것이다.

여러 데이터를 배열의 하나의 공간에 함께 저장할 수는 없다. 대신에 배열안에 배열을 만들면 된다. 배열안에 리스트와 같은 다른 자료구조를 사용할 수 있다.

 

해시 충돌이 발생할 확률은 입력하는 데이터의 수와 배열의 크기와 관련이 있다. 입력하는 데이터의 수와 비교해서 배열의 크기가 클 수록 충돌 확률은 낮아진다.

 

통계적으로 입력한 데이터의 수가 배열의 크기를 75% 넘지 않으면 해시 인덱스는 자주 충돌하지 않는다.

반대로 75%를 넘으면 자주 충돌하기 시작한다.

 

배열의 크기를 크게 만들면 해시 충돌은 줄어서 성능은 좋아지지만, 많은 메모리가 낭비된다. 반대로 배열의 크기를 너무 작게 만들면 해시가 자주 충돌해서 성능이 나빠진다. 상황에 따라 다르겠지만 보통 75%를 적절한 크기로 보고 기준으로 잡는 것이 효과적이다.

 

정리

• 데이터 저장
  • 평균: O(1)
  • 최악: O(n)
    • 데이터 조회
  • 평균: O(1)
  • 최악: O(n)

해시 인덱스를 사용하는 방식은 사실 최악의 경우는거의 발생하지 않는다. 배열의 크기만 적절하게 잡아주면, 대부분 O(1)에 가까운 매우 빠른 성능을 보여준다. 해시 알고리즘은 어떠한 데이터를 고유한 고정된 길이의 숫자나 문자열로 변환하는 방식인데, 중요한 점은 같은 입력에 대해서는 항상 같은 해시 값을 반환한다는 것이다.

 

여기서 의미하는 고정된 길이란 저장된 공간의 크기를 뜻한다. 예를 들어 int형은 4byte를 차지하는 고정된 길이를 뜻한다.

 

그러나 다른 입력에 대해서 동일한 해시 값을 반환하는 경우도 있는데 이를 해시 충돌이라한다. 해당 알고리즘은 특정 데이터가 존재하는지 빠르게 확인하거나, 데이터를 고유한방식으로 정렬하거나 구분할 때 사용된다.

 

해시 코드는 객체에 대한 유일한(식별하기 위한) 정수 값, 해시 함수는 이러한 해시 코드를 생성하는 함수, 그리고 해시 인덱스는 해시 코드를 사용해서 데이터의 저장 위치를 결정하는 값을 뜻한다.

 

hashCode

---

문자열 해시코드

코드 문자 데이터를 기반으로 숫자 해시 인덱스를 구하려할 경우 어떻게 동작하는지 알아보자.

모든 문자는 본인만의 고유한 숫자로 표현할 수 있다. 아스키 코드이다. 예를 들어 "A"는 65를 반환한다. "B"는 66을 반환한다.
"AB"는 65와 66을 한 131이다.

 

그리고 이를 통한 해시코드를 기반으로 해시 인덱스를 생성할 수 있는 것이다. A라는 문자열을 hashCode를 통해 65 값을 얻어낸 후 hashIndex를 통해 나머지 값인 5 라는 인덱스를 얻어낸다.

 

해시코드
hashCode를 통해 나온 정수 값은 HashMap, HashSet, HashTable 등의 해시 기반의 컬렉션에서 이 해시코드를 사용한다.
해당 컬렉션들은 해시코드를 사용하여 객체를 저장 및 검색, 삭제 하는데 사용되며 객체의 동등성을 검사하는데 사용된다. (두 객체가 논리적으로 같다면) 반드시 같은 해시 코드를 반환한다.

 

여태까지의 특징은 Set에서 조회 혹은 검색하려는 값을, 인덱스 그 자체로 쓰고있다.

이것이 해시 알고리즘이 조회 혹은 검색부분에서 강력한 이유, 게다가 데이터를 등록하고 삭제하는 부분에서도 조회와 검색에서 동일한 O(1)의 성능을 가지고 있다.

 

해시 인덱스를 사용하는 해시 자료 구조는 데이터 추가, 검색, 삭제의 성능이 O(1)로 매우 빠르다 . 따라서 많은 곳에서 자주 사용된다.

자바에는 정수 int , Integer 뿐만 아니라 char , String , Double , Boolean 등 수 많은 타입이 있다. 뿐만 아니라 개발자가 직접 정의한 Member , User 와 같은 사용자 정의 타입도 있다.

 

Object.hashCode()

---

해시 알고리즘

이라는 것이 너무 중요하게 사용되기 때문에 `Object`에서 해당 메서드를 정의해놨다. 자바는 모든 객체가 자신만의 해시코드를 표현할 수 있는 기능을 제공하는데 바로 `Object`에 있는 `hashCode()`이다.

• hashCode()를 그대로 사용하기 보다는 보통 오버라이딩해서 사용한다.
• hashCode()의 기본 구현은 객체의 참조값을 기반으로해서 해시 코드를 생성한다.
• 쉽게 이야기해서 객체의 인스턴스가 다르면 해시코드도 다르다.

public class JavaHashCodeMain {  

    public static void main(String[] args) {  
        //Object의 기본 hashCode는 객체의 참조값을 기반으로 생성  
        Object obj1 = new Object();  
        Object obj2 = new Object();  
        System.out.println("obj1.hashCode() = " + obj1.hashCode());  
        System.out.println("obj2.hashCode() = " + obj2.hashCode());
        System.out.println("obj1 = " + obj1);  
        System.out.println("obj2 = " + obj2);
    }
 }

결과

obj1.hashCode() = 762218386
obj2.hashCode() = 796533847
obj1 = java.lang.Object@2d6e8792
obj2 = java.lang.Object@2f7a2457

hashCode의 결과는 객체의 참조값을 기본으로 10진수로 생성한 값이다. 그리고 그 밑의 결과는 참조값을 기반으로 16진수로 나타낸 것이다.

 

Object 가 기본으로 제공하는 hashCode() 는 객체의 참조값을 해시 코드로 사용한다. 따라서 각각의 인스턴스마다 서로 다른 값을 반환한다.

Object 클래스의 hashCode() 메서드는 객체의 메모리 주소를 정수 형태로 반환한다.
Object 클래스의 toString 메서드

이 메모리 주소는 객체가 JVM(Java Virtual Machine) 힙 메모리에서 위치한 곳을 가리키는 유일한 값에 해당하는데, 메모리 주소를 직접적으로 반환하는 것이 아닌, 해당 메모리 주소를 바탕으로 만든 해시 값을 반환하는 것이다.

 

마치 99를 넣었을 때 99라는 인덱스를 반환하는 것이아닌 9라는 인덱스를 반환하는 것처럼 해당 값을 가지고 고유한 값을 반환하는 것이다.

객체의 동일성과 동등성

---

`Object` 는 동등성 비교를 위한 `equals()` 메서드를 제공한다. 자바는 두 객체가 같다라는 표현을 2가지로 분리해서 사용한다.

• 동일성(Identity) : == 연산자를 사용해서 두 객체의 참조가 동일한 객체를 가리키고 있는지 확인한다.
• 동등성(Equality) : equals() 메서드를 사용하여 두 객체가 논리적으로 동등한지 확인한다.

즉 동일성(==) 은 물리적으로 같은 메모리에 있는 객체인지 메모리의 참조값을 확인하는 것이고, 동등성(equals()) 은 논리적으로 같은지 확인하는 것이다.

 

여기서 물리적이란, 메모리의 참조가 기준인 값을 물리적이라하며, 논리적이란 사람이 생각하는 기준을 뜻한다.

System.out.println("(member1 ==  member2) = " + (member1 == member2));  
System.out.println("member1 equals member2 = " + member1.equals(member2));  

여기서 == 동일성을 통한 비교의 값은 false인 이유와 equals()가 true인 이유에 대해서 좀 더 자세히 설명해보자면,

동일성은 물리적인 위치라 했다. 물리적인 위치라 함은 메모리에 참조되는 값을 의미하는데, member1과 member2는 new 연산자를 통해 세상에 나온 얘이기 때문에 각각의 Heap 메모리에 들어갈 것이다. 그러니 이들이 차지하는 메모리의 참조값은 서로 다를 수 밖에 없다.

 

그러기에 저 둘의 동일성을 비교했을 시 서로 같지 않기 때문에 나오는 값은 false이다.

그럼 동등성을 비교해보자. 둘이 가지고 있는 값은 아래 코드와 같다.

Member member1 = new Member("idA");  
Member member2 = new Member("idA");

그럼 사람의 시점에서 둘의 값은 현재 같은 값을 가지고 있다. 같은 값을 가지고 있기 때문에 객체가 가지고 있는 값만 비교해서 봤을 때 둘은 논리적으로 같다고 할 수 있다.

 

그러므로 동등성에 대해서는 true라는 값이 반환되는 것이다.

 

equals,hashCode의 중요성

해시 자료 구조를 사용하려면 `hashCode()` 도 중요하지만, 해시 인덱스가 충돌할 경우를 대비에서 `equals()` 도 반드시 재정의해야 한다.  해시 인덱스가 충돌할 경우 같은 해시 인덱스에 있는 데이터들을 하나하나 비교해서 찾아야한다. 이때 `equals()` 를 사용해서 비교한다.

해시 인덱스가 같아도 실제 저장된 데이터는 다를 수 있다. 따라서 특정 인덱스에 데이터가 하나만 있어도 `equals()` 로 찾는 데이터가 맞는지 검증해야 한다.

 

예를들어 두 개의 객체가 있고 같은 값을 가지고 있다는 가정하에, 두 메서드를 재정의하지 않고 동등성과 동일성을 비교했을 경우

두 객체는 동등성과 동일성에 대해서도 false를 반환할 것이다. 그리고 값이 같기 때문에 저장되는 인덱스는 다르며 값이 중복되어서 저장된다.

 

hashCode는 구현했지만 equals를 구현하지 않은 경우

hashCode는 구현했지만 equals를 구현하지 않은 경우, 해시 테이블(예: HashSet, HashMap)에서 같은 해시 코드를 가진 객체가 동일한 버킷에 저장될 수 있지만, equals 메서드가 재정의되지 않았기 때문에 논리적으로 동일한 객체라도 서로 다른 객체로 간주된다.

이로 인해 데이터의 중복 저장이 발생할 수 있으며, 논리적으로 동일한 객체를 검색할 때, 다른 인스턴스로 인해 찾을 수 없게 될 것이다.

 

 

 

정리
두 객체가 논리적으로 같다면 hashCode도 같다.
두 객체는 실질적으로 다른 메모리를 참조하기 때문에 인스턴스는 다르다. 그러므로 == 연산자를 통해서 나오는 값은 false이다.

 

hashCode() 만 재정의하면 필요한 모든 종류의 객체를 해시 자료 구조에 보관할 수 있다. 정리하면 해시 자료 구조에 데이터를 저장하는 경우 hashCode() 를 구현해야 한다. 그리고 equals()도 같이 재정의 해야한다.

 

해시 코드를 통해, 해시 인덱스를 생성하고, 해시 인덱스를 통해 값을 저장하는 것에 대해 학습했다. 해시 코드가 필요한 이유는 Set의 자료구조는 중복된 값을 허용하지 않는데, 허용하지 않을 수 있던 것은 hashCode와 equals를 통해 물리적, 논리적으로 같은 인스턴스인지 혹흔 같은 값을 가지고 있는지의 기준에 따라 값을 저장 할지 안할지를 결정하는 것을 배웠다.

 

Set이 순서를 보장하지 않는 이유

왜냐하면 데이터 저장 시 HashIndex 값을 기준으로 값을 저장하게 되는데 어떠한 값이 저장되냐에 따라 Index가 달라지기 때문에 순서를 보장하지 않는 것.

 

Set 인터페이스의 구현체

HashSet

- 해시 자료 구조를 사용해서 요소를 저장한다.

- 요소들은 특정한 순서 없이 저장된다. 즉, 요소를 추가한 순서를 보장하지 않는다.

- HashSet의 주요 연산(추가, 삭제, 검색)은 평균적으로 O(1) 시간 복잡도를 가진다.

- 데이터의 유일성만 중요하고, 순서가 중요치 않은 경우에 적합하다.

 

LinkedHashSet

- Node를 이용해 연결리스트를 추가해서 요소들의 순서를 유지한다.

- 각 요소들은 추가된 순서대로 유지되며, 순서대로 조회 시 요소들이 추가된 순서대로 반환된다.

- 주요 연산에 대해 평균 O(1) 시간 복잡도를 가진다.

- 데이터의 유일성과 함께 데이터의 순서가 중요한 경우 적합하다.

- 참고: 연결 링크를 유지해야 하기 때문에 `HashSet` 보다는 조금 더 무겁다.