- Set은 중복을 허용하지 않고 입력 순서가 보장되지 않는 자료구조지만 LinkedHashSet은 입력 순서를 보장해줌
Set Interface
package Interface_form;
public interface Set<E> {
/**
*
* @param e 집합에 추가할 요소
* @return Set에 요소가 없어 정상적으로 추가되면 true
*/
boolean add(E e);
/**
*
* @param o Set에서 삭제할 특정 요소
* @return 정상적으로 삭제되면 true
*/
boolean remove(Object o);
/**
*
* @param o Set에서 찾을 특정 요소
* @return Set에 해당 요소가 포함되어있으면 true
*/
boolean contains(Object o);
/**
* 지정된 객체가 현재 Set과 같은지를 반환
* @param o Set과 비교할 객체
* @return Set과 객체가 동일할 경우 true
*/
boolean equlas(Object o);
/**
* 현재 Set이 빈 상태(요소가 없는)인지 여부를 반환
* @return Set이 비어있다면 true
*/
boolean isEmpty();
/**
* 현재 집합의 요소의 개수를 반환합니다. 만약 들어있는 요소가
* {@code Integer.MAX_VALUE}를 넘을 경우 {@code Integer.MAX_VALUE}를 반환합니다.
* @return Set의 요소의 개수
*/
int size();
/**
* Set의 모든 요소를 제거
*/
void clear();
}Node class
public class Node<E> {
final int hash;
final E key;
Node<E> next; // for Separate Chaining
Node<E> nextLink; // for linked list(set)
Node<E> prevLink; // for linked list(set)
public Node(int hash, E key, Node<E> next) {
this.hash = hash;
this.key = key;
this.next = next;
this.nextLink = null;
this.prevLink = null;
}
}LinkedHashSet
import Interface_form.Set;
public class LinkedHashSet<E> implements Set<E> {
private final static int DEFAULT_CAPACITY = 1 << 4;
private static final float LOAD_FACTOR = 0.75f;
Node<E>[] table;
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 int hash(Object key) {
int hash;
if (key == null) {
return 0;
}
else {
return Math.abs(hash = key.hashCode()) ^ (hash >>> 16);
}
}
private void linkLastNode(Node<E> o) {
Node<E> last = tail;
tail = o;
/*
* 만약 마지막 노드가 null이라는 것은 노드에 저장된 데이터가 없는,
* 즉 head 노드도 null인 상태라는 것이다.
* 그러므로 head도 새 노드인 o를 가리키도록 한다.
*/
if (last == null) {
head = o;
}
/*
* last가 null이 아닐경우 새 노드 o의 앞의 노드를 가리키는 노드를 last로 두고,
* last의 다음 노드는 새 노드인 o를 가리키도록 한다.
*/
else {
o.prevLink = last;
last.nextLink = o;
}
}
@Override
public boolean add(E e) {
return add(hash(e), e) == null;
}
private E add(int hash, E key) {
int idx = hash % table.length;
Node<E> newNode = new Node<E>(hash, key, null);
if (table[idx] == null) {
table[idx] = newNode;
}
else {
Node<E> temp = table[idx];
Node<E> prev = null;
while (temp != null) {
// 동일 객체라면 저장하지 않고 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 용적의 75%을 넘어가는 경우 용적을 늘려준다.
if (size >= LOAD_FACTOR * table.length) {
resize();
}
return null;
}
@SuppressWarnings("unchecked")
private void resize() {
int newCapacity = table.length * 2;
// 기존 테이블의 두배 용적으로 생성
final Node<E>[] newTable = (Node<E>[]) new Node[newCapacity];
for (int i = 0; i < table.length; i++) {
Node<E> value = table[i];
if (value == null) {
continue;
}
table[i] = null;
Node<E> nextNode;
// 현재 인덱스에 연결 된 노드들을 순회한다.
while (value != null) {
int idx = value.hash % newCapacity;
/*
* 새로 담을 index에 요소(노드)가 존재할 경우
* == 새로 담을 newTalbe에 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;
}
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이라는 의미로
* 이전 노드가 tail이 된다.
*/
if (nextNode == null) {
tail = prevNode;
}
else {
nextNode.prevLink = prevNode;
o.nextLink = null;
}
}
@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;
// 해당노드의 이전 노드가 존재하지 않는 경우 (= 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> temp = table[idx];
/*
* 같은 객체 내용이어도 hash값은 다를 수 있다.
* 하지만, 내용이 같은지를 알아보고 싶을 때 쓰는 메소드이기에
* hash값은 따로 비교 안해주어도 큰 지장 없다.
* 단, o가 null인지는 확인해야한다.
*/
while (temp != null) {
if (o == temp.key || (o != null && temp.key.equals(o))) {
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;
}
head = tail = null;
}
@SuppressWarnings("unchecked")
@Override
public boolean equals(Object o) {
// 만약 파라미터 객체가 현재 객체와 동일한 객체라면 true
if(o == this) {
return true;
}
// 만약 o 객체가 LinkedHashSet 계열이 아닌경우 false
if(!(o instanceof LinkedHashSet)) {
return false;
}
LinkedHashSet<E> oSet;
/*
* Object로부터 LinkedHashSet<E>로 캐스팅 되어야 비교가 가능하기 때문에
* 만약 캐스팅이 불가능할 경우 ClassCastException 이 발생한다.
* 이 경우 false를 return 하도록 try-catch문을 사용해준다.
*/
try {
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;
}
}https://st-lab.tistory.com/161?category=856997
HashSet과 LinkedHashSet은 직접 구현하기 어려웠다.
위 블로그 글을 정독하고 코드를 이해한 뒤 메소드 하나씩 코드를 따라치며 이해하는 방식으로 진행했다.
인간은 망각의 동물이라지만 이건 너무한 거 아니냐고