HashSet

1. 직접 구현하는 Set1 - MyHashSetV1

해시 알고리즘을 사용하여 Set(중복 X, 순서 X) 자료구조를 다시 구현해 볼 것이다.

이전 강의에서 구현했던 MyHashSetV0은 데이터 추가, 검색 시에 O(n)으로 성능이 나쁘다.

 

따라서, 해시 알고리즘을 사용하도록 개선된 MyHashSetV1의 코드는 아래와 같다.

import java.util.Arrays;
import java.util.LinkedList;
public class MyHashSetV1 {
    static final int DEFAULT_INITIAL_CAPACITY = 16;
    LinkedList<Integer>[] buckets;
    private int size = 0;
    private int capacity = DEFAULT_INITIAL_CAPACITY;
    public MyHashSetV1() {
        initBuckets();
    }
    public MyHashSetV1(int capacity) {
        this.capacity = capacity;
        initBuckets();
    }
    private void initBuckets() {
        buckets = new LinkedList[capacity];
        for (int i = 0; i < capacity; i++) {
            buckets[i] = new LinkedList<>();
        }
    }
    public boolean add(int value) {
        int hashIndex = hashIndex(value);
        LinkedList<Integer> bucket = buckets[hashIndex];
        if (bucket.contains(value)) {
            return false;
        }
        bucket.add(value);
        size++;
        return true;
    }
    public boolean contains(int searchValue) {
        int hashIndex = hashIndex(searchValue);
        LinkedList<Integer> bucket = buckets[hashIndex];
        return bucket.contains(searchValue);
    }
    public boolean remove(int value) {
        int hashIndex = hashIndex(value);
        LinkedList<Integer> bucket = buckets[hashIndex];
        boolean result = bucket.remove(Integer.valueOf(value));
        if (result) {
            size--;
            return true;
        } else {
            return false;
        }
    }
    private int hashIndex(int value) {
        return value % capacity;
    }
    public int getSize() {
        return size;
    }
    @Override
    public String toString() {
        return "MyHashSetV1{" +
                "buckets=" + Arrays.toString(buckets) +
                ", size=" + size +
                '}';
    }
}

배열의 모든 인덱스 위치에는 연결 리스트가 들어있게 코드를 구현했다.

MyHashSet1은 해시 알고리즘을 사용하였기 때문에 데이터 등록, 검색, 삭제 시에 O(1)로 크게 개선됐다.

 

2. 문자열 해시 코드

숫자가 아닌 문자열 데이터를 저장할 때, 해시 인덱스를 사용하려면 어떻게 해야 할까?

먼저 코드는 다음과 같다.

public class StringHashMain {
    static final int CAPACITY = 10;
    public static void main(String[] args) {
//char
        char charA = 'A';
        char charB = 'B';
        System.out.println(charA + " = " + (int)charA);
        System.out.println(charB + " = " + (int)charB);
//hashCode
        System.out.println("hashCode(A) = " + hashCode("A"));
        System.out.println("hashCode(B) = " + hashCode("B"));
        System.out.println("hashCode(AB) = " + hashCode("AB"));
//hashIndex
        System.out.println("hashIndex(A) = " + hashIndex(hashCode("A")));
        System.out.println("hashIndex(B) = " + hashIndex(hashCode("B")));
        System.out.println("hashIndex(AB) = " + hashIndex(hashCode("AB")));
    }
    static int hashCode(String str) {
        char[] charArray = str.toCharArray();
        int sum = 0;
        for (char c : charArray) {
            sum += c;
        }
        return sum;
    }
    static int hashIndex(int value) {
        return value % CAPACITY;
    }
}

ASCII 코드 표를 참고하면, 모든 문자는 본인만의 고유한 숫자로 표현할 수 있다. 

이 과정을 그림으로 살펴보면 아래와 같다.

 

해시 코드 -> 데이터를 대표하는 값

해시 함수 -> 해시 코드를 생성하는 함수

해시 인덱스 -> 해시 코드를 사용하여 데이터의 저장 위치를 결정하는 값

 

해시 충돌 -> 다른 데이터를 입력해도 같은 해시 코드가 출력될 수 있다.

ex) "BC" -> B(66) + C(67) = 133

"AD" -> A(65) + D(68) = 133

 

3. 자바의 hashCode()

Object.hashCode()

자바는 모든 객체가 자신만의 해시 코드를 표현할 수 있는 기능을 제공한다. Object의 hashCode() 메서드이다.

public class Object {
    public int hashCode();
}

• 이 메서드를 재정의(오버라이딩) 하여 사용한다.
• 객체의 참조값을 기반으로 해시 코드 생성 -> ∴ 객체의 인스턴스가 다르면 해시 코드도 다르다.

코드 구현

import java.util.Objects;
public class Member {
    private String id;
    public Member(String id) {
        this.id = id;
    }
    public String getId() {
        return id;
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Member member = (Member) o;
        return Objects.equals(id, member.id);
    }
    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
    @Override
    public String toString() {
        return "Member{" +
                "id='" + id + '\'' +
                '}';
    }
}

