S E P H ' S
[자료구조] 15. HashSet (해시 셋) 본문
Hash
HashSet에 대해 다루기 전에 Hash에 대한 개념을 먼저 다뤄보도록 하자.
Hash는 임의의 길이를 갖는 데이터를 고정된 길이의 데이터로 변환하는 것이다.
그리고 위와 같은 기능을 하는 함수를 해시 함수(Hash Function)이라고 한다.
abcd 라는 문자열이 있다면 이를 특정 길이 (ex 256bit, 512bit 등) 의 데이터로 변환시키는 것이다.
만약 특정 길이를 32bit로 고정된다는 가정하에 아래 이미지를 보자.
32bit는 2진수일때 기준이므로, 16진수로 보자면 4bit 당 한 묶음이기 때문에 16진수로 표현하면 8개의 문자를 얻게된다. 즉 해시함수를 돌리기 전 문자열의 길이가 얼마이든지 일정한 길이를 얻는다는 것이다. 실제로 대표적인 해시함수의 SHA계열의 SHA-512는 512bit의 고정 길이를, SHA-256은 256bit의 고정된 길이로 매핑된다.
이러한 과정을 해싱(Hashing)한다고 하며 해시함수에 얻어진 값을 보통 다이제스트(digest)라고 한다. 이 해시는 왜 필요할까?
그동한 구현해온 ArrayList나 LinkedList 등 수많은 자료구조에서 '특정 값'을 찾기위해 어떻게 했는가?
배열 혹은 노드를 순회하면서 특정값의 유무를 찾아내야 했었다. 하지만 해시함수를 이용한다면 굳이 순회할 필요가 없다.
왜냐면 동일한 메시지(값)에 대해서는 동일한 다이제스트(digest)를 갖기 때문이다. 위 이미지에서 a 문자열을 hash 함수에 돌려 얻은 값이 86aff3ca이다. 이는 고정값이다. 즉 동일한 해시 알고리즘을 사용한다면 동일값에 대해 동일한 결과를 얻게 된다는 것이다.
즉, 특정값에 대한 다이제스트는 변하지 않기 때문에 이를 배열의 위치 즉 인덱스로 활용하는 것이다. 좀더 쉽게 말하자면 특정 값에 대해 배열의 특정 위치로 지정해두는 것과 같다고 보면 된다.
Set은 '중복 원소'를 허용하지 않는다 했다. 이것은 우리가 원소를 추가할 때마다 해당 원소의 중복 유무를 검사해야한다는 것이다. 그럴때마다 모든 원소를 검사한다는 것은 매우 비효율적이다.
그렇기에 고안한 방법이 hash함수를 통해 특정 값에 대한 고유의 다이제스트를 얻고 그 값에 대응하는 index를 찾아서 해당 인덱스에 있는 요소만 검사하면 되는 것이다. 이것이 HashSet의 기본 개념이다.
자바에서는 hashCode()라는 간편한 함수 덕분에 굳이 해시함수를 구현할 필요가 없다. hashCode()를 통해 객체의 주소값을 이용해 해시 알고리즘에 의해 생성된 고유의 정수값을 반환한다. 즉, 객체가 같은 메모리 주소를 가리키고 있다면 같은 정수값을 얻을 수 있다.
int a = X.hashCode();
주의할 점은 '객체가 같은 주소'를 가리킬 경우이다. 즉, 객체가 같은 내용을 지니더라도 가리키는 주소가 다르면 다른 값을 지닌다는 것이다.
public class Main {
public static void main(String[] args) {
Test a = new Test("aaa");
Test b = new Test("aaa"); // 내용이 같음
Test c = a; // 주소 복사 (shallow copy)
System.out.println("a : " + a.hashCode());
System.out.println("b : " + b.hashCode());
System.out.println("c : " + c.hashCode());
}
static class Test {
String str;
public Test(String str) {
this.str = str;
}
}
}
a 객체와 b 객체는 내용이 같더라도 서로 다른 주소에 할당된 '다른 객체'이기 때문에 다른 값이 나오고 a와 c는 같은 주소를 갖기 때문에 같은 값을 갖는다. 그래서 우리가 쓰는 String,int, double 등의 자료형들은 hashCode()를 오버라이드(Override)하여 객체 내용이 비교될 수 있도록 재정의하고 있다.
해시 충돌
위 개념말고 추가로 반드시 알아야 하는 개념이 있다. 바로 해시 충돌이다.
hashCode()를 사용하더라도 1차적 문제가 있다. 일단 int형 범위이다. int형은 32비트로 표현되는 자료형이다. 즉, 2^32의 경우의 수를 가질수 있다는 의미이다. 하지만 2^32로 모든 객체를 다 표현하기에는 한계가 있다.
설령 생성되는 객체가 우연히 모두 2^32로 표현이 가능하더라도 문제는 그만큼의 배열 공간을 생성해야한다는 점이다. 이는 메모리 낭비가 심할뿐더러 Java에서는 대략 단일 배열에 대해 약 21억 크기까지만 생성이 가능하다. 그렇기 때문에 메모리 낭비를 줄이기 위해 배열의 사이즈를 줄여서 사용한다. 예를 들어 M개의 인덱스를 갖고있는 배열(테이블)이 있을때 다음과 같이 인덱스를 지정하는 것이다.
int index = X.hashCode() % M;
이때 자바에서는 hashCode()가 음수값이 나올 수도 있다. 그렇기 때문에 절댓값으로 변환하여 양수로 변환해주는 것이 필요하다.
int index = Math.abs(X.hashCode()) % M;
위와 같이 해주더라도 해시충돌의 경우와 버킷(배열)의 크기에 따른 값은 같은 인덱스를 참조하는 일이 발생할 수 밖에 없다. 이를 해결하는 방법은 크게 두가지로 나뉜다.
위와 같이 Open Addressing 방식과 Separate Chaining 방식이 있다. 각각의 장단점은 아래와 같다.
Open Addressing
[장점]
- 해시충돌이 일어날 가능성이 적기 때문에 데이터의 개수가 작을수록 속도가 빨라진다.
- 연속된 공간에 데이터를 저장하기 때문에 캐시 효율이 좋아진다.
[단점]
- 해시충돌이 발생하면 해당 객체의 인덱스 값이 바뀌어 버린다.
- 부하율(load factor) 즉, 테이블에 저장된 데이터가 많아질수록(= 밀도가 높아질수록) 성능이 급격히 저하된다.
Separate Chaining
[장점]
- 해시충돌이 일어나더라도 연결리스트로 노드가 연결되기에 index가 변하지 않는다.
- 테이블의 각 인덱스는 연결리스트로 구현되기 때문에 데이터 개수의 제약을 거의 받지 않는다.
[단점]
- 부하율(load factor)에 따라 선형적으로 성능이 저하됨. 즉, 부하율이 작을 경우에는 Open Addressing 방식이 빠르다.
자바에서는 Separate Chaining을 적용한다. 이번에 구현할 HashSet도 Separate Chaining 방법을 적용한다.
부하율에 대해서 조금더 알아보자면 보통 데이터가 70% ~ 80% 정도 채워질 경우 성능이 저하된다고 한다. 그래서 Java에서도 load factor 값을 0.75로 두고 있다.
또한 최악의 경우 해시충돌에 의해 한개의 인덱스에 여러개의 노드가 연결될 경우도 있다. 자바 내부에서는 이럴경우 해당 인덱스의 LinkedList를 Binary Tree(이진트리)로 변환하여 데이터의 색인 속도를 높인다. 이번 포스팅에서는 LinkedList 형식으로만 연결한다.
이번에 구현할 HashSet은 다음과 같이 구현될 것이다.
Node 구현
public class Node<E> {
/*
hash 와 key 값은 변하지 않으므로 final 로 선언해준다.
*/
final int hash;
final E key;
Node<E> next;
public Node(int hash, E key, Node<E> next) {
this.hash = hash;
this.key = key;
this.next = next;
}
}
HashSet 구현
<필수목록>
- 클래스 및 생성자와 필수 메소드 구성
- add 메소드 구현
- resize 메소드 구현
- remove 메소드 구현
- size, isEmpty, contains, clear, equals 메소드 구현
<부가목록>
- toArray 구현
<필수 목록>
HashSet 클래스 및 생성자 구성
HashSet은 Node 배열 기반으로 데이터를 저장하는 방식과 같은 인덱스에 있을 경우에는 LinkedList 형식의 chain 형식을 기반으로 구현된다. HashSet이라는 이름으로 생성한다. 또한 Set Interface 포스팅에서 작성했던 Set 인터페이스를 implements 한다.
public class HashSet<E> implements SetInterface<E> {
// 최소 기본 용적이며 2^n 형태가 좋음
private final static int DEFAULT_CAPACITY = 1 << 4;
// 3/4 이상 채워질 경우 resize 하기 위함
private final static float LOAD_FACTOR = 0.75f;
Node<E>[] table; // 요소의 정보를 담고 있는 Node를 저장할 Node 타입 배열
private int size; // 요소의 개수
@SuppressWarnings("unchecked")
public HashSet() {
table = (Node<E> []) new Node[DEFAULT_CAPACITY];
size = 0;
}
// 보조 해시 함수 (상속 방지를 위해 private static final 선언)
private static final int hash(Object key) {
int hash;
if (key == null) {
return 0;
} else {
// hashCode() 의 경우 음수가 나올 수 있으므로 절댓값을 통해 양수로 변환한다.
return Math.abs(hash = key.hashCode()) ^ (hash >>> 16);
}
}
}
- DEFAULT_CAPACITY : Node 배열의 기본 및 최소 용적이다. 한마디로 요소를 담을 배열의 크기를 의미. 배열을 동적으로 관리할 때 최소 크기가 1 << 4, 즉 16 미만으로 내려가지 않기 위한 변수이다. 그리고 요소의 개수와는 다른의미이므로 주의하자.
- LOAD_FACTOR : 테이블의 크기에 비해 데이터 양이 일정 이상 많아지면 성능이 저하된다. 그 기준점을 0,75로 잡아 75%가 넘으면 배열의 용적을 늘릴 수 있도록 하는 기준 변수이다.
- size : 배열에 전체 요소(원소)의 Node 개수 변수
- table : 요소(Node)를 담을 배열이다.
보조해시 함수인 hash() 메소드는 반드시 필요한 것은 아니다. hash 함수도 고른 분포를 가질수 있게 설계되어 큰 역할을 하지는 못하지만 원래는 최대한 해시 충돌을 피하기 위해 보조해시함수를 써서 고른 분포를 할 수 있도록 하기 위한 함수가 보조해시 함수이다. Java 11의 구현과 유사하게 key의 hashCode() 의 절댓값과 그 값을 16비트 왼쪽으로 밀어낸 값과 XOR 값을 반환하도록 했다.
여기서 설명하는 모든 것은 기본적으로 table의 용적이 2^n 꼴임을 알아두자.
add 메소드 구현
사용자가 추가한 data는 key를 의미하고 이 key에 대한 hash 값을 얻어 table 배열의 위치를 지정하여 해당 위치에 노드를 추가해야 한다. 그림을 통해 살펴보도록 하자.
(각 데이터의 hash 값은 실제로 그림의 값같이 가지지 않는다.)
위 그림에서는 비교를 equals() 수준에서 했지만, 좀 더 정확히 비교하려면 다음과 같이 객체를 비교하는 것이 더 정확하다.
- hash 값이 같은가?
- 주소값이 같거나 혹은 key 객체가 같은 내용인가?
1,2번 조건을 둘다 만족해야 추가할 수 있도록 하는 것이 더 정확하다.
public boolean add(E e) {
// key(e) 에 대해 만들어뒀던 보조해시함수의 값과 key(데이터 e)를 보낸다.
return add(hash(e), e) == null;
}
private E add(int hash, E key) {
int idx = hash % table.length;
// table[idx] 가 비어있을 경우 새 노드 생성
if (table[idx] == null) {
table[idx] = new Node<E>(hash, key, null);
}
/*
* table[idx]에 요소가 이미 존재할 경우 (==해시 충돌)
*
* 두 가지 경우의 수 존재
* 1. 객체가 같은 경우
* 2. 객체는 같지 않으나 얻어진 index 가 같은 경우
*/
else {
Node<E> temp = table[idx]; // 현재 위치 노드
Node<E> prev = null; // temp 의 이전 노드
// 첫 노드(table[idx]) 부터 탐색
while (temp != null) {
/*
* 만약 현재 노드의 객체가 같은 경우 (hash 값이 같으면서 key 가 같은 경우)는
* HashSet 은 중복을 허용하지 않으므로 key 를 반환한다.
* (key 가 같은 경우는 주소가 같거나 객체가 같은 경우가 존재)
*/
if ((temp.hash == hash) && (temp.key == key || temp.key.equals(key))) {
return key;
}
prev = temp;
temp = temp.next; // 다음 노드로 이동
}
// 마지막 노드에 새 노드를 연결
prev.next = new Node<E>(hash, key, null);
}
size++;
// 데이터 개수가 현재 table 용적의 75%를 넘는다면 용적을 늘려준다.
if (size >= LOAD_FACTOR * table.length) {
resize();
}
return null; // 정상적으로 추가 되었을 경우 null 반환
}
resize 메소드 구현
모든 자료구조는 동적 할당을 할 줄 알아야 한다. 동적 할당이 아닌 고정된 크기에 데이터를 넣는다면 메모리 관리도 좋지 못하고 특히나 HashSet에서는 해시 충돌을 최소화 해야하기 때문에 고정 배열크기에 데이터를 많이 추가될 수록 빠른 색인이라는 HashSet의 장점을 찾아볼 수 없게 된다.
그렇기 때문에 일정 이상 데이터가 차면 배열을 늘려서 재배치하는 것이 성능에서 우월하다. 용적 대비 데이터 개수의 비율을 부하율(load factor)이라고 했고 이 기준점을 75% 즉 0.75로 잡았다.
resize 메소드는 크게 두 가지 방식으로 구현된다.
가장 보편적 방식, 다른 하나는 용적이 2^n 꼴로 표현된다면 수학, 논리연산 지식을 응용하여 매우 획기적으로 재배치할 수 있는 방법이 있다.
기본적으로는 resize()를 할 경우 현재 용적의 두 배로 늘려주면 된다. 일단 Node배열을 하나 새로 생성하고 기존 테이블의 있는 모든 요소들을 탐색하며 각 노드의 hash 값을 이용해 새로 만든 배열의 길이로 나눈 나머지를 구해 재배치를 하는 것이다.
각 인덱스별로 순회하되, 해당 인덱스의 연결된 노드를 우선적으로 탐색하면서 재배치를 해주면 된다.
위 과정을 코드로 옮기면 다음과 같다.
@SuppressWarnings("unchecked")
private void resize() {
int newCapacity = table.length * 2;
// 기존 테이블의 두배 용적으로 생성
final Node<E>[] newTable = (Node<E>[]) new Node[newCapacity];
// 0번째 인덱스부터 차례대로 순회
for (int i = 0; i < table.length; i++) {
// 각 인덱스의 첫번째 노드(head)
Node<E> value = table[i];
// 해당 값이 없을 경우 다음으로 넘어간다
if (value == null) {
continue;
}
table[i] = null; // gc
Node<E> nextNode; // 현재 노드의 다음 노드를 가리키는 변수
// 현재 인덱스에 연결된 노드들을 순회한다.
while(value != null) {
int idx = value.hash % newCapacity; // 새로운 인덱스를 구한다.
/*
* 새로 담을 index 에 요소가 존재할 경우
* == 새로 담을 newTable 에 index 값이 겹칠 경우 (해시 충돌)
*/
if (newTable[idx] != null) {
Node<E> tail = newTable[idx];
// 가장 마지막 노드로 간다.
while (tail.next != null) {
tail = tail.next;
}
/*
* 반드시 Value 가 참조하고 있는 다음 노드와의 연결을 끊어줘야 한다.
* 그렇지 않으면 각 인덱스의 마지막 노드(tail)도 다른 노드를 참조하여 잘못된 참조 발생가능성이 있다.
*/
nextNode = value.next;
value.next = null;
tail.next = value;
}
// 충돌되지 않는다면 ( 빈공간이라면 해당 노드를 추가 )
else {
/*
* 반드시 Value 가 참조하고 있는 다음 노드와의 연결을 끊어줘야 한다.
* 그렇지 않으면 각 인덱스의 마지막 노드(tail)도 다른 노드를 참조하여 잘못된 참조 발생가능성이 있다.
*/
nextNode = value.next;
value.next = null;
newTable[idx] = value;
}
value = nextNode; // 다음 노드로 이동
}
}
table = null;
table = newTable; // 새로 생성한 table 을 table 변수에 연결
}
주의할 점은 새로운 테이블(newTable)에 변수를 담을때 new Node<E>(value.hash, value.key, null) 로 담으면 안된다. 만약에 사용자 클래스에서 hashCode()를 오버라이드를 정확하게 하면 문제가 되지 않으나 그렇지 않았다면 기본적으로 메모리 주소에 대한 해싱 값을 반환한다고 했다.
즉, value 자체에 담고 있던 hash값과 new Node()로 생성된 새로운 노드는 내용은 같을지라도 hashCode() 값은 달라져 버린다. 그렇기에 value가 참조하고 있는 Node 자체를 담는 것이 안전하다.
대신에 고려할 것은 value를 그대로 연결하기 때문에 value에 연결되어 있는 next 노드 또한 그대로 딸려오는 문제가 발생할 수 있다. 재배치 되는 idx가 다음노드와 같다면 문제는 없겠으나 이미지에서도 확인해보면 반드시 그럴것이라는 보장이 없다. 그렇기 때문에 value.next 연결 링크를 끊어주고 넣어야 정상적으로 연결할 수 있다.
[2^n 꼴로 고정된 형태의 용적을 사용하는 경우 resize()]
각 요소들은 용적의 크기로 나눈 나머지를 이용했다. 이말은 곧 배열의 용적을 2배로 늘릴 때, 요소가 재배치되는 인덱스는 둘중 하나이다. 예시를 살펴보자
기존 용적 : 8, 새로운 용적 : 8 * 2 = 16
9 % 8 = 1 index -> 9 % 16 = 9 index
17 % 8 = 1 index -> 17 % 16 = 1 index
25 % 8 = 1 index -> 25 % 16 = 9 index
33 % 8 = 1 index -> 33 % 16 = 1 index
기존 8로 나눈 나머지는 모두 1로 동일했지만 그 용적을 두 배로 늘리게 된다면 1 or 9로 즉 원래 자리이거나 원래 자리 + 이전 용적(1 + 8) 이 된다는 사실을 알 수 있다.
다른 케이스도 마찬가지이다.
10 % 8 = 2 index -> 10 % 16 -> 10 index
18 % 8 = 2 index -> 18 % 16 -> 2 index
26 % 8 = 2 index -> 26 % 16 -> 10 index
34 % 8 = 2 index -> 34 % 16 -> 2 index
즉, 용적을 두배로 늘리게 되면 두 가지 경우 중 하나에 배치된다.
1. 원래 자리(현재 자리)에 그대로 배치
2. 원래 자리 + 이전용적을 더한 값 만큼의 위치에 배치
이미지로 보자면 아래와 같다.
용적을 두배 늘릴때, 기존 인덱스는 두 개의 특정 인덱스로 위치하게 되는 것이다.
그러면 어떻게 위치를 특정해야 할까?
맨 처음 나왔던 방법인 용적을 나누는 방법(hash % capacity)과 비트 연산을 이용하는 방법이 있다.
하지만 비트 연산은 2^n 꼴에서만 유효하므로 그 외의 용적에서는 비트 연산 대신 나머지 연산으로 해야한다.
위 이미지에서 배치되는 곳이 두 곳으로 특정된다는 것을 확인할 수 있다.
이때 제자리에 배치되는 경우를 low 라고 하고 제자리 + 이전 용적 크기 값의 위치 즉 높은 인덱스에 배치되는 경우를 high라고 나눠보도록 한다.
기존 용적 : 8, 새로운 용적 : 16
(hash % capacity)
9 % 8 = 1 index -> 9 % 16 = 9 index (high)
17 % 8 = 1 index -> 17 % 16 = 1 index (low)
25 % 8 = 1 index -> 25 % 16 = 9 index (high)
33 % 8 = 1 index -> 33 % 16 = 1 index (low)
여기서 high에 배치되는 경우는 어떤 경우일까?
바로 hash를 기존 용적으로 나눴을 때 몫이 홀수가 되는 경우이다.
2진수로 생각하여 비트연산으로 계속 알아보자. 8의 몫이 홀수가 된다는 것은 무슨 의미일까?
2진법을 10진법으로 변환할 때 보통 다음과 같이 계산한다.
0000 1011(2) = 2^0 + 2^1 + 2^3 = 1 + 2 + 8 = 11
각 자리수는 2^n 값이다.
이때 4는 2^2(0000 0100)이다. 다음부터 2^3 (0000 1000), 2^4 (0001 0000) 모두 2배씩 증가하면서 4의 짝수 배수가 된다. 이 것은 짝수 배수끼리 더해도 4로 나눈 몫은 항상 짝수가 나올수 밖에 없는 것이다. 즉, 4의 몫이 홀수가 된다는 것은 어떻게 되더라도 세 번째 비트가 1이어야 한다는 것이다. 0100 형태여야 한다는 것이다.
우리는 기본 용적을 8(1000)로 두었다. 그렇다는 것은 이 8을 나눴을 때 몫이 홀수가 되는 경우가 high index에 배치된다는 것이고 8이라함은 네번째 비트가 1인 경우만 체크하면 된다는 것이다. 좀더 범용적으로 말한다면 2^n꼴인 용적을 사용하는 경우 기본 용적 2^n 자리의 비트 수가 1인 경우만 체크하면 된다. 다시 예시를 들어보자.
앞서 기본 용적 8을 16으로 늘렸다. 구해야할 것은 기존 인덱스에서 8로 나눈 몫이 짝수인지 홀수인지에 따라 high, low index가 결정된다.
기존 용적 : 8, 새로운 용적 : 16
(hash % capacity)
9(0000 1001) % 8 = 1 index -> 9 % 16 = 9 index(high)
17(0001 0001) % 8 = 1 index -> 17 % 16 = 1 index(low)
25(0001 1001) % 8 = 1 index -> 25 % 16 = 9 index(high)
33(0010 0001) % 8 = 1 index -> 33 % 16 = 1 index(low)
기존 용적인 8을 가리키는 비트가 1인지 아닌지만 판별하면 high, low index 배치를 알 수 있게 되고 결과적으로 다음과 같이 바꿔 연산할 수 있다.
(hash & oldCapacity == 0) -> 기존 index 그대로 == low
(hash & oldCapcity != 0) -> (기존 index + oldCapacity) == high
9(0000 1001) & 8(0000 1000) = 8(0000 1000) -> 9(1+ 8) index(high)
17(0001 0001) & 8(0000 1000) = 0(0000 0000) -> 1 index(low)
25(0001 1001) & 8(0000 1000) = 8(0000 1000) -> 9(1+8) index(high)
33(0010 0001) & 8(0000 1000) = 0(0000 0000) -> 1 index(low)
기존에 사용했던 이미지를 바탕으로 2^n 꼴의 resize 과정 또한 이미지로 확인해보자
이러한 방식으로 각 인덱스 별로 low 와 high를 나누어 해당 노드들을 한번에 추가하는 방법이 있다. 코드는 다음과 같다.
@SuppressWarnings("unchecked")
private void resize_use_bit_op() {
int oldCapacity = table.length; // 기존 용적
int newCapacity = oldCapacity << 1; // 새용적
final Node<E> [] newTable = (Node<E> []) new Node[newCapacity];
for (int i = 0; i < oldCapacity; i++) {
Node<E> data = table[i];
if (data == null) continue;
table[i] = null; // gc
// 데이터에 다음 노드가 없을 경우 (== 하나만 있을 경우)
if (data.next == null) {
/*
== data.hash % newCapacity
2^n 으로 인해 000..0100..00 에서 =1을 한 0001..0011..11 꼴로 만든 뒤
AND 연산에 의해 나머지 값이 구해짐
*/
newTable[data.hash & (newCapacity - 1)] = data;
continue;
}
// 데이터가 두 개 이상 연결되어 있을 경우
// 제자리 배치되는 노드(연결리스트)
Node<E> lowHead = null;
Node<E> lowTail = null;
// 새로 배치되는 노드(연결리트스)
Node<E> highHead = null;
Node<E> highTail = null;
/*
재배치되는 노드는 원래 자리에 그대로 있거나
원래 자리에 새로 늘어난 크기 만큼의 자리에 배치되거나 둘 중 하나이다.
ex) oldCapacity = 4, newCapacity = 8
만약 데이터가 index 2 에 위치했다고 하면
* oldTable -> index_of_data = 2
사이즈가 두 배 늘어 새로운 테이블에 배치될 경우 두 가지 중 하나이다
newTable -> index_of_data = 2 or 6 (2 + oldCapacity)
*/
Node<E> next; // 다음 노드를 가리키는 노드
// 해당 인덱스에 연결된 모든 노드를 탐색
do {
next = data.next;
// oldCapacity 의 몫이 짝수일 경우 == low 에 배치됨
if ((data.hash & oldCapacity) == 0) {
// low 에 처음 배치되는 노드일 경우 해당 노드를 head 로 둔다.
if (lowHead == null) lowHead = data;
else lowTail.next = data;
lowTail = data; // lowTail = lowTail.next 와 같은 의미
}
/*
data.hash & oldCapacity != 0
oldCapacity = 4, newCapacity = 8 이고 재배치 하려는 index 가 2라면
2 or 6 에 위치하게 된다.
이때, 6에 위치하는 경우는 재배치 하기 전의 이전 사이즈였던 4에 대해
n % 4 = 2 이었을 때, n % 8 = 6 이 된다는 의미이다.
쉽게 말해 4로 나눈 몫이 홀수일 경우이다.
비트로 생각하면 4에 대응하는 비트가 1인 경우이다.
ex)
hash = 45 -> 0010 1101 (2)
oldCap = 4 -> 0000 0100 (2)
newCap = 8 -> 0000 1000 (2)
재배치 이전 index = (hash & (oldCap - 1))
0010 1101 (2) - 0000 0011(2) = 0000 0001(2) = index 1
재배치 이후 index = (hash & (newCap - 1))
0010 1101 (2) - 0000 0111(2) = 0000 0101(2) = index 5
2진법으로 볼때 새로운 위치에 배치되는 경우는
hash & oldCap = 0010 1101(2) & 0000 0100(2)
= 0000 0100(2) 로 0이 아닌 경우이다.
*/
else {
// high 에 처음 배치된다면 해당 노드가 head를 가리키도록 한다.
if (highHead == null) highHead = data;
else highTail.next = data;
highTail = data;
}
data = next; // 다음 노드로 넘어간다.
} while (data != null);
/*
low 가 존재할 경우 low 의 head 를 원래 인덱스에 그대로 담아준다.
이때 tail 에 해당되는 노드가 참조하고 있는 다음 노드와의 연결을 끊어야 한다.
그렇지 않으면 각 인덱스의 마지막 노드(tail)도 다른 노드를 참조하게 되어 잘못된 참조가 발생할 수 있다.
*/
if (lowTail != null) {
lowTail.next = null;
newTable[i] = lowHead;
}
/*
high 가 존재할 경우 high 의 head 를 (원래 인덱스 + 이전 용적) 값에 담아준다.
이때 tail 에 해당되는 노드가 참조하고 있는 다음 노드와의 연결을 끊어야 한다.
그렇지 않으면 각 인덱스의 마지막 노드(tail)도 다른 노드를 참조하게 되어 잘못된 참조가 발생할 수 있다.
*/
if (highTail != null) {
highTail.next = null;
newTable[i + oldCapacity] = highHead;
}
}
table = newTable; // 새 테이블을 연결해준다.
}remove 메소드 구현
삭제 및 반환은 삽입할 때의 기존의 요소와 중복되는지를 검색했던 방식 그대로이다.
다만 마지막에 원소를 추가하는 것이 아닌 삭제를 하는 것 뿐이다. 그림으로 확인해보자.
위와 같이 index를 찾고 해당 객체 내용이 같다면 해당 노드에 연결된 링크를 모두 끊고 그 앞과 뒤 노드끼리 서로 연결하면 된다.
앞, 뒤 노드를 연결하기 위해서는 위 이미지처럼 prev 변수를 하나 두고 쓰는 것이 편리하다.
@Override
public boolean remove(Object o) {
// null 이 아니라는 것은 노드가 삭제되었다는 의미다.
return remove(hash(o), o) != null;
}
private Object remove(int hash, Object key) {
int idx = hash % table.length;
Node<E> node = table[idx];
Node<E> removedNode = null;
Node<E> prev = null;
if (node == null) {
return null;
}
while (node != null) {
// 같은 노드를 찾았다면
if (node.hash == hash && (node.key == key || node.key.equals(key))) {
removedNode = node; // 삭제되는 노드를 반환하기 위해 담아둔다.
// 해당노드의 이전 노드가 존재하지 않는 경우 ( = head 노드인 경우)
if (prev == null) {
table[idx] = node.next;
node = null;
}
// 그 외엔 이전 노드의 next 를 삭제할 노드의 다음노드와 연결해준다.
else {
prev.next = node.next;
node = null;
}
size--;
break; // 삭제되었기 때문에 탐색 종료
}
prev = node;
node = node.next;
}
return removedNode;
}위와 같이 삭제 과정을 진행하면 된다. 만약 while() 문에 같은 요소가 존재하지 않으면 removedNode 는 결국 null을 반환한다.
즉, 삭제할 노드가 없다면 null을 반환함으로써 상위 메소드에서 false를 반환하고 삭제할 노드가 있을 경우 null 이 아니기 때문에 true를 반환하는 원리이다.
size, isEmpty, contains, clear, equals 메소드 구현
현재 HashSet에 저장된 요소의 개수를 알고 싶을 때 size 값을 리턴하기 위한 메소드로 size(), 해당 HashSet이 비어있는 상태인지를 확인하는 isEmpty() 메소드를 만든다. 또한 contains로 찾고자 하는 요소(key)가 HashSet에 존재하는지 볼 수 있도록 간단히 구현하고 현재 HashSet 객체와 파라미터로 주어지는 HashSet 객체가 같은지를 판별해주는 메소드인 equals도 작성해보도록 할 것이다.
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean contains(Object o) {
int idx = hash(o) % table.length;
Node<E> temp = table[idx];
/*
같은 객체 내용이어도 hash 값은 다를 수 있다.
하지만, 내용이 같은지를 알아보고 싶을 때 쓰는 메소드이므로
hash 값은 따로 비교 하지 않아도 큰 지장은 없다.
단 o 가 null 인지는 확인해야 한다.
*/
while (temp != null) {
// 같은 객체를 찾았을 경우 true 리턴
if (o == temp.key || (o != null && (o.equals(temp.key)))) {
return true;
}
temp = temp.next;
}
return false;
}
@Override
public void clear() {
if (table != null && size > 0) {
for (int i = 0; i < table.length; i++) {
table[i] = null; // 모든 노드 삭제
}
size = 0;
}
}
@SuppressWarnings("unchecked")
@Override
public boolean equals(Object o) {
// 만약 파라미터 객체가 현재 객체와 동일하다면 true
if (o == this) {
return true;
}
// 만약 o 객체가 HashSet 이 아닌 경우 false
if (!(o instanceof HashSet)) {
return false;
}
HashSet<E> oSet;
/*
Object 로부터 HashSet<E>로 캐스팅 되어야 비교가 가능하기 때문에
만약 캐스팅이 불가능할 경우 ClassCastException 이 발생한다.
이 경우 false 를 return 하도록 try-catch 문을 사용한다.
*/
try {
// HashSet 타입으로 캐스팅
oSet = (HashSet<E>) o;
// 사이즈(요소 개수)가 다르다는 것은 명백히 다른 객체다.
if (oSet.size() != size) {
return false;
}
for (int i = 0; i < oSet.table.length; i++) {
Node<E> oTable = oSet.table[i];
while (oTable != null) {
/*
서로 Capacity 가 다를 수 있기 때문에 index 에 연결된 원소들을
비교하는 것이 아닌 contains 로 원소의 존재 여부를 먼저 확인해야 한다.
*/
if (!contains(oTable)) {
return false;
}
oTable = oTable.next;
}
}
} catch (ClassCastException e) {
return false;
}
// 위 검사가 모두 완료되면 같은 객체임이 증명됨
return true;
}
<부가 목록>
toArray 메소드 구현
public Object[] toArray() {
if (table == null) return null;
Object[] ret = new Object[size];
int index = 0;
for (int i = 0; i < table.length; i++) {
Node<E> node = table[i];
// 해당 인덱스에 연결된 모든 노드를 하나씩 담는다.
while (node != null) {
ret[index] = node.key;
index++;
node = node.next;
}
}
return ret;
}
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
Object[] copy = toArray(); // toArray()를 통해 먼저 배열을 얻는다.
// 들어온 배열이 copy 된 요소 개수보다 작을 경우 size 에 맞게 늘려주면서 복사한다.
if (a.length < size) {
return (T[]) Arrays.copyOf(copy, size, a.getClass());
}
// 그 외에는 copy 배열을 a 에 0번째부터 채운다.
System.arraycopy(copy, 0, a, 0, size);
return a;
}전체 코드
package Z_DataStructure.Set.HashSet;
import Z_DataStructure.A_InterfaceForm.SetInterface;
import java.util.Arrays;
public class HashSet<E> implements SetInterface<E> {
// 최소 기본 용적이며 2^n 형태가 좋음
private final static int DEFAULT_CAPACITY = 1 << 4;
// 3/4 이상 채워질 경우 resize 하기 위함
private final static float LOAD_FACTOR = 0.75f;
Node<E>[] table; // 요소의 정보를 담고 있는 Node를 저장할 Node 타입 배열
private int size; // 요소의 개수
@SuppressWarnings("unchecked")
public HashSet() {
table = (Node<E> []) new Node[DEFAULT_CAPACITY];
size = 0;
}
// 보조 해시 함수 (상속 방지를 위해 private static final 선언)
private static final int hash(Object key) {
int hash;
if (key == null) {
return 0;
} else {
// hashCode() 의 경우 음수가 나올 수 있으므로 절댓값을 통해 양수로 변환한다.
return Math.abs(hash = key.hashCode()) ^ (hash >>> 16);
}
}
public boolean add(E e) {
// key(e) 에 대해 만들어뒀던 보조해시함수의 값과 key(데이터 e)를 보낸다.
return add(hash(e), e) == null;
}
private E add(int hash, E key) {
int idx = hash % table.length;
// table[idx] 가 비어있을 경우 새 노드 생성
if (table[idx] == null) {
table[idx] = new Node<E>(hash, key, null);
}
/*
* table[idx]에 요소가 이미 존재할 경우 (==해시 충돌)
*
* 두 가지 경우의 수 존재
* 1. 객체가 같은 경우
* 2. 객체는 같지 않으나 얻어진 index 가 같은 경우
*/
else {
Node<E> temp = table[idx]; // 현재 위치 노드
Node<E> prev = null; // temp 의 이전 노드
// 첫 노드(table[idx]) 부터 탐색
while (temp != null) {
/*
* 만약 현재 노드의 객체가 같은 경우 (hash 값이 같으면서 key 가 같은 경우)는
* HashSet 은 중복을 허용하지 않으므로 key 를 반환한다.
* (key 가 같은 경우는 주소가 같거나 객체가 같은 경우가 존재)
*/
if ((temp.hash == hash) && (temp.key == key || temp.key.equals(key))) {
return key;
}
prev = temp;
temp = temp.next; // 다음 노드로 이동
}
// 마지막 노드에 새 노드를 연결
prev.next = new Node<E>(hash, key, null);
}
size++;
// 데이터 개수가 현재 table 용적의 75%를 넘는다면 용적을 늘려준다.
if (size >= LOAD_FACTOR * table.length) {
resize();
}
return null; // 정상적으로 추가 되었을 경우 null 반환
}
@SuppressWarnings("unchecked")
private void resize() {
int newCapacity = table.length * 2;
// 기존 테이블의 두배 용적으로 생성
final Node<E>[] newTable = (Node<E>[]) new Node[newCapacity];
// 0번째 인덱스부터 차례대로 순회
for (int i = 0; i < table.length; i++) {
// 각 인덱스의 첫번째 노드(head)
Node<E> value = table[i];
// 해당 값이 없을 경우 다음으로 넘어간다
if (value == null) {
continue;
}
table[i] = null; // gc
Node<E> nextNode; // 현재 노드의 다음 노드를 가리키는 변수
// 현재 인덱스에 연결된 노드들을 순회한다.
while(value != null) {
int idx = value.hash % newCapacity; // 새로운 인덱스를 구한다.
/*
* 새로 담을 index 에 요소가 존재할 경우
* == 새로 담을 newTable 에 index 값이 겹칠 경우 (해시 충돌)
*/
if (newTable[idx] != null) {
Node<E> tail = newTable[idx];
// 가장 마지막 노드로 간다.
while (tail.next != null) {
tail = tail.next;
}
/*
* 반드시 Value 가 참조하고 있는 다음 노드와의 연결을 끊어줘야 한다.
* 그렇지 않으면 각 인덱스의 마지막 노드(tail)도 다른 노드를 참조하여 잘못된 참조 발생가능성이 있다.
*/
nextNode = value.next;
value.next = null;
tail.next = value;
}
// 충돌되지 않는다면 ( 빈공간이라면 해당 노드를 추가 )
else {
/*
* 반드시 Value 가 참조하고 있는 다음 노드와의 연결을 끊어줘야 한다.
* 그렇지 않으면 각 인덱스의 마지막 노드(tail)도 다른 노드를 참조하여 잘못된 참조 발생가능성이 있다.
*/
nextNode = value.next;
value.next = null;
newTable[idx] = value;
}
value = nextNode; // 다음 노드로 이동
}
}
table = null;
table = newTable; // 새로 생성한 table 을 table 변수에 연결
}
@SuppressWarnings("unchecked")
private void resize_use_bit_op() {
int oldCapacity = table.length; // 기존 용적
int newCapacity = oldCapacity << 1; // 새용적
final Node<E> [] newTable = (Node<E> []) new Node[newCapacity];
for (int i = 0; i < oldCapacity; i++) {
Node<E> data = table[i];
if (data == null) continue;
table[i] = null; // gc
// 데이터에 다음 노드가 없을 경우 (== 하나만 있을 경우)
if (data.next == null) {
/*
== data.hash % newCapacity
2^n 으로 인해 000..0100..00 에서 =1을 한 0001..0011..11 꼴로 만든 뒤
AND 연산에 의해 나머지 값이 구해짐
*/
newTable[data.hash & (newCapacity - 1)] = data;
continue;
}
// 데이터가 두 개 이상 연결되어 있을 경우
// 제자리 배치되는 노드(연결리스트)
Node<E> lowHead = null;
Node<E> lowTail = null;
// 새로 배치되는 노드(연결리트스)
Node<E> highHead = null;
Node<E> highTail = null;
/*
재배치되는 노드는 원래 자리에 그대로 있거나
원래 자리에 새로 늘어난 크기 만큼의 자리에 배치되거나 둘 중 하나이다.
ex) oldCapacity = 4, newCapacity = 8
만약 데이터가 index 2 에 위치했다고 하면
* oldTable -> index_of_data = 2
사이즈가 두 배 늘어 새로운 테이블에 배치될 경우 두 가지 중 하나이다
newTable -> index_of_data = 2 or 6 (2 + oldCapacity)
*/
Node<E> next; // 다음 노드를 가리키는 노드
// 해당 인덱스에 연결된 모든 노드를 탐색
do {
next = data.next;
// oldCapacity 의 몫이 짝수일 경우 == low 에 배치됨
if ((data.hash & oldCapacity) == 0) {
// low 에 처음 배치되는 노드일 경우 해당 노드를 head 로 둔다.
if (lowHead == null) lowHead = data;
else lowTail.next = data;
lowTail = data; // lowTail = lowTail.next 와 같은 의미
}
/*
data.hash & oldCapacity != 0
oldCapacity = 4, newCapacity = 8 이고 재배치 하려는 index 가 2라면
2 or 6 에 위치하게 된다.
이때, 6에 위치하는 경우는 재배치 하기 전의 이전 사이즈였던 4에 대해
n % 4 = 2 이었을 때, n % 8 = 6 이 된다는 의미이다.
쉽게 말해 4로 나눈 몫이 홀수일 경우이다.
비트로 생각하면 4에 대응하는 비트가 1인 경우이다.
ex)
hash = 45 -> 0010 1101 (2)
oldCap = 4 -> 0000 0100 (2)
newCap = 8 -> 0000 1000 (2)
재배치 이전 index = (hash & (oldCap - 1))
0010 1101 (2) - 0000 0011(2) = 0000 0001(2) = index 1
재배치 이후 index = (hash & (newCap - 1))
0010 1101 (2) - 0000 0111(2) = 0000 0101(2) = index 5
2진법으로 볼때 새로운 위치에 배치되는 경우는
hash & oldCap = 0010 1101(2) & 0000 0100(2)
= 0000 0100(2) 로 0이 아닌 경우이다.
*/
else {
// high 에 처음 배치된다면 해당 노드가 head를 가리키도록 한다.
if (highHead == null) highHead = data;
else highTail.next = data;
highTail = data;
}
data = next; // 다음 노드로 넘어간다.
} while (data != null);
/*
low 가 존재할 경우 low 의 head 를 원래 인덱스에 그대로 담아준다.
이때 tail 에 해당되는 노드가 참조하고 있는 다음 노드와의 연결을 끊어야 한다.
그렇지 않으면 각 인덱스의 마지막 노드(tail)도 다른 노드를 참조하게 되어 잘못된 참조가 발생할 수 있다.
*/
if (lowTail != null) {
lowTail.next = null;
newTable[i] = lowHead;
}
/*
high 가 존재할 경우 high 의 head 를 (원래 인덱스 + 이전 용적) 값에 담아준다.
이때 tail 에 해당되는 노드가 참조하고 있는 다음 노드와의 연결을 끊어야 한다.
그렇지 않으면 각 인덱스의 마지막 노드(tail)도 다른 노드를 참조하게 되어 잘못된 참조가 발생할 수 있다.
*/
if (highTail != null) {
highTail.next = null;
newTable[i + oldCapacity] = highHead;
}
}
table = newTable; // 새 테이블을 연결해준다.
}
@Override
public boolean remove(Object o) {
// null 이 아니라는 것은 노드가 삭제되었다는 의미다.
return remove(hash(o), o) != null;
}
private Object remove(int hash, Object key) {
int idx = hash % table.length;
Node<E> node = table[idx];
Node<E> removedNode = null;
Node<E> prev = null;
if (node == null) {
return null;
}
while (node != null) {
// 같은 노드를 찾았다면
if (node.hash == hash && (node.key == key || node.key.equals(key))) {
removedNode = node; // 삭제되는 노드를 반환하기 위해 담아둔다.
// 해당노드의 이전 노드가 존재하지 않는 경우 ( = head 노드인 경우)
if (prev == null) {
table[idx] = node.next;
node = null;
}
// 그 외엔 이전 노드의 next 를 삭제할 노드의 다음노드와 연결해준다.
else {
prev.next = node.next;
node = null;
}
size--;
break; // 삭제되었기 때문에 탐색 종료
}
prev = node;
node = node.next;
}
return removedNode;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean contains(Object o) {
int idx = hash(o) % table.length;
Node<E> temp = table[idx];
/*
같은 객체 내용이어도 hash 값은 다를 수 있다.
하지만, 내용이 같은지를 알아보고 싶을 때 쓰는 메소드이므로
hash 값은 따로 비교 하지 않아도 큰 지장은 없다.
단 o 가 null 인지는 확인해야 한다.
*/
while (temp != null) {
// 같은 객체를 찾았을 경우 true 리턴
if (o == temp.key || (o != null && (o.equals(temp.key)))) {
return true;
}
temp = temp.next;
}
return false;
}
@Override
public void clear() {
if (table != null && size > 0) {
for (int i = 0; i < table.length; i++) {
table[i] = null; // 모든 노드 삭제
}
size = 0;
}
}
@SuppressWarnings("unchecked")
@Override
public boolean equals(Object o) {
// 만약 파라미터 객체가 현재 객체와 동일하다면 true
if (o == this) {
return true;
}
// 만약 o 객체가 HashSet 이 아닌 경우 false
if (!(o instanceof HashSet)) {
return false;
}
HashSet<E> oSet;
/*
Object 로부터 HashSet<E>로 캐스팅 되어야 비교가 가능하기 때문에
만약 캐스팅이 불가능할 경우 ClassCastException 이 발생한다.
이 경우 false 를 return 하도록 try-catch 문을 사용한다.
*/
try {
// HashSet 타입으로 캐스팅
oSet = (HashSet<E>) o;
// 사이즈(요소 개수)가 다르다는 것은 명백히 다른 객체다.
if (oSet.size() != size) {
return false;
}
for (int i = 0; i < oSet.table.length; i++) {
Node<E> oTable = oSet.table[i];
while (oTable != null) {
/*
서로 Capacity 가 다를 수 있기 때문에 index 에 연결된 원소들을
비교하는 것이 아닌 contains 로 원소의 존재 여부를 먼저 확인해야 한다.
*/
if (!contains(oTable)) {
return false;
}
oTable = oTable.next;
}
}
} catch (ClassCastException e) {
return false;
}
// 위 검사가 모두 완료되면 같은 객체임이 증명됨
return true;
}
public Object[] toArray() {
if (table == null) return null;
Object[] ret = new Object[size];
int index = 0;
for (int i = 0; i < table.length; i++) {
Node<E> node = table[i];
// 해당 인덱스에 연결된 모든 노드를 하나씩 담는다.
while (node != null) {
ret[index] = node.key;
index++;
node = node.next;
}
}
return ret;
}
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
Object[] copy = toArray(); // toArray()를 통해 먼저 배열을 얻는다.
// 들어온 배열이 copy 된 요소 개수보다 작을 경우 size 에 맞게 늘려주면서 복사한다.
if (a.length < size) {
return (T[]) Arrays.copyOf(copy, size, a.getClass());
}
// 그 외에는 copy 배열을 a 에 0번째부터 채운다.
System.arraycopy(copy, 0, a, 0, size);
return a;
}
}정리
Hash의 개념과 Set 개념까지 더해져서 내용이 매우 길었던 느낌이다. 기본적으로 처음부터 개념을 다잡아가는 과정에서 좋은 경험이었다고 생각한다. 하나 주의해야할 점은 만약 사용자 클래스를 만들게 된다면 hashCode()와 equals를 재정의해야한다. 그렇지 아니면 정확한 객체간 비교가 되지 않는다.
'Programing & Coding > Data Structure' 카테고리의 다른 글
| [자료구조] 17. Linked Hash Set (연결 해시 셋) (0) | 2023.07.19 |
|---|---|
| [자료구조] 16. 해시 충돌 (0) | 2023.07.17 |
| [자료구조] 14. Java 셋 인터페이스 (Set Interface) (0) | 2023.07.13 |
| [자료구조] 13. 세그먼트 트리(Segment Tree) (0) | 2023.06.29 |
| [자료구조] 12. 우선순위 큐(Priority Queue) (0) | 2023.04.13 |
