티스토리 뷰

자료구조

자료구조 - Hash Set

realizers 2022. 12. 7. 22:04
728x90
반응형

Hash Set

  • Set은 중복 원소를 저장할 수 없으며 하나의 NULL값만 저장할 수 있습니다. 또한 순서를 보장하지 않기 때문에 순서 보장이 필요한 경우에는 LinkedHashSet을 사용해야 합니다. 
  • 우선 Set에 대해 살펴보기 전에 Hash란 친구는 어떤 역할을 하는지 알아보겠습니다.

 

Hash 란?

  • 어떠한 데이터를 Hash Function의 input으로 넣어 output으로 나오는 결과가 Hash라고 생각하면 됩니다. 그리고 이 도출된 Hash를 사용해 데이터 저장위치의 Key가 됩니다.
  • 그렇다면 왜 Hash Function을 사용해 Hash를 만들고 이를 사용할까요? 그 이유는 효율적인 데이터 탐색이라고 생각할 수 있습니다. 해시를 사용한다면 자료구조(ex: List)를 순회하지 않고 효율적으로 데이터를 탐색할 수 있습니다.

 

💡 Hash의 활용

  • Set은 중복을 허용하지 않는다고 언급을 하였습니다. 그럼 이제 어떻게 중복을 허용하지 않는지 살펴보겠습니다. 
  • Hash Function을 통해 만들어진 Hash를 사용하여 그 값에 대응하는 index를 찾아서 해당 인덱스에 있는 요소만을 검사하게 됩니다. 
  • 참고로 자바에서의 Hash는 hashCode 메서드를 통해 얻을 수 있으므로 따로 구현을 하지 않아도 됩니다. hashCode 메서드는 객체의 주소값을 이용해 해시 알고리즘에 의해 생성된 고유의 정수값을 반환하며, 객체가 같은 메모리를 참조하고 있다면 같은 정수값을 반환하게 됩니다.

 

💡 Hash 충돌

  • Hash Function에서 서로 다른 데이터가 해싱 후 동일한 Hash값이 나오는 경우가 있는데 이를 해시 충돌이라 합니다. 이러한 해시 충돌은 발생확률이 적을수록 좋습니다.
public class Main {
    public static void main(String[] args) {
        String str1 = "0-42L";
        String str2 = "0-43-";

        System.out.println("str1 : " + str1.hashCode()); // str1 : 45721201
        System.out.println("str2 : " + str2.hashCode()); // str2 : 45721201
        System.out.println((str1.hashCode() == str2.hashCode())); // true
    }
}

 

💡 Hash 충돌의 해결방법 - Open Addressing

  • Open Addressing이란 충돌이 발생한 경우 다른 자리에 대신 저장한다는 의미입니다.
  • Linear Probing, Quadratic Probing이 있으며 두가지 동일한 문제점이 있어 가장 이상적인 해결방법은 이중 해시를 사용하는 방법이라 합니다.

Linear Probing

  • 충돌이 발생한 경우 그 옆자리가 비었는지 확인하고 비어있을 경우 그 자리에 대신 저장하는 방식입니다.
  • f(k) + 1 -> f(k) + 2 -> f(k) + 3 ...방식이므로 충돌의 횟수가 증가함에 따라 특정 영역에 데이터가 몰릴 가능성이 높아집니다.

Quadratic Probing

  • Linear Probing의 대안으로 나온곳이 조금 더 멀리서 빈 공간을 찾는 방식입니다.
  • f(k) + 1제곱 -> f(k) + 2제곱 -> f(k) + 3제곱 ... 방식이므로 출동 발생시 n제곱 칸 옆의 슬롯을 검사하게 됩니다.

 

💡 Hash 충돌의 해결방법 - Separate Chaining

  • Separate Chaining은 저장소(Buckets)에서 충돌이 발생한다면 기존 값과 새로운 값을 연결 리스트로 연결하는 방법입니다.
  • 자바에서 Separate Chaining와 보조 해시 함수를 사용하여 해시 충돌을 방지하고 있습니다.

장점

  • 미리 충돌을 대비해서 공간을 만들어 놓을 필요가 없습니다. 충돌이 발생하면 그때 공간을 만들어 연결을 해줍니다.

단점

  • 같은 해시에 자료들이 많이 연결되면 검색시 효율이 낮아질 수 있습니다.

 

구현하고자 하는 구조

 

Bucket의 동적 확장

  • 구현에 앞서 중요한 동적 확장에 대해 살펴보겠습니다.
  • 데이터가 저장되는 공간인 Bucket의 길이를 적게하면 메모리를 아낄 수 있지만 해시코드의 충돌 가능성은 높아집니다. 이러한 이유로 인해 저장된 데이터의 개수가 일정 개수 이상이된다면 버킷의 길이를 2배로 늘리게됩니다. 또한 이러한 동적 확장은 버킷이 75% 차게되면 발생하게 됩니다.
  • 버킷의 최대 개수는 2의 30승이라 합니다.

