자바 HashSet
포스팅에 앞서 내용이 틀릴 수 있습니다.
해당 부분 지적 감사히 받습니다.
이번시간에는 HashSet에 대해 알아보자.
자료구조 중에서는 검색 효율이 O(1)인 자료구조가 있다. (정확히는 O(1)에 근접하는, 최악 O(N)이나 확률 극히 낮음)
바로 HashSet이다.
HashSet은 순서를 고려하지 않고, 중복을 허용하지 않는 자료 구조이다.
HashSet의 가장 큰 장점은 데이터 서칭 시간이 O(1)에 근사한 값으로 아주 빠르게 원하는 값을 찾아낼 수 있다.
다른 자료 구조들은 모든 데이터를 탐색하며, 찾고자 하는 값이 있는지 하나하나 비교를 했어야 했다.
어떻게 O(1)로 검색을 할 수 있는 것일까?
바로 찾고자 하는 데이터를 인덱스로 사용하면 해결된다.
int 7을 array [7]에 저장해 두면, 해당 데이터의 위치를 아니까, 바로 접근해서 찾을 수 있게 된다.
이것이 HashSet의 원리이다.
하지만 이는 데이터가 int 타입일 때만 사용 가능하다.
String 타입을 HashSet에 저장하려면? index는 반드시 음이 아닌 정수로 갖기 때문에 방금 설명까지 만으로는 구현이 불가능하다.
따라서 String이든 다른 타입이든 음이 아닌 정수로 표현할 수 있어야 한다.
바로 hashCode()가 이를 가능하게 해 준다.
자바에서는 기본적으로 Object 클래스에 hashCode가 선언되어 있다.
또 자바는 String과 같은 기본 객체 클래스에 각 hashCode가 선언되어 있다.
따라서 래퍼 클래스를 사용할 때는, 기본적으로 오버라이딩 된 hashCode()를 사용해 인덱스를 구하면 된다.
import java.util.Arrays;
import java.util.LinkedList;
public class MyHashSetV2 {
static final int DEFAULT_INITIAL_CAPACITY = 16;
private LinkedList<Object>[] buckets;
private int size = 10;
private int capacity = DEFAULT_INITIAL_CAPACITY;
public MyHashSetV2(){
initBuckets();
}
public MyHashSetV2(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(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){
int hashCode = value.hashCode();
int hashIndex = Math.abs(hashCode) % capacity;
return hashIndex;
}
public int getSize(){
return size;
}
@Override
public String toString() {
return "MyHashSetV2{" +
"buckets=" + Arrays.toString(buckets) +
", size=" + size +
", capacity=" + capacity +
'}';
}
}
HashSet구현
public class MyHashSetV2Main {
public static void main(String[] args) {
MyHashSetV2 set = new MyHashSetV2(10);
set.add("A");
System.out.println("\"A\".hashCode() = " + "A".hashCode());
set.add("B");
System.out.println("\"B\".hashCode() = " + "B".hashCode());
set.add("C");
System.out.println("\"C\".hashCode() = " + "C".hashCode());
set.add("D");
System.out.println("\"D\".hashCode() = " + "D".hashCode());
set.add("AB");
System.out.println("\"AB\".hashCode() = " + "AB".hashCode());
set.add("SET");
System.out.println("\"SET\".hashCode() = " + "SET".hashCode());
System.out.println("set = " + set);
}
}
HashSetMain
실행결과
"A".hashCode() = 65
"B".hashCode() = 66
"C".hashCode() = 67
"D".hashCode() = 68
"AB".hashCode() = 2081
"SET".hashCode() = 81986
set = MyHashSetV2{buckets=[[], [AB], [], [], [], [A], [B, SET], [C], [D], []], size=16, capacity=10}각 문자열의 해시함수를 적용한 결과 해시 코드가 나왔고 이를 용량으로 나눠주면 미리 정해둔 인덱스 범위 내에 분배된다.
위에서는 capacity가 10이고, 각 해시 코드를 10으로 나눈 나머지를 인덱스로 사용하면 어떤 문제가 생길까?
B와 SET의 경우 나머지가 6으로 갖게 나온다.
이를 해시 충돌이라 한다.
하지만 해시 충돌이 발생해도 괜찮다.
미리 정의해 둔 10이라는 크기 안에 LinkedList를 넣어줌으로써 해시 충돌이 나도 값을 넣을 수 있다.
그래서 값을 찾을 때는, 먼저 해시코드로 인덱스를 찾고, 그 안에 있는 LinkedList를 돌며 해당 값을 찾는 식으로 탐색이 일어나게 된다.
그렇기 때문에 최악의 경우 O(N)이 나타날 수 있게 되는 것이다. (B와 SET만 들어갔을 경우)
보통은 O(1)의 속도를 가지며, 평균적으로는 해시 함수에 의해 해시코드가 잘 분포되어 O(1)에 근사한 탐색 시간을 갖는다.
또 우리는 사용자 정의 클래스(타입) 또한 선언할 수 있었다.
이럴 경우에는 반드시 equals와 hashCode 메서드를 직접 구현해줘야 한다.
사용자 정의 타입일 경우 Object를 기본으로 상속받으며 Object의 equals는 아래와 같다
public boolean equals(Object obj) {
return (this == obj);
}
이는 동일성 비교로 객체의 참조값을 통해 비교연산을 수행한다.
하지만 사용자 정의 객체일 경우, "A" 인스턴스 1과 "A"인스턴스 2의 객체 참조값이 다르게 부여된다.
이럴 경우 데이터는 "A"로 동일하지만 객체의 참조값이 다르기에 해시코드의 값이 달라져 데이터 중복이 발생할 수 있다.
따라서 equals를 동일성에서 동등성 비교로 바꿔주어야 한다.
hashCode 또한 마찬가지로 기본적으로 객체의 참조값을 통해 해시코드를 반환해 준다.
이는 실 데이터가 같아도 객체의 참조값을 기준으로 하기에 다른 해시코드를 반환할 수 있다.
따라서 데이터의 값을 기준으로 해시코드가 생성되게 해시 함수를 재정의 해줘야 한다.
private String id ; // id가 같으면 해시 코드도 같다.
@Override
public int hashCode() {
return Objects.hash(id);
}
다음 시간에는 HashMap에 대해 알아보자.
3월 12일은 멘사테스트 신청기간이며 22일 날 테스트가 서울에서 치러진다.
예전 신청기간에서는 멍 때리고 있다가 신청 인원이 마감되어 아쉬웠던 기억이 있다.
실패하든 성공하든 한번 도전해 보자.