Notice
Recent Posts
Recent Comments
Link
S E P H ' S
[자료구조] 17. Linked Hash Set (연결 해시 셋) 본문
Programing & Coding/Data Structure
[자료구조] 17. Linked Hash Set (연결 해시 셋)
yoseph0310 2023. 7. 19. 16:47Linked Hash Set
HashSet 자체는 순서를 보장하지 않는다. 이번에는 입력 순서를 보장하는 LinkedHashSet을 알아볼 것이다.
이전에 구현했던 LinkedList와 HashSet의 특성을 같이 갖는 자료구조이다.
HashSet을 구현할때, 우리는 데이터를 해싱한 값을 Node[] table 배열의 인덱스(index)로 활용하여 해당 인덱스에 데이터를 저장했다. 이는 데이터를 빠르게 탐색할 수 있는 장점을 갖게 하지만 데이터가 해싱된 값에 따라 저장되는 위치가 달라지므로 순서가 보장되지는 않는다.
이러한 단점을 보완하기 위해 LinkedList를 구현할 때, 노드 클래스에는 이전 노드를 가리키는 변수인 prev와 다음 노드를 가리키는 next 변수를 두고, LinkedList 클래스에서는 연결된 노드들의 첫 노드를 가리키는 head, 마지막 노드를 가리키는 tail을 두어서 상호 연결을 하는 원리로 HashSet 구현과 동일하게 table에 저장하되 순서를 보장할 수 있도록 LinkedList의 구현 기능을 추가해준 것이다.
이전의 HashSet 구현에 LinkedList처럼 연결에 필요한 변수만 추가된 것이다.
위 이미지는 해시셋의 기본구조이다. 아래 LinkedHashSet의 기본구조를 보면서 더 자세히 알아보도록 하자.
Separate Chaining 방식으로 해시 충돌이 일어났을 경우 체이닝을 위한 next 변수와 순서를 보장하기 위한 prevLink, nextLink로 링크드 해시셋을 표현한 그림이다. 테이블에 담기면서 아래의 링크드리스트 꼴로 참조를 통해 연결되있다고 보면 된다.
Node 구현
public class Node<E> {
final int hash;
final E key;
Node<E> next; // for Separate Chaining
Node<E> prevLink; // for linked list(set)
Node<E> nextLink; // for linked list(set)
public Node(int hash, E key, Node<E> next) {
this.hash = hash;
this.key = key;
this.next = next;
this.prevLink = null;
this.nextLink = null;
}
}
LinkedHashSet 구현
<필수목록>
- 클래스 및 생성자와 필수 메소드 구성
- add 메소드
- resize 메소드
- remove 메소드
- size, isEmpty, contains, clear, equals 메소드
- toArray 구현
클래스 및 생성자 구성
public class LinkedHashSet<E> implements SetInterface<E> {
// 최소 기본 용적이며 2^n 꼴 형태가 좋다.
private static final int DEFAULT_CAPACITY = 1 << 4;
// 3/4 이상 채워질 경우 resize 하기 위한 임계값
private static final float LOAD_FACTOR = 0.75f;
Node<E>[] table; // 요소의 정보를 담고있는 Node 를 저장할 Node 타입 배열
private int size; // 요소의 개수
// 들어온 순서를 유지할 LinkedList
private Node<E> head; // 노드의 첫 부분
private Node<E> tail; // 노드의 마지막 부분
@SuppressWarnings("unchecked")
public LinkedHashSet() {
table = (Node<E> []) new Node[DEFAULT_CAPACITY];
size = 0;
head = null;
tail = null;
}
// 보조 해시 함수 (상속 방지를 위해 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);
}
}
}
보조 해시 함수인 hash 메소드가 있다. 반드시 필요한 것은 아니며 최대한 해시충돌을 피하기 위해 보조해시함수를 통해 고른 분포를 할 수 있도록 하기 위함이다. Java 11의 구현과 유사하게 key의 hashCode()의 절댓값과 그 값을 16비트 왼쪽 밀어낸 값과의 XOR 값을 반환한다.
나머지 연산을 할때에는 hashCode 값이 음수가 나올 것을 고려하여 Math.abs() 함수를 사용해야 하지만 비트 연산 (&)을 사용할 경우 Math.abs()를 쓸 필요가 없다.
또한 이번 연결해시 셋에서는 사용자 용적 설정을 할 수 있는 생성자를 따로 두지 않았다. HashSet의 용적은 2^n 꼴로 두는 것이 매우 편리하고 좋다고 이전 포스팅에서도 확인할 수 있었다. 2^n 꼴이 좋은 이유는 사용자가 해시충돌을 예측하기 어렵고 충돌이 발생하더라도 Separate Chaining 방식으로 연결되므로 굳이 용적을 설정하게 둘 필요도 없기 때문이다.
add 메소드
add 과정 자체는 HashSet의 add와 과정이 동일하며 마지막에 노드에 대해 '링크'가 추가되는 것만 다르다.
private void linkLastNode(Node<E> o) {
Node<E> last = tail; // 마지막 노드를 가져온다.
tail = o; // tail 을 새로운 노드 o 가 가리키도록 갱신
/*
만약 마지막 노드가 null 이라는 것은 노드에 저장된 데이터가 없는,
즉, head 도 null 인 상태라는 것이다.
그러므로 head 도 새 노드를 가리키도록 해야한다.
*/
if (last == null) head = o;
/*
마지막 노드가 null 이 아닐 경우 새 노드 o의 앞의 노드를 가리키는 노드를 last 로 두고,
last 의 다음 노드는 새 노드인 o를 가리키도록 한다.
*/
else {
o.prevLink = last;
last.nextLink = o;
}
}
마지막 노드를 연결하는 메소드를 작성 후 LinkedHashSet의 추가 과정을 한번 알아보자.
전체적 과정은 HashSet과 다를게 없고 마지막 노드들의 순서를 위한 link만 추가해주면 된다. 코드는 아래와 같다.
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;
Node<E> newNode = new Node<>(hash, key, null);
// table[idx] 가 비어있을 경우 새 노드 생성
if (table[idx] == null) {
table[idx] = newNode;
} 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 = newNode;
}
size++;
linkLastNode(newNode); // table 에 저장이 끝나면 해당 노드를 연결시킨다.
// 데이터 개수가 현재 table 용적의 75%를 넘는다면 용적을 늘려준다.
if (size >= LOAD_FACTOR * table.length) {
resize();
}
return null; // 정상적으로 추가 되었을 경우 null 반환
}resize 메소드
resize 메소드는 HashSet과 과정과 코드가 완전 동일하다.
이해하기 쉽도록 이미지와 코드를 적어두도록 하겠다.
2^n 꼴로 고정된 형태의 용적을 사용하는 경우 resize() 가 굉장히 빠르고 쉽다는 것을 지난 포스트에서 설명했었다. 글이 너무 길어지니 이 포스트에서 resize 부분의 더보기 부분을 확인해주길 바란다.
@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 변수에 연결
}remove 메소드
삭제 및 반환은 반대로 table에 해당 노드를 삭제한 다음 삭제된 노드와 연결 링크를 끊고 새로 이어주기만 하면 끝난다.
index를 찾고 해당 객체 내용이 같다면 해당 노드의 연결된 링크들을 끊어주고 그 앞과 뒤의 노드끼리 서로 연결하면 된다.
먼저 연결리스트의 링크를 끊어주는 메소드를 구현한다.
private void unlinkNode(Node<E> o) {
Node<E> prevNode = o.prevLink; // 삭제하는 노드의 이전노드
Node<E> nextNode = o.nextLink; // 삭제하는 노드의 다음노드
/*
prevNode 가 null 이라는 것은 삭제 노드가 head 였다는 의미이다.
따라서 그 다음 노드인 nextNode 가 head 가 된다.
*/
if (prevNode == null) head = nextNode;
else {
prevNode.nextLink = nextNode;
o.prevLink = null;
}
/*
nextNode 가 null 이라는 것은 삭제 노드가 tail 였다는 의미이다.
따라서 그 이전 노드인 prevNode 가 tail 이 된다.
*/
if (nextNode == null) tail = prevNode;
else {
nextNode.prevLink = prevNode;
o.nextLink = null;
}
}
@Override
public boolean remove(Object o) {
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; // 삭제되는 노드를 반환하기 위해 담아둔다.
// 해당 노드의 이전 노드가 존재하지 않는 경우 (= table 에 첫번째 체인 노드인 경우)
if (prev == null) table[idx] = node.next;
// 그 외엔 이전 노드의 Next 를 삭제할 노드의 다음 노드와 연결한다.
else {
prev.next = node.next;
}
// table 의 체인을 끊었으니 다음으로 순서를 유지하는 link 를 끊는다.
unlinkNode(node);;
node = null;
size--;
break; // 삭제되었으니 종료
}
prev = node;
node = node.next;
}
return removedNode;
}
while 문에서 같은 요소가 존재하지 않으면 removedNode는 Null 상태이므로 결국 Null 을 반환한다.
즉, 삭제할 노드가 없다면 null을 반환함으로써 상위 메소드에서 false를 반환하고 삭제할 노드가 있을 경우 null 이 아니기 때문에 true를 반환하는 원리이다.
size, isEmpty, contains, clear, 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> tmp = table[idx];
while (tmp != null) {
if (o == tmp.key || (o != null && tmp.key.equals(o))) {
return true;
}
tmp = tmp.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;
}
head = tail = null;
}
@SuppressWarnings("unchecked")
@Override
public boolean equals(Object o) {
if (o == this) return true;
if (!(o instanceof LinkedHashSet)) {
return false;
}
LinkedHashSet<E> oSet;
/*
Object 로부터 LinkedHashSet<E> 로 캐스팅 되어야 비교가 가능하기 때문에
만약 캐스팅이 불가능할 경우 ClassCastException 이 발생한다.
이 경우 false 를 return 하도록 try-catch 문을 사용해준다.
*/
try {
// LinkedHashSet 타입으로 캐스팅
oSet = (LinkedHashSet<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 || head == null) {
return null;
}
Object[] ret = new Object[size];
int index = 0;
// 들어온 순서대로 head 부터 tail 까지 순회
for (Node<E> x = head; x != null; x = x.nextLink) {
ret[index] = x.key;
index++;
}
return ret;
}
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
Object[] copy = toArray();
if (a.length < size) {
return (T[]) Arrays.copyOf(copy, size, a.getClass());
}
System.arraycopy(copy, 0, a, 0, size);
return a;
}
전체 코드
package Z_DataStructure.Set.LinkedHashSet;
import Z_DataStructure.A_InterfaceForm.SetInterface;
import java.util.Arrays;
public class LinkedHashSet<E> implements SetInterface<E> {
// 최소 기본 용적이며 2^n 꼴 형태가 좋다.
private static final int DEFAULT_CAPACITY = 1 << 4;
// 3/4 이상 채워질 경우 resize 하기 위한 임계값
private static final float LOAD_FACTOR = 0.75f;
Node<E>[] table; // 요소의 정보를 담고있는 Node 를 저장할 Node 타입 배열
private int size; // 요소의 개수
// 들어온 순서를 유지할 LinkedList
private Node<E> head; // 노드의 첫 부분
private Node<E> tail; // 노드의 마지막 부분
@SuppressWarnings("unchecked")
public LinkedHashSet() {
table = (Node<E> []) new Node[DEFAULT_CAPACITY];
size = 0;
head = null;
tail = null;
}
// 보조 해시 함수 (상속 방지를 위해 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);
}
}
private void linkLastNode(Node<E> o) {
Node<E> last = tail; // 마지막 노드를 가져온다.
tail = o; // tail 을 새로운 노드 o 가 가리키도록 갱신
/*
만약 마지막 노드가 null 이라는 것은 노드에 저장된 데이터가 없는,
즉, head 도 null 인 상태라는 것이다.
그러므로 head 도 새 노드를 가리키도록 해야한다.
*/
if (last == null) head = o;
/*
마지막 노드가 null 이 아닐 경우 새 노드 o의 앞의 노드를 가리키는 노드를 last 로 두고,
last 의 다음 노드는 새 노드인 o를 가리키도록 한다.
*/
else {
o.prevLink = last;
last.nextLink = o;
}
}
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;
Node<E> newNode = new Node<>(hash, key, null);
// table[idx] 가 비어있을 경우 새 노드 생성
if (table[idx] == null) {
table[idx] = newNode;
} 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 = newNode;
}
size++;
linkLastNode(newNode); // table 에 저장이 끝나면 해당 노드를 연결시킨다.
// 데이터 개수가 현재 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; // 새 테이블을 연결해준다.
}
private void unlinkNode(Node<E> o) {
Node<E> prevNode = o.prevLink; // 삭제하는 노드의 이전노드
Node<E> nextNode = o.nextLink; // 삭제하는 노드의 다음노드
/*
prevNode 가 null 이라는 것은 삭제 노드가 head 였다는 의미이다.
따라서 그 다음 노드인 nextNode 가 head 가 된다.
*/
if (prevNode == null) head = nextNode;
else {
prevNode.nextLink = nextNode;
o.prevLink = null;
}
/*
nextNode 가 null 이라는 것은 삭제 노드가 tail 였다는 의미이다.
따라서 그 이전 노드인 prevNode 가 tail 이 된다.
*/
if (nextNode == null) tail = prevNode;
else {
nextNode.prevLink = prevNode;
o.nextLink = null;
}
}
@Override
public boolean remove(Object o) {
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; // 삭제되는 노드를 반환하기 위해 담아둔다.
// 해당 노드의 이전 노드가 존재하지 않는 경우 (= table 에 첫번째 체인 노드인 경우)
if (prev == null) table[idx] = node.next;
// 그 외엔 이전 노드의 Next 를 삭제할 노드의 다음 노드와 연결한다.
else {
prev.next = node.next;
}
// table 의 체인을 끊었으니 다음으로 순서를 유지하는 link 를 끊는다.
unlinkNode(node);;
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> tmp = table[idx];
while (tmp != null) {
if (o == tmp.key || (o != null && tmp.key.equals(o))) {
return true;
}
tmp = tmp.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;
}
head = tail = null;
}
@SuppressWarnings("unchecked")
@Override
public boolean equals(Object o) {
if (o == this) return true;
if (!(o instanceof LinkedHashSet)) {
return false;
}
LinkedHashSet<E> oSet;
/*
Object 로부터 LinkedHashSet<E> 로 캐스팅 되어야 비교가 가능하기 때문에
만약 캐스팅이 불가능할 경우 ClassCastException 이 발생한다.
이 경우 false 를 return 하도록 try-catch 문을 사용해준다.
*/
try {
// LinkedHashSet 타입으로 캐스팅
oSet = (LinkedHashSet<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 || head == null) {
return null;
}
Object[] ret = new Object[size];
int index = 0;
// 들어온 순서대로 head 부터 tail 까지 순회
for (Node<E> x = head; x != null; x = x.nextLink) {
ret[index] = x.key;
index++;
}
return ret;
}
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
Object[] copy = toArray();
if (a.length < size) {
return (T[]) Arrays.copyOf(copy, size, a.getClass());
}
System.arraycopy(copy, 0, a, 0, size);
return a;
}
}정리
중복을 허용하지 않는 자료구조로 HashSet(HashMap)을 주로 사용하는데 순서까지 보장하고 싶다면 사용하게 되는 LinkedHashSet(LinkedHashMap)에 대해서 알아보았다. 그리고 Set은 내부적으로 Map으로 구성되고 둘의 차이점은 Map은 (key, value)로 쌍이 이뤄져 있고 Set은 key를 값으로 사용한다는 것이 차이점이었다.
또 연결 해시 셋의 테이블을 보게되면 저장 방식에는 순서가 유지되어 있지 않지만 link를 통해 뽑을 때는 순서가 유지된다는 것을 알 수 있다.
'Programing & Coding > Data Structure' 카테고리의 다른 글
| [자료구조] 19. HashTable, HashMap(LinkedList / Red-Black-Tree) (0) | 2024.01.19 |
|---|---|
| [자료구조] 18. 트리(Tree)의 개념 (0) | 2023.07.19 |
| [자료구조] 16. 해시 충돌 (0) | 2023.07.17 |
| [자료구조] 15. HashSet (해시 셋) (1) | 2023.07.16 |
| [자료구조] 14. Java 셋 인터페이스 (Set Interface) (0) | 2023.07.13 |
'Programing & Coding/Data Structure' Related Articles
more