여기서는 Member의 id값을 기준으로 equals 비교를 한다.

 

비교!

• Object의 해시 코드(Object가 기본으로 제공하는 hashCode())
  -> 객체의 참조값을 해시 코드로 사용하므로, 인스턴스마다 서로 다른 값을 반환
• 자바의 기본 클래스의 해시 코드
  -> 데이터의 값이 같으면 같은 해시 코드를 반환

참고!

• 동일성
  • == 연산자 사용
  • 두 객체의 참조가 동일한 객체를 가르키는지 확인하는 것
• 동등성
  • equals() 메서드를 사용
  • 두 객체가 논리적으로 동등한지 확인하는 것

아래의 예시 코드는  동일성은 다르고, 동등성은 같다.

User a = new User("id-100")
User b = new User("id-100")

 

4. 직접 구현하는 Set2 - MyHashSetV2

자바의 hashCode()를 사용하여 타입과 관계 없이 해시 코드를 구할 수 있다.

import java.util.Arrays;
import java.util.LinkedList;
public class MyHashSetV2 {
    static final int DEFAULT_INITIAL_CAPACITY = 16;
    private LinkedList<Object>[] buckets;
    private int size = 0;
    private int capacity = DEFAULT_INITIAL_CAPACITY;
    public MyHashSetV2() {
        initBuckets();
    }
    public MyHashSetV2(int capacity) {
        this.capacity = capacity;
        initBuckets();
    }
    private void initBuckets() {
        buckets = new LinkedList[capacity];
        for (int i = 0; i < capacity; i++) {
            buckets[i] = new LinkedList<>();
        }
    }
    public boolean add(Object value) {
        int hashIndex = hashIndex(value);
        LinkedList<Object> bucket = buckets[hashIndex];
        if (bucket.contains(value)) {
            return false;
        }
        bucket.add(value);
        size++;
        return true;
    }
    public boolean contains(Object searchValue) {
        int hashIndex = hashIndex(searchValue);
        LinkedList<Object> bucket = buckets[hashIndex];
        return bucket.contains(searchValue);
    }
    public boolean remove(Object value) {
        int hashIndex = hashIndex(value);
        LinkedList<Object> bucket = buckets[hashIndex];
        boolean result = bucket.remove(value);
        if (result) {
            size--;
            return true;
        } else {
            return false;
        }
    }
    private int hashIndex(Object value) {
//hashCode의 결과로 음수가 나올 수 있다. abs()를 사용해서 마이너스를 제거한다.
        return Math.abs(value.hashCode()) % capacity;
    }
    public int getSize() {
        return size;
    }
    @Override
    public String toString() {
        return "MyHashSetV2{" +
                "buckets=" + Arrays.toString(buckets) +
                ", size=" + size +
                ", capacity=" + capacity +
                '}';
    }
}

 

5. 직접 구현하는 Set3 - 직접 만든 객체 보관

MyHashSet2는 Object를 받을 수 있으므로 Member와 같은 객체 보관도 가능하다.

주의! hashCode(), equals() 두 메서드를 반드시 모두 구현해야 한다.

import collection.set.member.Member;
public class MyHashSetV2Main2 {
    public static void main(String[] args) {
        MyHashSetV2 set = new MyHashSetV2(10);
        Member hi = new Member("hi");
        Member jpa = new Member("JPA"); //대문자 주의!
        Member java = new Member("java");
        Member spring = new Member("spring");
        System.out.println("hi.hashCode() = " + hi.hashCode());
        System.out.println("jpa.hashCode() = " + jpa.hashCode());
        System.out.println("java.hashCode() = " + java.hashCode());
        System.out.println("spring.hashCode() = " + spring.hashCode());
        set.add(hi);
        set.add(jpa);
        set.add(java);
        set.add(spring);
        System.out.println(set);
//검색
        Member searchValue = new Member("JPA");
        boolean result = set.contains(searchValue);
        System.out.println("set.contains(" + searchValue + ") = " + result);
    }
}

 

↓ 실행 결과

hi.hashCode() = 3360
jpa.hashCode() = 73690
java.hashCode() = 3254849
spring.hashCode() = -895679956
MyHashSetV2{buckets=[[Member{id='hi'}, Member{id='JPA'}], [], [], [], [], [],
[Member{id='spring'}], [], [], [Member{id='java'}]], size=4, capacity=10}
//검색
bucket.contains(Member{id='JPA'}) = true

• Member의 hashCode()를 id 값을 기반으로 재정의했다.
• 자바가 제공하는 기본 클래스들은 대부분 hashCode(), equals()를 함께 재정의해 두었다.

 

6. equals, hashCode의 중요성

클래스를 만들 때 hashCode() , equals() 를 재정의하지 않으면,

해시 자료 구조에서 Object가 기본으로 제공하는 hashCode() , equals() 를 사용하게 된다.

그런데 Object 가 기본으로 제공하는 기능은 단순히 인스턴스의 참조를 기반으로 작동하므로 문제가 생긴다.

 

