직접 구현하는 Hash Set

HashSet

• 순서 보장 X
• 중복 허용 X
• 조회, 수정, 삭제를 거의 O(1)로 가능

HashSet은 Set의 구현체 중 하나입니다.

직접 구현

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

제네릭을 통해 객체를 저장하도록 수정

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

• 제네릭 타입을 받도록 수정
• 객체에서 equals와 hashCode 오버라이딩 필수

참고

• https://www.inflearn.com/course/김영한의-실전-자바-중급-2