💡 로드 팩터(부하율)

  • 로드 팩터란 쉽게 설명하면 부하율이라 생각할 수 있습니다. 예를들어 HashSet의 기본 버킷 수는 16입니다. 이때 16개 보다 더 많은 데이터가 들어오게 된다면 버킷의 수를 증가시켜 더 많은 데이터를 받을 수 있도록 해야합니다. 이때 부하율을 몇 %로 잡느냐를 정하는게 로드 팩터입니다.
  • HashSet을 기본적으로 선언하면 디폴트 로드 팩터는 0.75입니다. 즉 75%의 버킷이 차면 추가적으로 데이터를 저장할 공간을 확보하게 됩니다. 이때 용량은 현재 버킷 개수의 2배만큼 용량이 증가하게 됩니다.
  • 이 과정에서 순서 보장이 이루어지지 않게 됩니다. 쉽게 표현하면 기본 버킷의 수 16개 이전에는 데이터가 차곡차곡 쌓아졌더라도 
    버킷의 용량이 2배만큼 증가하게 되면서 기존의 데이터는 새롭게 해시를 얻어 이곳저곳에 저장이 됩니다. 그렇기 때문에 이러한 과정에서 순서가 보장이 안됩니다.

 

Hash Set 구현

💡 구현하고자하는 메서드

public interface Set<E> {

    /**
     * 데이터가 Set에 없는 경우 데이터를 추가합니다.
     */
    void add(E element);

    /**
     * 특정 데이터를 Set에서 삭제합니다.
     */
    void remove(E element);

    /**
     * 특정 데이터가 포함되어 있는지 확인합니다.
     */
    boolean contains(E element);

    /**
     * 특정 데이터가 현재 집합과 같은지 여부를 확인합니다.
     */
    boolean equals(Object o);

    /**
     * 현재 Set의 모든 데이터를 삭제합니다.
     */
    void clear();
}

 

💡 Node 구현

  • Node는 그림에서 설명한 내용을 토대로 구현합니다.
public class Node<E> {

    final int hash;
    final E key;
    Node<E> next;

    public Node(int hash, E key, Node<E> next) {
        this.hash = hash;
        this.key = key;
        this.next = next;
    }
}

 

💡 HashSet의 기본 토대 구현

  • HashSet의 가장 중요한 기본 토대입니다.
  • DEFAULT_CAPACITY는 데이터를 담을 배열의 기본 용적입니다. 또한 데이터의 개수와는 다른 의미이므로 주의해야 합니다.
  • LOAD_FACTOR는 부하율입니다. 테이블의 크기에 비해 데이터의 양이 일정 이상 많아지면 성능이 저하되므로 그 기준점을 75%로 잡고, 75%가 넘으면 용적을 늘릴 수 있도록 합니다.
  • size는 배열의 총 데이터 수입니다.
  • tables는 데이터를 담을 배열입니다.
  • hash 메서드는 최대한의 해시 충돌을 피하기 위한 보조 해시함수입니다.
public class HashSet<E> implements Set<E> {

    private static final int DEFAULT_CAPACITY = 16;  // 최소 기본 용적
    private static final float LOAD_FACTOR = 0.75f;  // 3/4 이상 채워질 경우 resize하기 위한 변수
    private int size;                                // 데이터의 수
    private Node<E>[] tables;                        // 데이터의 정보를 담고 있는 배열

    @SuppressWarnings("unchecked")
    public HashSet() {
        this.tables = (Node<E>[]) new Node[DEFAULT_CAPACITY];
        this.size = 0;
    }

    static final int hash(Object key) {
        int hash;
        if (key == null) {
            return 0;
        } else {
            return Math.abs(hash = key.hashCode()) ^ (hash >>> 16);
        }
    }
}

 

💡 resize 메서드

  • 새로운 배열의 크기는 현재 배열이 가지고 있는 데이터의 개수 * 2를 하여 크기를 지정합니다.
  • 현재 테이블의 크기만큼 반복문을 순회하여 새로운 테이블에 하나씩 옮겨줍니다. 이때 해시 충돌이 발생하는 경우와 발생하지 않는 경우가 있으므로 주의깊게 살펴봐야 합니다.
