[JAVA - 자료구조] HashSet

이제 Set컬렉션에 해시알고리즘을 적용하여 Set보다 훨씬 성능이 좋은 HashSet을 구현해보자

먼저 HashSet에서는 해시 알고리즘을 활용할 인덱스를 갖는 배열과 그 각각의 배열안에 해시 코드값이 같은 데이터를 저장하기위한 LinkedList로 구현된다.

필드영역

static final int DEFAULT_INITIAL_CAPACITY = 16;  

LinkedList<Integer>[] buckets;  

private int size = 0;  
private int capacity = DEFAULT_INITIAL_CAPACITY;

• DEFAULT_INITIAL_CAPACITY: 해시 인덱스가 적용될 배열의 기본 길이를 설정하기위한 상수
• LinkedList<Integer>[] buckets: 해시인덱스가 적용될 배열
• private int size: buckets의 사이즈
• private int capacity = DEFAULT_INITIAL_CAPACITY: 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<>();  
    }  
}

기본생성자와 배열의 길이를 받아서 생성하는 생성자 두 가지를 지원한다
initBuckets()에서는 각각의 배열 인덱스에 LinkedList를 생성해준다.

메서드

add()

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;  
}

먼저 해시알고리즘을 통하여 참조할 해시인덱스를 구하고 구한 해시인덱스를 통해 실제 데이터가 저장될 LinkedList를 구한다. (bucket)
그 다음 bucket리스트에 추가하고자하는 값이 있는지 검사하고 만약 이미 같은 값이 존재한다면 false를 반환하고, 값이 존재하지 않는다면 값을 추가한뒤 size+1을 해준뒤 true를 반환한다.
->Set은 중복값을 허용하지 않기때문에

remove

public boolean remove(int value) {  
    int hashIndex = hashIndex(value);  
    LinkedList<Integer> bucket = buckets[hashIndex];  
    if (bucket.contains(value)) {  
        bucket.remove(Integer.valueOf(value));  
        size--;  
        return true;  
    }  
    return false;  
}

add()메서드와 구현과정이 유사하기때문에 따로 설명은하지 않겠다
하지만 bucket.remove를 하는 과정에서 파라미터로 받은 value를 래퍼 클래스로 박싱하는 부분만 살펴보자

자바가 지원하는 LinkedList의 remove메서드는 아래와 같이 오버로딩 되어있다.

public E remove(int index) {  
    checkElementIndex(index);  
    return unlink(node(index));  
}

public boolean remove(Object o) {  
    if (o == null) {  
        for (Node<E> x = first; x != null; x = x.next) {  
            if (x.item == null) {  
                unlink(x);  
                return true;  
            }  
        }  
    } else {  
        for (Node<E> x = first; x != null; x = x.next) {  
            if (o.equals(x.item)) {  
                unlink(x);  
                return true;  
            }  
        }  
    }  
    return false;  
}

매개변수로 int와 Object가 모두 선언되어있기때문에 인자로 기본타입인 int값을 전달할 경우 삭제가 되지 않거나 index와 일치하는 값을 삭제하는 의도되지 않는 방향으로 구현이 될 수 있다.
때문에 Object타입의 매개변수를 사용하기위해 기본값인 value를 래퍼 클래스로 감싸서 인자로 전달하는 것이다. 이렇게하면 boolean타입으로 반환값을 받을 수 있을것이다.

contains()

public boolean contains(int searchValue) {  
    int hashIndex = hashIndex(searchValue);  
    LinkedList<Integer> bucket = buckets[hashIndex];  
    return bucket.contains(searchValue);  
}

실질적으로 데이터가 저장되어있는 LinkedList를 해시 코드에 맞게 가져온 뒤 그 리스트 안에 검색하고자하는 값이 있는지 조회하여 있으면 true 없으면 false를 반환한다.

공용 메서드

public int getSize() {  
    return size;  
}  

public int hashIndex(int value) {  
    return value % capacity;  
}

지금까지 HashSet을 간단하게 직접 구현해봤다.
여기서 의문점이 하나 생기는데 정수타입은 어떻게 해시 알고리즘을 적용하는지 이해했는데 만약 문자열이 데이터로 들어온다면 어떻게 해시 알고리즘을 적용해야될까?
문자열에 해시알고리즘을 적용하는 방법을 알아보자

---

문자열 해시알고리즘 적용

문자열은 문자의 배열이라는 특성을 이용하며 자바에서 문자는 char타입으로 char하나는 숫자로 치환할 수 있다.
->컴퓨터는 인간이 쓰는 문자를 인식하지 못하기때문에 문자를 숫자로 치환해서 사용함
이러한 특징들을 사용하여 문자열에도 해시알고리즘을 적용할 수 있다.

public class StringHashMain {  
    static final int CAPACITY = 10;  

    public static void main(String[] args) {  
        int AB = hashCode("AB");  
        System.out.println(AB);  
        int hashIndex = hashIndex(AB);  
        System.out.println(hashIndex);  
    }  

    static int hashCode(String string) {  
        char[] charArray = string.toCharArray();  
        int sum = 0;  
        for (char c : charArray) {  
            sum += c;  
        }  
        return sum;  
    }  

