MyHashSetV1
이전 포스팅에서 만든 MyHashSetV0의 단점은 add() 메서드가 호출될 때, 셋에 중복된 데이터가 있는지 전체 데이터를 항상 확인해야 했다는 점이다. contains() 메서드도 마찬가지로 전체 데이터를 순차적으로 확인해야 했기 때문에, 모든 경우에서 O(n) 시간이 소요되어 빠른 조회의 개념과는 거리가 멀었다.
그래서 우리는 배열의 인덱스 개념을 차용하여 찾아가는 시간을 O(1)로 단축할 수 있었다. 이 방식은 효율적인 데이터 저장을 가능하게 했지만, 배열 인덱스를 그대로 사용할 경우 메모리 낭비가 심했다. 이를 극복하기 위해 나머지 연산(modulo) 개념을 도입하여, 메모리 낭비를 줄이는 방식으로 MyHashSet V1을 개선했다.(생략)
하지만 이 방식은 Set에 들어올 요소가 Integer일 때만 유효하다. 문자열 같은 다른 타입이 들어올 경우, int index와 매칭될 수 없기 때문이다.
문자열 해시코드
기본형 char는 int로 캐스팅이 가능하다. 모든 문자는 기본적으로 고유한 숫자로 표현될 수 있으며, 예를 들어 'A'는 65, 'B'는 66과 같이 각 문자가 숫자에 대응된다.
예를 들어, "AB"와 같은 String 문자열은 내부적으로 65 + 66의 값으로 처리된다. 즉, 문자열을 저장할 때 각 문자에 고유한 숫자를 할당하여 인식하게 되며, 이 숫자는 ASCII 코드나 유니코드 값에 기반한다.
자세한 내용이 궁금하다면, ASCII 코드표를 참고하여 각 문자가 어떤 숫자로 매핑되는지 확인할 수 있다.
문자열 해시 충돌
- "BC"는 66 + 67 = 133
- "AD"는 65 + 68 = 133
위와 같이 "BC"와 "AD"는 각각 숫자 133으로 변환되지만, 그 값은 해시코드로 사용될 수 있다. 이 과정은 데이터가 해시 함수를 거쳐 해시 코드로 변환되는 방식이다.
해시 충돌이 발생하는 경우, 두 값은 같은 인덱스의 공간에 저장된다. 그러나 "BC"와 "AD"는 서로 동등성이 다르기 때문에, 이들은 equals() 메서드를 통해 구분할 수 있다. 즉, 해시 코드가 동일하더라도, 동등성 비교를 통해 실제 데이터는 서로 다르다고 판별할 수 있다.
Java의 hashCode()
자바에서는 Object.hashCode()를 지원한다. 오브젝트의 해시코드는 참조형의 주소를 해시코드화 시킨다. 보통 대부분의 클래스들은 이를 오버라이딩하여 자신들의 속성들을 해시코드화 시킨다.
MyHashSetV2
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(int capacity) {
this.capacity = capacity;
initBuckets();
}
public MyHashSetV2() {
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) {
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 +
'}';
}
}문자열이든 숫자든 어떠한 객체든, 해당 클래스들이 hashCode()와 equals()를 잘 오버라이딩 했다면, 제네릭에서 Integer를 사용했던 것처럼, 이를 Object로 변경하여도 문제없이 사용할 수 있다.
Object 타입을 도입함으로써, 문자열과 같은 다양한 데이터 타입을 처리할 수 있게 된다. 이로 인해, 타입에 대한 제약이 사라지고, 문자열에 대한 걱정도 덜 수 있게 된다. hashCode()와 equals() 메서드를 통해 객체 비교와 해시 충돌 처리 등이 잘 이루어지면, Object 타입을 통해 다양한 타입의 객체들을 안전하게 관리할 수 있다.
짝꿍 - (hashCode(), equals())
자바의 IDE(IntelliJ)에서는 generate 기능을 통해 equals()와 hashCode()를 동시에 오버라이드하도록 유도한다. 그 이유는 Object 클래스의 hashCode()와 equals() 메서드를 잘 이해하면 명확해진다.
만약 클래스에서 hashCode()만 오버라이딩하지 않았다면, 같은 속성값을 가진 인스턴스라도 다른 객체일 경우 참조값이 달라서 다른 hashCode()가 도출된다. 이런 잘못된 해싱은 서로 다른 인덱스에 동등한 객체가 존재할 수 있게 만들며, 이는 중복을 유발할 수 있다.
반면, equals()만 오버라이딩하지 않으면, 해싱은 잘 되겠지만, add()나 contains()와 같은 메서드에서 set 내부의 아이템이 인자로 들어온 아이템과 "동일성"으로 비교될 때 Object.equals()를 사용하게 된다. 이로 인해 같은 객체라고 생각할 수 있는 인스턴스가 다른 객체로 인식되어 중복이 발생할 수 있다.
hashCode()와 equals() 둘 다 오버라이딩하지 않으면 중복 저장이 일어나며, 동등성 비교가 불가능해져서 버그가 발생할 수 있다. 즉, hashCode()와 equals()는 함께 오버라이딩해야 제대로 된 해시 구조를 사용할 수 있다.
따라서 해시 개념을 사용할 때는 hashCode()와 equals()를 반드시 함께 오버라이드하도록 하자. 대부분의 IDE에서는 이를 generate 기능으로 쉽게 처리할 수 있으므로, 이를 적극 활용하면 빠르게 코드를 작성할 수 있다.
MyHashSetV3
// 인터페이스
package collection.set;
public interface MySet<E> {
boolean add(E element);
boolean remove(E value);
boolean contains(E value);
}
// 구현
package collection.set;
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(int capacity) {
this.capacity = capacity;
initBuckets();
}
public MyHashSetV3() {
initBuckets();
}
private void initBuckets() {
buckets = new LinkedList[capacity];
for (int i = 0; i < capacity; i++) {
buckets[i] = new LinkedList<>();
}
}
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;
}
public boolean contains(E searchValue) {
int hashIndex = hashIndex(searchValue);
LinkedList<E> bucket = buckets[hashIndex];
return bucket.contains(searchValue);
}
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(E value) {
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 +
'}';
}
}
마지막으로, Object 대신 제네릭을 적용하여 내부 타입의 결정을 "아무거나"로 하지 않고, 미래에 책임을 넘기고 통일성을 부여한다. 이렇게 제네릭을 사용하면, MySet에 들어갈 타입을 설계 시점에 정의하고, 유연하게 타입을 변경할 수 있게 된다. 또한, 타입 안정성도 보장받을 수 있어, 타입 관련 오류를 컴파일 타임에 미리 잡을 수 있다.
그리고 MySet은 인터페이스에서 구현되어, 다른 Set 구현체와의 확장성도 남겨둔다. 이를 통해 전략 패턴을 적용할 수 있으며, 나중에 다양한 자료구조를 쉽게 교체하거나 확장할 수 있는 기반을 제공한다. 이는 유지보수와 확장성 측면에서 매우 유리하다.
정리
- 왜 IDE에서 hashCode, equals를 동일 생성해주려 하는지 이해
- char -> int 캐스팅 (ASCII CODE) 이해
- 동등성과 동일성, 속성해싱과 참조주소해싱 이해
