Set
Set은 유일한 요소들을 갖는 컬렉션이다.
특징
- 유일성: Set에는 중복된 요소가 존재하지 않으며 요소를 추가할 때 이미 존재하는 요소면 무시한다
- 순서 미보장: 대부분의 셋 구현은 요소들의 순서를 보장하지 않는다
- 빠른 검색: Set은 요소의 유무를 빠르게 확인할 수 있도록 최적화 되어있다.
- 보통 중복을 허용하지 않으면서 요소의 유무만 확인할 경우에 사용된다.
import java.util.Arrays;
public class MyHashSetV0 {
private int[] elementData = new int[10];
private int size = 0;
public boolean add(int value) {
if (contains(value)) {
return false;
}
elementData[size++] = value;
return true;
}
public boolean contains(int value) {
for (int data : elementData) {
if (data == value) {
return true;
}
}
return false;
}
public int getSize() {
return size;
}
@Override
public String toString() {
return "MyHashSetV0{" + "elementData=" + Arrays.toString(Arrays.copyOf(elementData, size)) + ", size=" + size +
'}';
}
}
간단하게 구현한 Set구조로 따로 설명없이 코드만 봐도 이해할 수 있을 것이다.
하나만 짚고가자면 Set은 Set의 특징에서도 설명했듯이 데이터의 중복을 허용하지 않고 데이터의 검색을 contains()
메서드를 통해 boolean
타입으로 데이터의 유무를 확인할 수 있다.
Java의 Set
자바는 Set을 인터페이스로 제공하며 Set인터페이스는 HashSet
, LinkedHashSet
, TreeSet
, SortedSet
등 여러 구현 클래스를 가지고 있다
Set인터페이스를 구현하는 구현클래스들은 모두 Set의 특징요소들을 모두 만족하며 각각 개발상황에 맞는 구현체를 사용할 수 있다
HashSet
- 해시 알고리즘을 사용해서 Set을 구현
- 요소들은 순서없이 저장되어 요소의 순서를 보장하지 않는다. 즉, 입력한 순서와 출력순서는 연관이 없다
- 해시 알고리즘을 사용하기때문에 추가,삭제,검색과 같은 연산에 대해 평균적으로 O(1)시간 복잡도를 갖는다
- 데이터의 유일성(중복 없음)을 중요시하고 순서가 보장될 필요 없을 경우에 사용한다
- 예시
- 사용자 이름 중복확인: 이미 사용중인 사용자 이름을 확인
- 채팅: 현재 접속중인 사용자 목록 관리
- 쿠폰코드관리: 중복되지 않는 유효한 쿠폰코드를 관리할 때 사용
LinkedHashSet
- HashSet을 상속받으며 HashSet에 Linked구조가 추가된 자료구조이다
- 해시 인덱스를 산출하여 데이터를 저장할 배열의 인덱스를 구하고 배열 안을
Node
로 구성하여 데이터를Node
안에 저장하고 다음 저장될 데이터를 참조한다. - 요소들은 추가된 순서대로 유지되기때문에 입력된 순서와 출력의 순서를 보장할 수 있다.
import java.util.LinkedHashSet;
public class JavaSetMain {
public static void main(String[] args) {
LinkedHashSet
set.add(5);
set.add(8);
set.add(1);
set.add(3);
System.out.println(set);
}
}
//실행결과
[5, 8, 1, 3]
- 사용예시
- 최근 본 상품목록
- 브라우저 방문기록
- 즐겨찾기 목록
- 해시 알고리즘을 적용했기때문에 O(1)의 시간복잡도를 갖지만 `Node`를 생성하고 관리하는 과정이 있기때문에 `HashSet`보다는 무겁다
#### TreeSet
- 자바의 TreeSet은 이진 탐색 트리를 개선한 레드-블랙 트리를 내부에서 사용한다
- 요소들은 정렬된 순서로 저장되며 순서의 기준은 `Comparator`로 변경할 수 있다. 덕분에 객체와 같이 순서대로 저장하기 모호한 데이터들도 기준을 정해 순서대로 저장할 수 있다
- O(log n)의 시간복잡도를 갖는다
- 데이터들을 정렬된 순서로 유지하면서 집합의 특성을 유지해야할 때 사용한다
- 데이터의 입력순서대로 저장되는 것이 아니라 데이터 값자체 크기(정수,문자열기준)의 순서에 따라 저장된다.
- 사용예시
- 이름 목록 정렬: 사용자의 이름순서대로 정렬
- 점수 순위의 관리
- 날짜정렬: 이벤트의 일정이나 날짜를 관리
- 제품가격정렬
> [!트리구조의 개념]
>자바 - 중급2편 - 섹션 8 - 자바가제공하는Set2 - TreeSet
``` run-java
import java.util.TreeSet;
public class JavaSetMain {
public static void main(String[] args) {
TreeSet<String> set = new TreeSet<>();
set.add("A");
set.add("8");
set.add("1");
set.add("3");
set.add("B");
System.out.println(set);
}
}
//실행결과
//[1, 3, 8, A, B]
실행결과로 데이터의 값 순서대로 저장된 것을 확인할 수 있다.
HashSet
이제 Set컬렉션에 해시알고리즘을 적용하여 Set보다 훨씬 성능이 좋은 HashSet을 구현해보자
먼저 HashSet에서는 해시 알고리즘을 활용할 인덱스를 갖는 배열과 그 각각의 배열안에 해시 코드값이 같은 데이터를 저장하기위한 LinkedList
로 구현된다.
필드영역
static final int DEFAULT_INITIAL_CAPACITY = 16;
LinkedList<Integer>[] buckets;
private int size = 0;
private int capacity = DEFAULT_INITIAL_CAPACITY;
DEFAULT_INITIAL_CAPACITY
: 해시 인덱스가 적용될 배열의 기본 길이를 설정하기위한 상수LinkedList<Integer>[] buckets
: 해시인덱스가 적용될 배열private int size
:buckets
의 사이즈private int capacity = DEFAULT_INITIAL_CAPACITY
:capacity
는 생성자에서 변경될 수 있기때문에 필드로도 따로 선언
생성자
public MyHashSetV1() {
initBuckets();
}
public MyHashSetV1(int capacity) {
this.capacity = capacity;
initBuckets();
}
private void initBuckets() {
buckets = new LinkedList[capacity];
for (int i = 0; i < capacity; i++) {
buckets[i] = new LinkedList<>();
}
}
기본생성자와 배열의 길이를 받아서 생성하는 생성자 두 가지를 지원한다initBuckets()
에서는 각각의 배열 인덱스에 LinkedList
를 생성해준다.
메서드
add()
public boolean add(int value) {
int hashIndex = hashIndex(value);
LinkedList<Integer> bucket = buckets[hashIndex];
if (bucket.contains(value)) {
return false;
}
bucket.add(value);
size++;
return true;
}
먼저 해시알고리즘을 통하여 참조할 해시인덱스를 구하고 구한 해시인덱스를 통해 실제 데이터가 저장될 LinkedList
를 구한다. (bucket)
그 다음 bucket
리스트에 추가하고자하는 값이 있는지 검사하고 만약 이미 같은 값이 존재한다면 false
를 반환하고, 값이 존재하지 않는다면 값을 추가한뒤 size+1
을 해준뒤 true
를 반환한다.
->Set은 중복값을 허용하지 않기때문에
remove
public boolean remove(int value) {
int hashIndex = hashIndex(value);
LinkedList<Integer> bucket = buckets[hashIndex];
if (bucket.contains(value)) {
bucket.remove(Integer.valueOf(value));
size--;
return true;
}
return false;
}
add()
메서드와 구현과정이 유사하기때문에 따로 설명은하지 않겠다
하지만 bucket.remove
를 하는 과정에서 파라미터로 받은 value
를 래퍼 클래스로 박싱하는 부분만 살펴보자
자바가 지원하는 LinkedList
의 remove
메서드는 아래와 같이 오버로딩 되어있다.
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
매개변수로 int
와 Object
가 모두 선언되어있기때문에 인자로 기본타입인 int
값을 전달할 경우 삭제가 되지 않거나 index와 일치하는 값을 삭제하는 의도되지 않는 방향으로 구현이 될 수 있다.
때문에 Object
타입의 매개변수를 사용하기위해 기본값인 value
를 래퍼 클래스로 감싸서 인자로 전달하는 것이다. 이렇게하면 boolean
타입으로 반환값을 받을 수 있을것이다.
contains()
public boolean contains(int searchValue) {
int hashIndex = hashIndex(searchValue);
LinkedList<Integer> bucket = buckets[hashIndex];
return bucket.contains(searchValue);
}
실질적으로 데이터가 저장되어있는 LinkedList
를 해시 코드에 맞게 가져온 뒤 그 리스트 안에 검색하고자하는 값이 있는지 조회하여 있으면 true
없으면 false
를 반환한다.
공용 메서드
public int getSize() {
return size;
}
public int hashIndex(int value) {
return value % capacity;
}
지금까지 HashSet을 간단하게 직접 구현해봤다.
여기서 의문점이 하나 생기는데 정수타입은 어떻게 해시 알고리즘을 적용하는지 이해했는데 만약 문자열이 데이터로 들어온다면 어떻게 해시 알고리즘을 적용해야될까?
문자열에 해시알고리즘을 적용하는 방법을 알아보자
문자열 해시알고리즘 적용
문자열은 문자의 배열이라는 특성을 이용하며 자바에서 문자는 char
타입으로 char
하나는 숫자로 치환할 수 있다.
->컴퓨터는 인간이 쓰는 문자를 인식하지 못하기때문에 문자를 숫자로 치환해서 사용함
이러한 특징들을 사용하여 문자열에도 해시알고리즘을 적용할 수 있다.
public class StringHashMain {
static final int CAPACITY = 10;
public static void main(String[] args) {
int AB = hashCode("AB");
System.out.println(AB);
int hashIndex = hashIndex(AB);
System.out.println(hashIndex);
}
static int hashCode(String string) {
char[] charArray = string.toCharArray();
int sum = 0;
for (char c : charArray) {
sum += c;
}
return sum;
}
static int hashIndex(int value) {
return value % CAPACITY;
}
}
용어정리
해시 함수
- 해시 함수는 임이의 데이터를 고정된 길이(저장 공간)의 해시값을 출력하는 함수이다
- 같은 데이터를 입력하면 항상 같은 해시 코드가 출력된다
- 다른 데이터를 입력하면 같은 해시코드가 출력될 수 있는데 이를 해시 충돌이라한다
해시 코드
- 해시 코드는 데이터를 대표하는 값을 뜻한다. 보통 해시 함수를 통해 만들어진다
해시 인덱스
- 해시 인덱스는 데이터의 저장 위치를 결정해주며 주로 해시코드를 사용해서 만든다
- 해시 코드의 결과에 배열의 크기를 나누어서 구한다
이제 정수와 문자열에 해시 코드를 구하는 방법은 충분히 이해했다
다음 문제는 Member
, User
, Order
와 같은 객체는 어떻게 해시 코드를 정의할 수 있을지에 대해 알아보자.
자바에서 제공하는 hashCode()
해시 자료구조는 데이터 추가, 검색, 삭제의 성능이 O(1)로 매우 빠르다. 따라서 해시 알고리즘은 많은 곳에서 자주 사용되기때문에 자바는 모든 객체가 자신만의 해시 코드를 표현할 수 있도록 Object
클래스에서 hashCode()
메서드를 따로 구현해놓았다.
자바에서 제공한 Object.hashCode()
를 사용하면 우리가 직접 구현해보았던 문자열의 해시 코드를 편리하고 더 최적화된 상태로 사용할 수 있으며 Member
, Order
같은 객체에 대한 해시코드도 제공한다.
자바에서 제공하는 hashCode()
메서드는 기본적으로 객체의 참조값을 기반으로 해시코드를 만들기때문에 보통 객체 클래스를 만들때 재정의해서 사용한다. 이 부분에 대해서 이해가 잘 안된다면 코드를 통해 설명하겠다.
hashCode()
가 재정의 되지 않은 Member
클래스 - 인스턴스의 참조값으로 해시코드 생성
public class Member {
private String id;
public Member(String id) {
this.id = id;
}
public String getId() {
return id;
}
@Override
public String toString() {
return "Member{" + "id='" + id + '\'' + '}';
}
}
사람이 보는 시선에서 Member
클래스는 필드인 id
가 같은 멤버라면 같은 사람이라는 것을 인지할 수 있으며 그렇게 되도록 설계해야한다.
즉, 아래의 member1
과 member2
는 같은 ID를 가지고있기때문에 같은 회원으로 조회되어야하며 해시코드가 동일해야한다.
public class JavaHashCodeMain {
public static void main(String[] args) {
Member member1 = new Member("member1");
Member member2 = new Member("member1");
int member1Hash = member1.hashCode();
System.out.println(member1Hash);
int member2Hash = member2.hashCode();
System.out.println(member2Hash);
System.out.println(member1.equals(member2));
}
}
실행결과
member1Hash = 168423058
member2Hash = 1325547227
false
하지만 실행결과를 살펴보면 두 인스턴스는 같은 ID를 가지고있음에도 다른 해시코드를 반환하며 equals()
의 결과또한 false를 반환하고있다.
이는 Object
의 hashCode()
메서드가 생성된 인스턴스의 참조값을 기반으로 해시코드를 생성하기때문이다. member1
와 member2
는 각각 다른 메모리에 생성되며 다른 참조값을 가지고있다는 의미이다.
===이는 물리적(메모리 시점)으로는 일치하지만 논리적(사람 시점)으로는 일치하지 않는다는 것을 의미한다===
이제 Object.hashCode()
와 equals
메서드를 재정의해서 논리적으로 동등하도록 오버라이딩해보자.
hashCode()
가 재정의 Member
클래스 - 인스턴스의 필드(id)값을 기반으로 해시코드 생성
public class Member {
private String id;
public Member(String id) {
this.id = id;
}
public String getId() {
return id;
}
@Override
public String toString() {
return "Member{" + "id='" + id + '\'' + '}';
}
@Override
public boolean equals(Object object) {
if (this == object)
return true;
if (object == null || getClass() != object.getClass())
return false;
Member member = (Member) object;
return Objects.equals(id, member.id);
}
@Override
public int hashCode() {
return Objects.hash(id);
}
}
hashCode()
메서드를 재정의할 때 인자로 id
필드를 주어서 id
가 같은 값일 경우 같은 해시코드를 반환하도록 재정의하였다.
이제 다시 메인 메서드를 실행해서 실행결과를 살펴보면
실행결과
member1Hash = 948881654
member2Hash = 948881654
true
같은 아이디를 가진 멤버에 대해서 같은 해시코드를 반환하는 것을 확인할 수 있으며 equals()
메서드의 결과도 true
가 나온 것을 확인할 수 있다.
'Language > Java' 카테고리의 다른 글
[Java] Enum타입 (1) | 2024.06.18 |
---|---|
[Java] - Generic (1) | 2024.06.15 |
[JAVA - 자료구조] ArrayList vs LinkedList (1) | 2024.06.09 |
[JAVA - 자료구조] LinkedList (1) | 2024.06.09 |
[JAVA] 익명 클래스 (1) | 2024.06.09 |
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!