참고
Set과 해시 함수
NOTE
Set은 각 요소가 고유하며 순서를 가지고 있고, 빠른 검색이 가능한 자료구조입니다. Set은 검색에 O(1)의 시간 복잡도를 가지며, 이는 해시 함수와 해시 인덱스를 이용하여 구현할 수 있습니다.
자바는 기본적으로 배열과 같은 구조를 통해 데이터들을 관리하고 있습니다. Set의 가장 큰 특징중 하나인 조회 시간복잡도 O(1)을 구현하기 위해서는 배열에서 O(1)이 걸리는 index를 통한 조회를 사용해야 합니다. 하지만 여기서 고려해야할 문제들이 있습니다.
1.
1, 99를 저장할때 배열크기를 100으로 지정하는건 메모리 낭비가 너무 큽니다.
2.
index는 숫자 값이며, 배열에는 여러가지 타입이 올 수 있습니다.
해시 인덱스
NOTE
해시 인덱스는 값을 배열 범위 내로 분산시키기 위해 나머지 연산을 사용하는 방법을 말합니다. 입력 값의 범위가 넓어도 실제로는 모든 범위의 값이 들어오지 않으므로, 배열의 크기를 제한하고 나머지 연산을 통해 메모리 낭비 문제를 해결할 수 있습니다.
public class HashStart4 {
static final int CAPACITY = 10;
public static void main(String[] args) {
Integer[] inputArray = new Integer[CAPACITY];
add(inputArray, 1);
add(inputArray, 2);
add(inputArray, 5);
add(inputArray, 8);
add(inputArray, 14);
add(inputArray, 99);
System.out.println("inputArray = " + Arrays.toString(inputArray));
// 검색
int searchValue = 14;
int hashIndex = hashIndex(searchValue);
System.out.println("searchValue hashIndex = " + hashIndex);
Integer result = inputArray[hashIndex]; // O(1)
System.out.println(result);
}
// 추가 이전에 해시 인덱스 연산
private static void add(Integer[] inputArray, int value) {
int hashIndex = hashIndex(value);
inputArray[hashIndex] = value;
}
// 나머지 연산(배열 크기만큼)
static int hashIndex(int value) {
return value % CAPACITY;
}
}
Java
복사
valuie → hashIndex() → 저장
하지만 배열의 크기가 제한된다는건 입력이 배열의 크기를 넘어서는 순간 저장하는 위치가 충돌될 수 있는 한계가 있습니다.
•
ex) 9, 99의 두 값은 10으로 나누면 같은 9가 됩니다. (해시 충돌)
해시 충돌
NOTE
해시 충돌은 같은 해시 코드가 생성되는 경우를 의미합니다. 해시 충돌에 대한 다양한 해결 방법이 있지만, 가장 간단한 방법은 충돌이 발생했을 때 값을 함께 저장하는 것입니다.
public class HashStart5 {
static final int CAPACITY = 10;
public static void main(String[] args) {
// {1, 2, 5, 8, 14, 99}
LinkedList<Integer>[] buckets = new LinkedList[CAPACITY];
System.out.println("buckets = " + Arrays.toString(buckets));
// 해시 충돌을 방지한 버킷생성
for (int i = 0; i < CAPACITY; i++) {
buckets[i] = new LinkedList<>();
}
System.out.println("buckets = " + Arrays.toString(buckets));
add(buckets, 1);
add(buckets, 2);
add(buckets, 5);
add(buckets, 8);
add(buckets, 14);
add(buckets, 99);
add(buckets, 9);
System.out.println("buckets = " + Arrays.toString(buckets));
int search = 9;
boolean contains = contains(buckets, search);
System.out.println("buckets.contains(" + search + ") = " + contains);
}
private static void add(LinkedList<Integer>[] buckets, int value ) {
int hashIndex = hashIndex(value);
LinkedList<Integer> bucket = buckets[hashIndex]; // O(1)
// 충돌시 리스트에 추가
if (!bucket.contains(value)) {
bucket.add(value);
}
}
//
private static boolean contains(LinkedList<Integer>[] buckets, int searchValue) {
int hashIndex = hashIndex(searchValue);
LinkedList<Integer> bucket = buckets[hashIndex]; // O(1)
return bucket.contains(searchValue); // O(n)
}
private static int hashIndex(int value) {
return value % CAPACITY;
}
}
Java
복사
해시 충돌 발생시 같은 Index에 추가!
•
배열 내에 또 다른 배열이 존재합니다. 이 배열 안의 모든 값을 검색 값과 비교합니다.
•
예를 들어, [99, 9]의 데이터가 있을 경우 99.equals(9), 9.equals(9)와 같은 연산을 통해 데이터를 찾습니다.
그러나 해시 충돌의 경우 성능에 부정적인 영향을 미칩니다. 예를 들어, 9, 19, 29, 99와 같은 데이터를 저장할 경우 모든 해시 인덱스가 9가 되어 모두 9번 인덱스에 저장됩니다.
입력값의 해시인덱스가 모두 동일한 경우
•
데이터 조회시 9번 인덱스의 리스트에서 저장한 데이터만큼 값을 반복해서 비교해야 하므로 성능이 O(n)으로 떨어질 수 있습니다.
•
그러나 이러한 경우는 확률적으로 매우 드물어서 실제 해시 충돌이 발생하더라도 내부에서 값 비교를 몇 번만 수행하게 됩니다.
•
통계적으로 보면, 입력 데이터의 수가 배열 크기의 75%를 넘지 않으면 인덱스 충돌이 자주 발생하지 않습니다.
문자열 해시 코드
NOTE
hashIndex를 생성하기 위해서는 입력값이 숫자여야 합니다. 그러나 데이터는 문자열이거나 객체가 저장될 수 있습니다. 자바는 hashCode() 메서드를 사용하여 특정 객체나 문자를 고유한 숫자 값으로 변환할 수 있습니다.
public class MyHashSetV2 {
static final int DEFAULT_INITIAL_CAPACITY = 16;
LinkedList<Object>[] buckets;
private int size = 0;
private int capacity = DEFAULT_INITIAL_CAPACITY;
// 생성자
public MyHashSetV2() {
initBucket(capacity);
}
public MyHashSetV2(int capacity) {
this.capacity = capacity;
initBucket(capacity);
}
private void initBucket(int capacity) {
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;
}
}
// hashIndex(abs를 추가한 이유는 hashCode()값이 음수가 나올 수 있기떄문)
private int hashIndex(Object value) {
return Math.abs(value.hashCode()) % capacity; // -1, -100 -> 1, 100
}
public int getSize(){
return size;
}
@Override
public String toString() {
return "MyHashSetV2{" +
"buckets=" + Arrays.toString(buckets) +
", size=" + size +
", capacity=" + capacity +
'}';
}
}
Java
복사
public static void main(String[] args) {
MyHashSetV2 set = new MyHashSetV2(10);
set.add("A");
set.add("B");
set.add("C");
set.add("D");
set.add("AB");
set.add("SET");
System.out.println(set);
System.out.println("A.hashCode() = " + "A".hashCode());
System.out.println("B.hashCode() = " + "B".hashCode());
System.out.println("AB.hashCode() = " + "AB".hashCode());
System.out.println("SET.hashCode() = " + "SET".hashCode());
// 검색
String searchValue = "SET";
boolean result = set.contains(searchValue);
System.out.println("result = " + result);
}
Java
복사
•
해시 함수 - Object.hash(): 해시 함수는 임의의 길이의 데이터를 입력으로 받아, 고정된 길이의 해시값(해시 코드)을 출력하는 함수다.
◦
여기서 의미하는 고정된 길이는 저장 공간을 의미하며, int 1, 100은 둘다 4byte를 차지하는 고정된 길이를 뜻한다.
◦
자바의 hashCode()는 정수를 반환하기 때문에 마이너스 값이 나올 수 있다.
•
해시 코드: 데이터를 대표하는 값을 나타내며 보통 해시 함수를 통해 만들어 진다.
•
해시 인덱스: 데이터의 저장 위치를 결정하는데, 주로 해시 코드와 배열의 크기를 나누어 구한다.
equals(), hashCode()의 중요성
NOTE
해시 자료구조에서 hashCode()와 equals() 메서드는 반드시 재정의해야 하며, hashCode()는 해시코드 반환, equals()는 동등성 비교에 사용됩니다.
hashCode(), equals() 모두 구현하지 않은 경우
만약 객체 Member를 구현하고 id가 같은사람을 동일하다고 하고 싶은 경우, equals()와 hashCode()를 재정의하지 않으면 동일한 A를 가진 객체가 서로 다른 해시코드를 가지며 같지않다고 판단합니다.
public class MemberNoHashNoEq {
private String id;
public MemberNoHashNoEq(String id) {
this.id = id;
}
public String getId() {
return id;
}
}
Java
복사
public static void main(String[] args) {
MyHashSetV2 set = new MyHashSetV2(10);
MemberNoHashNoEq m1 = new MemberNoHashNoEq("A");
MemberNoHashNoEq m2 = new MemberNoHashNoEq("A");
// 서로 다른 hashCode를 반환한다.
System.out.println("m1.hashCode() = " + m1.hashCode());
System.out.println("m2.hashCode() = " + m2.hashCode());
System.out.println("m1.equals(m2) = " + m1.equals(m2));
// 각 Member는 다르다고 판단하고 저장된다.
set.add(m1);
set.add(m2);
System.out.println(set);
MemberNoHashNoEq searchValue = new MemberNoHashNoEq("A");
System.out.println("searchValue.hashCode() = " + searchValue.hashCode());
boolean contains = set.contains(searchValue);
System.out.println("contains = " + contains);
}
Java
복사
MyHashSetV2{buckets=[[], [], [], [], [], [], [MemberNoHashNoEq{id='A'}], [], [], [], [MemberNoHashNoEq{id='A'}], [], [], [], [], []], size=2, capacity=16}
hashCode()만 구현한 경우
hashCode()만 구현한 경우 서로 같은 해시코드를 가지므로 동일한 해시 인덱스를 가집니다. 하지만 객체의 참조값을 비교하므로 중복 객체가 저장되고 검색이 실패합니다.
public class MemberOnlyHash {
private String id;
public MemberOnlyHash(String id) {
this.id = id;
}
public String getId() {
return id;
}
@Override
public int hashCode() {
return Objects.hash(id);
}
}
Java
복사
public static void main(String[] args) {
// 중복 등록
MyHashSetV2 set = new MyHashSetV2();
set.member.MemberOnlyHash m1 = new set.member.MemberOnlyHash("A");
set.member.MemberOnlyHash m2 = new set.member.MemberOnlyHash("A");
// 서로 동일한 해시코드를 가진다.
System.out.println("m1.hashCOde() = " + m1.hashCode());
System.out.println("m2.hashCode() = " + m2.hashCode());
System.out.println("m1.equals(m2) = " + m1.equals(m2));
// 실제 해시코드 값(서로 다름)
System.out.println("System.identityHashCode(m1) = " + System.identityHashCode(m1));
System.out.println("System.identityHashCode(m2) = " + System.identityHashCode(m2));
// 추가
set.add(m1);
set.add(m2);
System.out.println(set);
// 검색 실패
set.member.MemberOnlyHash searchValue = new set.member.MemberOnlyHash("A");
System.out.println("searchValue = " + searchValue.hashCode());
boolean contains = set.contains(searchValue);
System.out.println("contains = " + contains);
}
Java
복사
MyHashSetV2{buckets=[[MemberOnlyHash{id='A'}, MemberOnlyHash{id='A'}], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []], size=2, capacity=16}
hashCode(), equals() 모두 구현한 경우
hashCode()를 사용하면 동일한 해시코드와 해시 인덱스를 가지게 됩니다. 또한 equals()를 통해 동일함을 판단하여 중복 저장을 방지하며, 이를 통해 정확하게 검색할 수 있게 됩니다.
public class Member {
private String id;
public Member(String id) {
this.id = id;
}
public String getId() {
return id;
}
public void setId(String id) {
this.id = id;
}
@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);
}
}
Java
복사
public static void main(String[] args) {
// 중복 등록
MyHashSetV2 set = new MyHashSetV2();
set.member.MemberOnlyHash m1 = new set.member.MemberOnlyHash("A");
set.member.MemberOnlyHash m2 = new set.member.MemberOnlyHash("A");
// 서로 동일한 해시코드를 가진다.
System.out.println("m1.hashCOde() = " + m1.hashCode());
System.out.println("m2.hashCode() = " + m2.hashCode());
System.out.println("m1.equals(m2) = " + m1.equals(m2));
// 실제 해시코드 값(서로 다름)
System.out.println("System.identityHashCode(m1) = " + System.identityHashCode(m1));
System.out.println("System.identityHashCode(m2) = " + System.identityHashCode(m2));
// 추가
set.add(m1);
set.add(m2);
System.out.println(set);
// 검색 성공
set.member.MemberOnlyHash searchValue = new set.member.MemberOnlyHash("A");
System.out.println("searchValue = " + searchValue.hashCode());
boolean contains = set.contains(searchValue);
System.out.println("contains = " + contains);
}
Java
복사
MyHashSetV2{buckets=[[Member{id='A'}], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []], size=1, capacity=16}