    static int hashIndex(int value) {  
        return value % CAPACITY;  
    }  
}

---

용어정리

해시 함수

• 해시 함수는 임이의 데이터를 고정된 길이(저장 공간)의 해시값을 출력하는 함수이다
• 같은 데이터를 입력하면 항상 같은 해시 코드가 출력된다
• 다른 데이터를 입력하면 같은 해시코드가 출력될 수 있는데 이를 해시 충돌이라한다

해시 코드

• 해시 코드는 데이터를 대표하는 값을 뜻한다. 보통 해시 함수를 통해 만들어진다

해시 인덱스

• 해시 인덱스는 데이터의 저장 위치를 결정해주며 주로 해시코드를 사용해서 만든다
• 해시 코드의 결과에 배열의 크기를 나누어서 구한다

이제 정수와 문자열에 해시 코드를 구하는 방법은 충분히 이해했다
다음 문제는 Member, User, Order와 같은 객체는 어떻게 해시 코드를 정의할 수 있을지에 대해 알아보자.

---

자바에서 제공하는 hashCode()

해시 자료구조는 데이터 추가, 검색, 삭제의 성능이 O(1)로 매우 빠르다. 따라서 해시 알고리즘은 많은 곳에서 자주 사용되기때문에 자바는 모든 객체가 자신만의 해시 코드를 표현할 수 있도록 Object클래스에서 hashCode()메서드를 따로 구현해놓았다.

자바에서 제공한 Object.hashCode()를 사용하면 우리가 직접 구현해보았던 문자열의 해시 코드를 편리하고 더 최적화된 상태로 사용할 수 있으며 Member, Order같은 객체에 대한 해시코드도 제공한다.

자바에서 제공하는 hashCode()메서드는 기본적으로 객체의 참조값을 기반으로 해시코드를 만들기때문에 보통 객체 클래스를 만들때 재정의해서 사용한다. 이 부분에 대해서 이해가 잘 안된다면 코드를 통해 설명하겠다.

hashCode()가 재정의 되지 않은 Member클래스 - 인스턴스의 참조값으로 해시코드 생성

public class Member {  

    private String id;  

    public Member(String id) {  
        this.id = id;  
    }  

    public String getId() {  
        return id;  
    }  

    @Override  
    public String toString() {  
        return "Member{" + "id='" + id + '\'' + '}';  
    }  
}

사람이 보는 시선에서 Member클래스는 필드인 id가 같은 멤버라면 같은 사람이라는 것을 인지할 수 있으며 그렇게 되도록 설계해야한다.
즉, 아래의 member1과 member2는 같은 ID를 가지고있기때문에 같은 회원으로 조회되어야하며 해시코드가 동일해야한다.

public class JavaHashCodeMain {  
    public static void main(String[] args) {  
        Member member1 = new Member("member1");  
        Member member2 = new Member("member1");  

        int member1Hash = member1.hashCode();  
        System.out.println(member1Hash);  

        int member2Hash = member2.hashCode();  
        System.out.println(member2Hash);  

        System.out.println(member1.equals(member2));  
    }  
}

실행결과

member1Hash = 168423058
member2Hash = 1325547227
false

하지만 실행결과를 살펴보면 두 인스턴스는 같은 ID를 가지고있음에도 다른 해시코드를 반환하며 equals()의 결과또한 false를 반환하고있다.
이는 Object의 hashCode()메서드가 생성된 인스턴스의 참조값을 기반으로 해시코드를 생성하기때문이다. member1와 member2는 각각 다른 메모리에 생성되며 다른 참조값을 가지고있다는 의미이다.
===이는 물리적(메모리 시점)으로는 일치하지만 논리적(사람 시점)으로는 일치하지 않는다는 것을 의미한다===

이제 Object.hashCode()와 equals메서드를 재정의해서 논리적으로 동등하도록 오버라이딩해보자.

hashCode()가 재정의  Member클래스 - 인스턴스의 필드(id)값을 기반으로 해시코드 생성

public class Member {  

    private String id;  

    public Member(String id) {  
        this.id = id;  
    }  

    public String getId() {  
        return id;  
    }  

    @Override  
    public String toString() {  
        return "Member{" + "id='" + id + '\'' + '}';  
    }  

    @Override  
    public boolean equals(Object object) {  
        if (this == object)  
            return true;  
        if (object == null || getClass() != object.getClass())  
            return false;  
        Member member = (Member) object;  
        return Objects.equals(id, member.id);  
    }  

    @Override  
    public int hashCode() {  
        return Objects.hash(id);  
    }  
}

hashCode()메서드를 재정의할 때 인자로 id필드를 주어서 id가 같은 값일 경우 같은 해시코드를 반환하도록 재정의하였다.

이제 다시 메인 메서드를 실행해서 실행결과를 살펴보면
실행결과

member1Hash = 948881654
member2Hash = 948881654
true

같은 아이디를 가진 멤버에 대해서 같은 해시코드를 반환하는 것을 확인할 수 있으며 equals()메서드의 결과도 true가 나온 것을 확인할 수 있다.