6.1 hashCode X, equals X

Object의 기본 기능을 사용하기 때문에 객체의 참조값을 기반으로 해시 코드를 사용한다.

-> 실행할 때 마다 값이 달라진다.

 

6.2 hashCode O, equals X

Objects.hash(id) 를 사용해서 id 를 기준으로 해시 코드를 생성한다.

euqls()는 재정의하지 않았으므로 Object의 equals()를 상속 받아서 사용 -> 인스턴스의 참조값을 비교

문제점

1. 데이터 저장
   • Object의 equals()를 상속받아 사용하므로, 참조값이 다르므로 같은 데이터이지만 모두 저장되어서 중복 데이터가 저장된다.
2. 데이터 검색
   • 인스턴스의 참조값을 비교하므로, 같은 데이터여도 같다고 같다고 인식이 불가능하므로 데이터를 찾을 수 없다.

 

6.3 hashCode O, equals O

import collection.set.MyHashSetV2;
public class HashAndEqualsMain3 {
    public static void main(String[] args) {
//중복 등록 안됨
        MyHashSetV2 set = new MyHashSetV2(10);
        Member m1 = new Member("A");
        Member m2 = new Member("A");
        System.out.println("m1.hashCode() = " + m1.hashCode());
        System.out.println("m2.hashCode() = " + m2.hashCode());
        System.out.println("m1.equals(m2) = " + m1.equals(m2));
        set.add(m1);
        set.add(m2);
        System.out.println(set);
//검색 성공
        Member searchValue = new Member("A");
        System.out.println("searchValue.hashCode() = " +
                searchValue.hashCode());
        boolean contains = set.contains(searchValue);
        System.out.println("contains = " + contains);
    }
}

 

↓ 실행 결과

m1.hashCode() = 96
m2.hashCode() = 96
m1.equals(m2) = true
MyHashSetV2{buckets=[[], [], [], [], [], [], [Member{id='A'}], [], [], []],
size=1, capacity=10}
searchValue.hashCode() = 96
contains = true

 

그림과 같이 중복 데이터가 저장되지 않는다.

따라서, 해시 자료 구조를 사용하는 경우 hashCode() 와 equals() 를 반드시 함께 재정의해야 한다.

 

참고 - 해시 함수는 해시 코드가 최대한 충돌하지 않도록 설계

해시 함수로 해시 코드를 만들 때 단순히 문자의 숫자를 더하기만 해서는 해시가 충돌할 가능성이 높다.

해시 충돌 -> 같은 해시 인덱스에 보관 -> 성능이 나빠짐

해결 -> 위해 문자의 숫자를 단순히 더하기만 하는 것이 아니라, 내부에서 복잡한 추가 연산을 수행한다.

결과 -> 해시가 충돌할 가능성이 낮아짐, 해시 자료 구조 성능이 개선됨

 

7. 직접 구현하는 Set4 - 제네릭과 인터페이스 도입

아래의 예시 코드에서는 

• 핵심 기능을 인터페이스로 뽑았다.
• 제네릭을 도입하면 타입 안전성을 높일 수 있다.

public interface MySet<E> {
    boolean add(E element);
    boolean remove(E value);
    boolean contains(E value);
}

import java.util.Arrays;
import java.util.LinkedList;
public class MyHashSetV3<E> implements MySet<E> {
    static final int DEFAULT_INITIAL_CAPACITY = 16;
    private LinkedList<E>[] buckets;
    private int size = 0;
    private int capacity = DEFAULT_INITIAL_CAPACITY;
    public MyHashSetV3() {
        initBuckets();
    }
    public MyHashSetV3(int capacity) {
        this.capacity = capacity;
        initBuckets();
    }
    private void initBuckets() {
        buckets = new LinkedList[capacity];
        for (int i = 0; i < capacity; i++) {
            buckets[i] = new LinkedList<>();
        }
    }
    @Override
    public boolean add(E value) {
        int hashIndex = hashIndex(value);
        LinkedList<E> bucket = buckets[hashIndex];
        if (bucket.contains(value)) {
            return false;
        }
        bucket.add(value);
        size++;
        return true;
    }
    @Override
    public boolean contains(E searchValue) {
        int hashIndex = hashIndex(searchValue);
        LinkedList<E> bucket = buckets[hashIndex];
        return bucket.contains(searchValue);
    }
    @Override
    public boolean remove(E value) {
        int hashIndex = hashIndex(value);
        LinkedList<E> bucket = buckets[hashIndex];
        boolean result = bucket.remove(value);
        if (result) {
            size--;
            return true;
        } else {
            return false;
        }
    }
    private int hashIndex(Object value) {
//hashCode의 결과로 음수가 나올 수 있다. abs()를 사용해서 마이너스를 제거한다.
        return Math.abs(value.hashCode()) % capacity;
    }
    public int getSize() {
        return size;
    }
    @Override
    public String toString() {
        return "MyHashSetV3{" +
                "buckets=" + Arrays.toString(buckets) +
                ", size=" + size +
                ", capacity=" + capacity +
                '}';
    }
}