private void resize() {
    int newCapacity = this.tables.length * 2;
    final Node<E>[] newTables = (Node<E>[]) new Node[newCapacity];

    for (int i = 0; i < tables.length; i++) {
        Node<E> value = tables[i];

        if (value == null) continue;
        tables[i] = null; // help gc

        Node<E> nextNode;
        while (value != null) {
            int index = value.hash % newCapacity; // 새로운 인덱스 생성
            nextNode = value.next;
            // 새로 담을 index에 데이터가 존재하는 경우
            // 즉 새로담을 newTables에 index의 값이 겹치는 경우(해시 충돌)
            if (newTables[index] != null) {
                Node<E> tail = newTables[index];

                // while문을 사용하여 가장 마지막 노드로 이동
                while (tail.next != null) {
                    tail = tail.next;
                }
                // 충돌 발생하는 데이터의 끝지점에 데이터 추가
                tail.next = value; 
            } else {
                // 해시 충돌이 발생하지 않았다면
                newTables[index] = value;
            }
            value.next = null;
            value = nextNode; // 다음 노드로 이동
        }
    }
    this.tables = null; // 명시적 gc
    this.tables = newTables;
}

 

💡 add 메서드

  • 데이터를 추가할 때 해시 충돌이 발생하지 않았다면 정상적으로 데이터가 삽입이 되고, 해시 충돌이 발생한 경우 충돌한 노드의 다음 노드에 새로운 데이터가 삽입될 수 있도록 조정이 필요합니다.
@Override
public void add(E element) {
    add(hash(element), element);
}

private void add(int hash, E key) {
    int index = hash % this.tables.length;
    
    // tables[index]가 비어있는 경우 새로운 노드를 생성합니다.
    if (tables[index] == null) {
        tables[index] = new Node<>(hash, key, null);
    } else {
        // tables[index]가 비어있지 않은 경우는 해시 충돌이 발생한 자리입니다.
        Node<E> conflictNode = tables[index]; // 충돌이 발생한 현재 노드
        Node<E> prev = null;                  // 충돌이 발생한 현재 노드의 이전 노드

        while (conflictNode != null) {
            // 동일한 데이터라면 넣지 않음
            if ((conflictNode.hash == hash) && (conflictNode.key == key) && (conflictNode.key.equals(key))) {
                return;
            }
            prev = conflictNode;
            conflictNode = conflictNode.next; // 다음 노드로 이동
        }
        // 마지막 노드에 새로운 노드 연결
        prev.next = new Node<>(hash, key, null);
    }
    size++;

    // 데이터의 개수가 현재 용적의 75%를 넘어가는 경우 용적 재할당
    if (size >= LOAD_FACTOR * tables.length) {
        resize();
    }
}

 

💡 remove 메서드

@Override
public void remove(E element) {
    remove(hash(element), element);
}

private void remove(int hash, E key) {
    int index = hash % this.tables.length;

    Node<E> node = tables[index];
    Node<E> prev = null;

    if (node == null) {
        return;
    }

    while (node != null) {
        // 같은 노드를 발견했다면
        if (node.hash == hash && (node.key == key && node.key.equals(key))) {
            // 해당 노드의 이전 노드가 없다면 즉 head 노드인 경우
            if (prev == null) {
                tables[index] = node.next; // 현재 노드에 다음 노드 연결
                node = null; // 현재 노드 삭제
            } else {
                // 이전 노드의 next와 삭제할 노드의 다음 노드를 연결합니다.
                prev.next = node.next;
                node = null;
            }
            size--;
            break;
        }
        prev = node;
        node = node.next;
    }
}

 

💡 contains 메서드

@Override
public boolean contains(E element) {
    int index = hash(element) % tables.length;
    Node<E> node = tables[index];

    while (node != null) {
        if (element == node.key || (element != null && (element.equals(node.key)))) {
            return true;
        }
        node = node.next;
    }
    return false;
}

 

💡 equals 메서드

@Override
public boolean equals(Object obj) {
    if (obj == null) {
        return false;
    }
    if (!(obj instanceof HashSet)) {
        return false;
    }

    try {
        HashSet<E> set;
        set = (HashSet<E>) obj;
        if (set.size != size) {
            return false;
        }
        for (int i = 0; i < set.tables.length; i++) {
            Node<E> node = set.tables[i];
            while (node != null) {
                if (!contains((E) node)) {
                    return false;
                }
                node = node.next;
            }
        }
    } catch (ClassCastException e) {
        return false;
    }
    return false;
}

 

💡 clear 메서드

@Override
public void clear() {
    if (tables != null && size > 0) {
        for (int i = 0; i < tables.length; i++) {
            tables[i] = null;
        }
        size = 0;
    }
}

 

✔️ 정리

  • 자바 8에서는 Separate Chaining에서 Linked List 대신 Tree를 사용하기도 한다고합니다. 또한 String 클래스의 hashCode 메서드에서 31를 사용하는 이유는 성능 향상 도모를 위한 것이라고 할 수 있습니다.
  • HashSet은 어렵다...

 

깃 허브)

 

참고자료)

 

 

 

 

 

 

 

728x90
반응형
저작자표시

'자료구조' 카테고리의 다른 글

자료구조 - LinkedHashSet  (0) 2022.12.10
자료구조 - Array List  (0) 2022.12.04
자료구조 - Doubly Linked List  (0) 2022.12.03
자료구조 - Singly Linked List  (0) 2022.12.02