HashSet
#Java
이전 챕터에 처음 정의했던 Set의 성능을 해시 알고리즘을 통해 평균 O(1)으로 개선해보자.
MyHashSetV1
단순히 해시 인덱스를 다음과 같은 방법으로 구한다.
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<>();
}
}
// 중략
private int hashIndex(int value) {
return value % capacity;
}
//...
}
buckets: 연결 리스트를 배열로 사용한다- 해시 인덱스가 충돌이 발생하면 같은 연결 리스트 안에 여러 데이터가 저장된다.
initBuckets(): 연결 리스트를 생성해서 배열을 채운다.- 초기 배열의 크기를 생성자를 통해서 전달할 수 있다.
MyHashSetV1 은 해시 알고리즘을 사용한 덕분에 등록, 검색, 삭제 모두 평균 O(1)로 연산 속도를 크게 개선했다.
남은 문제
해시 인덱스를 사용하려면 데이터의 값을 배열의 인덱스로 사용해야 한다. 그런데 배열의 인덱스는 0, 1, 2 같은 숫자만 사용할 수 있다. "A", "B"와 같은 문자열은 배열의 인덱스로 사용할 수 없다.
문자열 해시코드
문자 데이터를 기반으로 숫자 해시 인덱스를 구하려면 어떻게 해야 할까?
다음 코드를 봐보자.
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;
}
모든 문자는 본인만의 고유한 숫자로 표현할 수 있기 때문에 int형으로 캐스팅하여 표현할 수 있다.
문자열은 두 개의 문자 각각을 int로 캐스팅하여 더하는 방식을 사용하면 된다.
해시 코드와 해시 인덱스
위에서 hashCode() 라는 메서드를 통해서 문자를 기반으로 고유한 숫자를 만들었다. 이렇게 만들어진 숫자를 해시 코드라 한다. 숫자 값인 해시 코드를 사용해서 해시 인덱스를 생성하고, 배열의 인덱스로 사용하면 된다.
해시 함수(Hash Function)
- 해시 함수는 임의의 길이의 데이터를 입력으로 받아, 고정된 길이의 해시값(해시 코드)을 출력하는 함수이다.
- 여기서 의미하는 고정된 길이는 저장 공간의 크기를 뜻한다. 예를 들어서
int형1,100은 둘 다 4byte를 차지하는 고정된 길이는 뜻한다.
- 여기서 의미하는 고정된 길이는 저장 공간의 크기를 뜻한다. 예를 들어서
- 같은 데이터를 입력하면 항상 같은 해시 코드가 출력된다.
- 다른 데이터를 입력해도 같은 해시 코드가 출력될 수 있다. 이것을 해시 충돌이라 한다.
해시 코드(Hash Code)
해시 코드는 데이터를 대표하는 값을 뜻한다. 보통 해시 함수를 통해 만들어진다.
해시 인덱스(Hash Index)
해시 인덱스는 데이터의 저장 위치를 결정하는데, 주로 해시 코드를 사용해서 만든다. 보통 해시 코드의 결과를 배열의 크기로 나누어서 구한다.
세상의 어떤 객체든지 정수로 만든 해시 코드만 정의할 수 있다면 해시 인덱스를 사용할 수 있다.
자바의 hashCode()
해시 인덱스를 사용하는 해시 자료 구조는 데이터 추가, 검색, 삭제의 성능이 O(1)로 매우 빠르다. 하지만 모든 타입을 해시 자료구조에 저장하려면, 정수 int , Integer 뿐만 아니라 char , String , Double , Boolean 등 수 많은 타입, 그리고 개발자가 직접 정의한 Member , User 와 같은 사용자 정의 타입의 객체가 숫자 해시 코드를 제공할 수 있어야 한다.
Object.hashCode()
Object 클래스는 모든 클래스의 최상위 클래스이다. 따라서 자바에서는 모든 객체가 자신만의 해시 코드를 표현할 수 있는 기능을 제공하기 위해 Object에 hashCode() 메서드가 존재한다.
public class Object {
public int hashCode();
}
- 이 메서드를 그대로 사용하지는 않고, 하위 클래스에서 보통 오버라이딩하여 사용한다.
- 이 메서드의 기본 구현은 객체의 참조값을 기반으로 해시 코드를 생성한다.
- 쉽게 이야기해서 객체의 인스턴스가 다르면 해시 코드도 다르다.
예시
public class Member {
private String id;
public Member(String id) {
this.id = id;
}
public String getId() {
return id;
}
// IDE가 자동 완성 해준 hashCode(), equals()
@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 + '\'' +
'}';
}
}
Object obj1 = new Object();
Object obj2 = new Object();
// 각 클래스마다 hashCode를 이미 오버라이딩 해두었다.
Integer i = 10;
String strA = "A";
String strAB = "AB"
// hashCode는 마이너스 값이 들어올 수 있다.
// Integer.valueOf(-1).hashCode()
// 동등한(동일 X) 두 객체. 참조 값이 다르다.
Member member1 = new Member("idA");
Member member2 = new Member("idA");
obj1.hashCode() = 762218386
obj2.hashCode() = 796533847
- 참조값이 다르므로 인스턴스마다 서로 다른 해시 코드 값을 반환한다.
10.hashCode = 10
'A'.hashCode = 65
'AB'.hashCode = 2081
-1.hashCode = -1
- 자바 기본 클래스는 이미
hashCode()메서드가 오버라이딩되어있다. - 데이터의 값이 같으면 같은 해시 코드를 반환한다.
- 값이 중복되지 않는 자료구조에서 값이 존재하는지를 체크하는데 hash가 등장했는데, 값이 같은데 다른 해시 코드를 반환하는 것은 말이 안된다.
- 즉, 동등하면 같은 해시 코드를 반환해야 한다.
- 해시 코드의 경우 정수를 반환하기 때문에 마이너스 값이 나올 수 있다.
(member1 == member2) = false
member1 equals member2 = true
member1.hashCode() = 104101
member2.hashCode() = 104101
Member의 경우 회원의id가 같으면 논리적으로 같은 회원이므로, 동등성 비교의 기준이 된다.- 이에 맞게
equals()를 재정의해야한다.
- 이에 맞게
- 해시코드에도
equals()와 같은 원리가 적용된다.- 회원
id를 기반으로 해시 코드를 생성해야 한다.
- 회원
hashCode()를 재정의할 때Objects.hash()에 해시 코드로 사용할 값을 지정해주면 쉽게 해시 코드를 생성할 수 있다.hashCode()를 재정의하지 않으면Object가 기본으로 제공하는hashCode()를 사용하게 된다. 이것은 객체의 참조값을 기반으로 해시 코드를 제공한다. 따라서 회원의id가 같아도 인스턴스가 다르면 다른 해시 코드를 반환하게 된다.
- 따라서 인스턴스가 다른
member1,member2둘다 같은 해시 코드를 반환하는 것을 확인할 수 있다.
정리
자바가 기본으로 제공하는 클래스 대부분은 hashCode() 를 재정의해두었다.
객체를 직접 만들어야 하는 경우에 hashCode() 를 재정의하면 된다.hashCode() 만 재정의하면 필요한 모든 종류의 객체를 해시 자료 구조에 보관할 수 있다.
정리하면 해시 자료 구조에 데이터를 저장하는 경우 hashCode() 를 구현해야 한다.
MyHashSetV2 - 모든 타입
모든 타입을 받을 수 있도록, V1에서 Integer Object로 수정한다.
hashIndex()
private int hashIndex(Object value) {
//hashCode의 결과로 음수가 나올 수 있다. abs()를 사용해서 마이너스를 제거한다.
return Math.abs(value.hashCode()) % capacity;
}
- 먼저
Object의hashCode()를 호출해서 해시 코드를 찾는다. 그리고 찾은 해시 코드를 배열의 크기(capacity)로 나머지 연산을 수행한다. Object의hashCode()를 사용한 덕분에 모든 객체의hashCode()를 구할 수 있다. 물론 다형성에 의해 오버라이딩 된hashCode()가 호출된다hashCode()의 실행 결과로 음수가 나올 수 있는데, 배열의 인덱스로 음수는 사용할 수 없다.Math.abs()를 사용하면 마이너스를 제거해서 항상 양수를 얻을 수 있다.
자바의 해시 함수는 단순히 문자들을 더하기만 하는 것이 아니라 더 복잡한 연산을 사용해서 해시 코드를 구한다.
아래에서 자세히 다룬다.
직접 구현하는 Set3 - 직접 만든 객체 보관
MyHashSetV2 는 Object 를 받을 수 있다. 따라서 직접 만든 Member 와 같은 객체도 보관할 수 있다.
여기서 주의할 점은 직접 만든 객체가 hashCode() , equals() 두 메서드를 반드시 구현해야 한다는 점이다.
아래 예를 보자.
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");
set.add(hi);
set.add(jpa);
set.add(java);
set.add(spring);
Member searchValue = new Member("JPA");
boolean result = set.contains(searchValue);
hashIndex(Object value)에서value.hashCode()를 호출하면 실제로는Member에서 재정의한hashCode()가 호출된다.
equals() 사용처
그렇다면 equals() 는 언제 사용할까?
"JPA"를 조회할 때 해시 인덱스는 0이다. 따라서 배열의 0 번 인덱스를 조회한다.
여기에는 [hi, JPA] 라는 회원 두 명이 있다. 이것을 하나하나 비교해야 한다. 이때 equals() 를 사용해서 비교한다.
따라서 해시 자료 구조를 사용할 때는 hashCode() 는 물론이고, equals()도 반드시 재정의해야 한다.
만약 equals()를 재정의하지 않으면, Object 가 기본으로 제공하는 참조값 기반의 equals()가 동작하여 문제가 발생한다. 동등한 객체여도 참조값이 달라 다른 해시 코드를 생성하거나, 동등하지 않다고 반환할 수 있다.
참고 - 해시 함수는 해시 코드가 최대한 충돌하지 않도록 설계
자바의 해시 함수는 문자의 숫자를 단순히 더하기만 하는 것이 아니라 내부에서 복잡한 추가 연산을 수행한다.
복잡한 추가 연산으로 다양한 범위의 해시 코드가 만들어지므로 해시가 충돌할 가능성이 낮아지고, 결과적으로 해시 자료 구조를 사용할 때 성능이 개선된다.
해시 함수는 같은 입력에 대해서 항상 동일한 해시 코드를 반환해야 한다.
좋은 해시 함수는 해시 코드가 한 곳에 뭉치지 않고 균일하게 분포하는 것이 좋다. 그래야 해시 인덱스도 골고루 분포되어서 해시 자료 구조의 성능을 최적화할 수 있다. 이런 해시 함수를 직접 구현하는 것은 쉽지 않다. 자바가 제공하는 해시 함수들을 사용하면 이런 부분을 걱정하지 않고 최적화 된 해시 코드를 구할 수 있다.
물론 충돌을 완전히 방지하는 것은 불가능하다. 하지만 equals() 를 사용해서 다시 비교하기 때문에 해시 코드가 충돌하더라도 문제가 되지는 않는다.
V4: 제네릭과 인터페이스 도입
제네릭과 인터페이스를 도입하면 최종적으로 타입 안정성이 높은 자료 구조를 만들 수 있다.
'Programming Language > Java' 카테고리의 다른 글
| [Java] 32. Set (0) | 2025.01.19 |
|---|---|
| [Java] 30. Hash (0) | 2025.01.19 |
| [Java] 29. 컬렉션- ArrayList, LinkedList, List (0) | 2025.01.19 |
| [Java] 28. 제네릭 - Generic(2) (0) | 2025.01.13 |
| [Java] 27. 제네릭 - Generic(1) (0) | 2025.01.13 |