들어가기 전
『자바의 신 3판』 을 읽고 내용 정리 및 공부한 내용을 정리한 글입니다.
서적: 자바의 신 3판 구입처
내용 정리
Set은 왜 필요한가?
Set의 주 용도
List는 순서가 중요한 데이터를 담을 때 사용된다면, Set은 순서에 상관없이, 어떤 데이터가 존재하는지를 확인하기 위한 용도로 많이 사용된다.
다시 말해서, 아래 항목들이 주 용도이다.
- 중복되는 것을 방지 (순서 없음)
- 원하는 값이 포함되어 있는 지를 확인
대표적인 예
예를 들어, 어떤 서버에 1분 간 사용자가 요청한 로그가 있다. 이 서버에 붙어서 요청한 IP를 기준으로 사용자의 수가 얼마나 되는지 확인한다고 가정해보자.
1분 간 동일한 서버에 요청하는 중복 사용자 수는 매우 많다. 이러한 경우에 ArrayList로 확인하려고 한다면 아래 과정을 반복해야 한다.
- indexOf() 메소드로 해당 객체가 존재하는지 확인한 후
- add() 메소드로 추가
하지만, Set을 구현한 클래스를 사용하면 데이터를 추가만 해주면 된다. 그러면 자동으로 데이터가 중복되지 않고 저장된다. 이때, 각 사용자가 사용한 IP의 순서는 그리 중요하지 않다.
이처럼 어떤 값이 존재하는지, 없는지 여부만 중요할 때 Set을 사용하면 된다.
Set 인터페이스를 구현한 주요 클래스
- HashSet
- 순서가 전혀 필요 없는 데이터를 해시 테이블(Hash Table)에 저장한다.
- Set 중에서 성능이 가장 좋다.
- TreeSet
- 저장된 데이터의 값에 따라서 정렬되는 Set이다.
- red-black이라는 트리 타입으로 값이 저장되며, HashSet보다 약간 성능이 느리다.
- LinkedHashSet
- 연결된 목록 타입으로 구현된 해시 테이블에 데이터를 저장한다.
- 저장된 순서에 따라서 값이 정렬된다.
- 성능이 이 셋 중에서 가장 나쁘다.
이러한 성능 차이가 발생하는 이유는 데이터 정렬 때문이다. 하지만, 몇 백만 건을 처리하지 않는 이상 우리가 그 성능 차이를 체감하기는 힘들다.
💡 red-black 트리
각 노드의 색을 붉은 색 혹은 검은색으로 구분하여 데이터를 빠르고 쉽게 찾을 수 있는 구조의 이진 트리를 말한다.
참고: https://ko.wikipedia.org/wiki/레드-블랙_트리
HashSet
상속 관계
먼저 상속 관계는 아래와 같다.
AbstractCollection을 확장한 AbstractSet을 확장했다. AbstractSet 클래스는 이름 그대로 abstract 클래스이며, 구현되어 있는 메소드는 3개 뿐이다.
| 클래스 | 메소드 명 | 설명 |
|---|---|---|
| Object 클래스에 선언됨 | equals() | Set은 데이터가 중복되는 것을 허용하지 않으므로, 데이터가 같은 지를 확인하는 작업은 Set의 핵심이다. |
| Object 클래스에 선언됨 | hashCode() | equals() 메소드는 hashCode() 메소드와 떨어질 수 없는 불가분의 관계이다. |
| AbstractSet 클래스에서 추가함 | removeAll() | 컬렉션을 매개 변수로 받아, 매개 변수 컬렉션에 포함된 모든 데이터를 지울 때 사용한다. |
equals(),hashCode()메소드를 구현하는 부분은 Set에서 매우 중요하다.
구현한 인터페이스
ArrayList와 비슷하다. 다만, Set은 순서가 없으므로 순서가 매개 변수로 넘어가는 메소드나, 수행 결과가 데이터 위치와 관련된 메소드들은 필요가 없다.
그러므로 get(int index) 나 indexOf(Object o) 와 같은 메소드들은 Set에 존재하지 않는다.
| 인터페이스 | 용도 |
|---|---|
| Serializable | 원격으로 객체를 전송하거나, 파일에 저장할 수 있음을 지정 |
| Cloneable | Object 클래스의 clone() 메소드가 제대로 수행될 수 있음을 지정. 즉, 복제가 가능한 객체임을 의미한다. |
| Iterable<E> | 객체가 “foreach” 문장을 사용할 수 있음을 지정 |
| Collection<E> | 여러 개의 객체를 하나의 객체에 담아 처리할 때의 메소드 지정 |
| Set<E> | Set 데이터를 처리하는 것과 관련된 메소드 지정 |
생성자
| 생성자 | 설명 |
|---|---|
| HashSet() | 데이터를 저장할 수 있는 16개의 공간과 0.75의 로드 팩터(load factor)를 갖는 객체를 생성한다. |
HashSet(Collection<? extends E> c) | 매개 변수로 받은 컬랙선 객체의 데이터를 HashSet에 담는다. |
| HashSet(int initialCapacity) | 매개 변수로 받은 개수만큼의 데이터 저장 공간과 0.75의 로드 팩터를 갖는 객체를 생성한다. |
| HashSet(int initialCapacity, float loadFactor) | 첫 매개 변수로 받은 개수만큼의 데이터 저장 공간과 두 번째 매개 변수로 받은 만큼의 로드 팩터를 갖는 객체를 생성한다. |
여기서 말하는 로드 팩터(load factor)란, (데이터의 개수)/(저장 공간) 을 의미한다.
만약 데이터의 개수가 증가하여 로드 팩터보다 커지면, 저장 공간의 크기는 증가되고 해시 재정리 작업(rehash)을 해야만 한다. 해시 재정리 작업에 들어가면, 내부에 갖고 있는 자료 구조를 다시 생성하는 단계를 거쳐야하므로 성능에 영향이 발생한다.
로드 팩터라는 값이 클수록 공간은 넉넉해지지만, 데이터를 찾는 시간은 증가한다.
따라서, 초기 공간 개수와 로드 팩터는 데이터의 크기를 고려하여 산정하는 것이 좋다. 왜냐하면 초기 크기가 (데이터의 개수)/(저장 공간) 보다 클 경우에는 데이터를 쉽게 찾기 위한 해시 재정리 작업이 발생하지 않기 때문이다.
따라서, 대량의 데이터를 여기에 담아 처리할 때에는 초기 크기와 로드 팩터의 값을 조절해 가면서 가장 적당한 크기를 찾아야만 한다.
하지만 대부분의 초급 개발자 분들은 로드 팩터를 건드릴 필요가 거의 없으므로, 매개 변수가 없는 첫 번째 생성자나, 초기 크기만 지정하는 세 번째 생성자를 사용하면 된다.
주요 메소드
HashSet에 선언되어 있는 메소드는 그리 많지 않다.
부모 클래스인 AbstractSet과 AbstractCollection에 선언 및 구현되어 있는 메소드를 그대로 사용하는 경우가 많다.
| 리턴 타입 | 메소드 이름 및 매개변수 | 설명 |
|---|---|---|
| boolean | add(E e) | 데이터를 추가한다. |
| void | clear() | 모든 데이터를 삭제한다. |
| Object | clone() | HashSet 객체를 복제한다. 하지만, 담겨있는 데이터들은 복제하지 않는다. |
| boolean | contains(Object o) | 지정한 객체가 존재하는지를 확인한다. |
| boolean | isEmpty() | 데이터가 있는지 확인한다. |
| Iterator<E> | iterator() | 데이터를 꺼내기 위한 Iterator 객체를 리턴한다. |
| boolean | remove(Object o) | 매개 변수로 넘어온 객체를 삭제한다. |
| int | size() | 데이터의 개수를 리턴한다. |
HashSet과 같은 Set을 사용하면 여러 중복되는 값들을 걸러내는 데 매우 유용하다. 출력해보면 저장한 순서대로 출력되지 않고, 뒤죽박죽으로 출력된 것을 볼 수 있다.
Iterator 객체로 출력하기
향상된 for문을 사용해 출력할 수도 있지만, 아래와 같이 Iterator 객체를 얻어서 출력할 수도 있다.
public void printCarSet2(Set<String> carSet) {
Iterator<String> iterator=carSet.iterator();
while(iterator.hasNext()) {
System.out.print(iterator.next()+" ");
}
System.out.println();
}Queue는 왜 필요한가?
FIFO의 용도
Queue(이하 큐)는 FIFO의 용도로 사용한다. FIFO는 First In First Out의 약자로 먼저 들어온 애가 먼저 나가는 것을 말한다.
웹 서버에 100명의 사용자가 요청을 했다고 가정하자. 만약 LIFO로 처리해서 사용자에게 응답을 준다면, 가장 먼저 와서 줄 서 있는 사용자가 가장 마지막에 응답을 받게 되므로, 더 이상 그 웹 서버를 사용하지 않을 수도 있다.
이렇게, 사용자들의 요청을 들어온 순서대로 처리할 때 큐를 사용한다.
Deque
LinkedList 클래스가 구현한 인터페이스 중에서 Java 6에서 추가된 Deque라는 것이 있다. API 상에서 보면 이 단어의 발음은 “deck”과 동일하다고 한다.
Deque는 “Double Ended Queue”의 약자이며, 일반 사전에 나오는 단어가 아니다. Deque는 Queue 인터페이스를 확장하였기 때문에 Queue의 기능을 전부 포함한다.
대신, 맨 앞에 값을 넣거나 빼는 작업, 맨 뒤에 값을 넣거나 빼는 작업을 수행하는 데 용이하도록 되어 있다고 보면 된다.
LinkedList란
앞 장에서 간단히 소개만 된 LinkedList라는 클래스가 있다. LinkedList는 자료 구조에 대해서 배울 때 중요한 항목 중 하나이기 때문에 꼭 기억하고 있어야만 한다.
LinkedList는 List 인터페이스 뿐만 아니라 Queue와 Deque 인터페이스도 구현하고 있다. 즉, LinkedList 자체가 List이면서도 Queue, Deque도 된다.
LinkedList의 동작 방식
LinkedList를 가장 쉽게 이해하려면 열차를 생각하면 된다. LinkedList에 A라는 하나의 값이 추가되면 열차의 맨 앞 칸에 데이터를 집어 넣는다. 이 때, LinkedList의 가장 앞의 값도 A이며, 가장 끝에 있는 값도 A다.
이 상태에서 B라는 데이터를 더 집어넣자. 그러면, 가장 앞에 있는 값은 A고, 가장 뒤에 있는 값은 B다. 여기서, A는 뒤에 B가 있다는 것을, B는 A가 앞에 있다는 것을 기억하고 있는다.
그 다음에 C라는 값을 집어넣자. 그러면 가장 앞에는 A, 그 다음에는 B, 마지막에는 C가 위치한다. 그런데, LinkedList에서는 앞에 있는 애와 뒤에 있는 애만 기억한다.
다시 말해서, A는 뒤에 있는 값이 B라는 것만 알고 그 뒤에 C가 있다는 것은 모른다. C도 앞에 B라는 것만 기억한다.
LinkedList를 사용하는 이유
간단하게 배열과 같이 데이터를 담아서 순차적으로 뺄 경우에는 별 필요가 없을 수도 있다. 하지만, 배열의 중간에 있는 데이터가 지속적으로 삭제되고, 추가될 경우에는 LinkedList가 배열보다 메모리 공간 측면에서 훨씬 유리하다.
배열과 같은 ArrayList와 Vector는 각 위치가 정해져 있고, 그 위치로 데이터를 찾는다.
- 맨 앞의 값을 삭제 시, 그 뒤에 있는 값들은 하나씩 앞으로 위치를 이동해야 제대로 된 위치의 값을 가진다.
그에 반해, LinkedList는 아래와 같은 이점을 가진다.
- 중간에 있는 데이터를 삭제 시, 지운 데이터의 앞에 있는 데이터와 뒤에 있는 데이터를 연결한다.
- 위치를 맞추기 위해서 값을 이동하는 단계를 거칠 필요가 없다.
LinkedList 클래스 선언부
ArrayList 클래스나 Vector 클래스와 상속 관계는 비슷하지만, AbstractSequentialList가 부모인 것을 볼 수 있다.
AbstractList와 AbstractSequentialList의 차이점은 add(), set(), remove() 등의 메소드에 대한 구현 내용이 상이하다는 정도다.
구현한 인터페이스의 목록
| 인터페이스 | 용도 |
|---|---|
| Serializable | 원격으로 객체를 전송하거나, 파일에 저장할 수 있음을 지정 |
| Cloneable | Object 클래스의 clone() 메소드가 제대로 수행될 수 있음을 지정. 즉, 복제가 가능한 객체임을 의미한다. |
| Iterable<E> | 객체가 “foreach” 문장을 사용할 수 있음을 지정 |
| Collection<E> | 여러 개의 객체를 하나의 객체에 담아 처리할 때의 메소드 지정 |
| Deque<E> | 맨 앞과 맨 뒤의 값을 용이하게 처리하는 큐와 관련된 메소드 지정 |
| List<E> | 목록형 데이터를 처리하는 것과 관련된 메소드 지정 |
| Queue<E> | 큐를 처리하는 것과 관련된 메소드 지정 |
- 앞서 말한 것처럼 List, Queue, Deque 인터페이스를 구현하고 있다.
- Deque 인터페이스를 구현하므로, 맨 앞과 끝의 데이터를 쉽게 처리할 수 있다.
생성자
LinkedList는 일반적인 배열 타입의 클래스와 다르게 생성자로 객체를 생성할 때 처음부터 크기를 지정하지 않는다.
각 데이터들이 앞 뒤로 연결되는 구조여서 미리 공간을 만들어 놓을 필요가 없기 때문이다. 따라서, 다음의 두 가지 생성자만 존재한다.
| 생성자 | 설명 |
|---|---|
| LinkedList() | 비어있는 LinkedList 객체를 생성한다. |
LinkedList(Collection<? extends E> c) | 매개 변수로 받은 컬렉션 객체의 데이터를 LinkedList 에 담는다. |
객체에 데이터를 추가하는 메소드
LinkedList 클래스는 구현한 인터페이스의 종류가 매우 많기 때문에, 메소드의 종류도 다양하다.
| 리턴 타입 | 메소드 이름 및 매개변수 | 설명 |
|---|---|---|
| void | addFirst(E e) | LinkedList 객체의 가장 앞에 데이터를 추가한다. |
| boolean | offerFirst(E e) | addFirst() 호출 |
| void | push(E e) | addFirst() 호출 |
| boolean | add(E e) | LinkedList 객체의 가장 뒤에 데이터를 추가한다. |
| void | addLast(E e) | add() 호출 |
| boolean | offer(E e) | add() 호출 |
| boolean | offerLast(E e) | addLast() 호출 |
| void | add(int index, E element) | LinkedList 객체의 특정 위치에 데이터를 추가한다. |
| Object | set(int index, E element) | LinkedList 객체의 특정 위치에 있는 데이터를 수정한다. 그리고, 기존에 있던 데이터를 리턴한다. |
| boolean | addAll(Collection<? extends E> c) | 매개 변수로 넘긴 컬렉션의 데이터를 추가한다. |
| boolean | addAll(int index, Collection<? extends E> c) | 매개 변수로 넘긴 컬렉션의 데이터를 지정된 위치에 추가한다. |
각 메소드의 이름을 보면, 매우 중복된 기능을 수행하는 메소드가 많은 것을 알 수 있다. LinkedList가 여러 종류의 인터페이스를 구현했기 때문에 이러한 상황이 발생한 것이다.
자바의 LinkedList 소스를 보면,
- 맨 앞에 추가하는 메소드는 동일한 기능을 수행하는 어떤 메소드를 호출해도
addFirst()메소드를 호출 - 맨 뒤에 추가하는 메소드는 동일한 기능을 수행하는
offer()메소드를 호출하면add()나addLast()메소드를 호출
여러 메소드를 혼용하여 사용하면 그 소스를 읽는 사람도 이해하기 힘들기 때문에 한 가지만 선정하여 사용하는 것을 권장하며, add 가 붙은 메소드를 사용하는 것이 오해의 소지가 가장 적다.
💡 참고로, LinkedList 객체를 그냥 System.out.println()으로 출력하면 객체에 들어있는 내용들이 순서대로 출력되며 대괄호로 감싸준다.
특정 위치의 데이터를 꺼내는 메소드들의 목록
맨 앞의 데이터를 가져오는 메소드는 모두 내부적으로 getFirst() 메소드를 호출한다.
| 리턴 타입 | 메소드 이름 및 매개변수 | 설명 |
|---|---|---|
| Object | getFirst() | LinkedList 객체의 맨 앞에 있는 데이터를 리턴한다. |
| Object | getLast() | LinkedList 객체의 맨 뒤에 있는 데이터를 리턴한다. |
| Object | peekLast() | LinkedList 객체의 맨 뒤에 있는 데이터를 리턴한다. |
| Object | get(int) | LinkedList 객체의 지정한 위치에 있는 데이터를 리턴한다. |
어떤 객체가 포함되어 있는지 확인하는 메소드들
데이터의 값으로 위치를 찾거나, 존재하는지를 확인한다.
| 리턴 타입 | 메소드 이름 및 매개변수 | 설명 |
|---|---|---|
| boolean | contains(Object) | 매개 변수로 넘긴 데이터가 있을 경우 true를 리턴한다. |
| int | indexOf(Object) | 매개 변수로 넘긴 데이터의 위치를 앞에서부터 검색하여 리턴한다. 없을 경우 -1을 리턴한다 |
| int | lastIndexOf(Object) | 매개 변수로 넘긴 데이터의 위치를 뒤에서부터 검색하여 리턴한다. 없을 경우 -1을 리턴한다 |
데이터를 삭제하는 메소드들
삭제 관련 메소드들은 특정 데이터를 삭제하는 메소드를 제외하고는, LinkedList 객체에서 삭제 후 삭제된 데이터를 리턴한다.
그래서 앞의 조회용 메소드보다는 이 메소드를 많이 사용한다.
💡 아래 표에서는 중복 메소드를 제거했지만, 실제로는 유사한 기능을 하는 메소드들이 많다.
앞의 이유로, 혼동을 피하려면remove()가 붙은 메소드를 사용할 것을 권장한다.
| 리턴 타입 | 메소드 이름 및 매개변수 | 설명 |
|---|---|---|
| Object | remove() | LinkedList 객체의 가장 앞에 있는 데이터를 삭제하고 리턴한다. |
| Object | removeFirst() | 맨 앞에 있는 데이터를 삭제하는 메소드들은 모두 내부적으로 이 메소드를 호출한다. |
| Object | pollLast() | LinkedList 객체의 가장 끝에 있는 데이터를 삭제하고 리턴한다. |
| Object | removeLast() | 맨 뒤에 있는 데이터를 삭제하는 메소드들은 모두 내부적으로 이 메소드를 호출한다. |
| Object | remove(int) | 매개 변수에 지정된 위치에 있는 데이터를 삭제하고 리턴한다. |
| boolean | remove(Object) | 매개 변수로 넘겨진 객체와 동일한 데이터 중 앞에서부터 가장 처음에 발견된 데이터를 삭제한다. |
| boolean | removeFirstOccurrence(Object) | |
| boolean | removeLastOccurrence(Object) | 매개 변수로 넘겨진 객체와 동일한 데이터 중 끝에서부터 가장 처음에 발견된 데이터를 삭제한다. |
그 외 메소드
| 리턴 타입 | 메소드 이름 및 매개변수 | 설명 |
|---|---|---|
| ListIterator<E> | listIterator(int index) | 매개 변수에 지정된 위치부터의 데이터를 검색하기 위한 ListIterator 객체를 리턴한다. |
| Iterator<E> | descendingIterator() | LinkedList의 데이터를 끝에서부터 검색하기 위한 Iterator 객체를 리턴한다. |
ListIterator 는 Iterator 인터페이스가 다음 데이터만을 검색할 수 있다는 단점을 보완하여, 이전 데이터도 검색할 수 있는 이터레이터다. 따라서, next() 외에도 previous() 메소드를 사용하면 이전 데이터를 확인할 수 있다.
API 문서를 보면 쉽게 이해할 수 있을 것이다.
간단 요약정리
- Set은 주로 중복되는 데이터를 처리하기 위해서 사용
- Queue는 먼저 들어온 데이터를 먼저 처리해주는 FIFO 기능을 처리하기 위해서 사용
- 특히 여러 쓰레드에서 들어오는 작업을 순차적으로 처리할 때 많이 사용된다.
정리해 봅시다.
Q. 순서와 상관 없는 여러 데이터를 하나의 객체에 저장할 때 사용하는 Collection의 하위 인터페이스는 무엇인가요?
Me: Set 인터페이스
Q. HashSet 클래스는 생성자를 통하여 저장 가능한 데이터의 초기 크기를 지정할 수 있나요?
Me: O
Q. HashSet 클래스의 객체에 데이터를 추가하는 메소드는 무엇인가요?
Me: add() 메소드
Q. HashSet 클래스의 객체에 어떤 데이터가 존재하는지 확인하는 메소드는 무엇인가요?
Me: contains() 메소드
Q. HashSet 클래스의 객체에 어떤 데이터를 삭제하는 메소드는 무엇인가요?
Me: remove() 메소드
Q. Queue는 FIFO를 처리하기 위한 클래스들의 인터페이스 입니다. FIFO는 무슨 단어의 약어인가요?
Me: First In First Out
Q. Deque는 무슨 단어의 약어이며, 용도는 무엇인가요?
Me: Double Ended Queue, 맨 앞이나 맨 뒤에 값을 넣거나 빼는 작업을 수행하는데 용이하도록 되어 있다.
Q. LinkedList 클래스의 특징을 이야기해 봅시다.
Me: List, Queue, Deque를 모두 구현했다. 각 데이터들이 앞 뒤로 연결되는 구조이기 때문에 미리 공간을 만들어둘 필요가 없다(생성자에 초기값 없음). 중간에 값을 삽입하고 제거하는 것에 뛰어난 성능을 보인다.
질문
💡 책에 있는 내용이 아닙니다.
책을 읽으며 설명이 더 필요하거나, 추가로 궁금한 점에 대해 질문 형식으로 작성 후, 답을 구해보고 있습니다.
참고한 사이트나 영상은 [출처]로 달아두었으며, 오류 지적은 언제나 환영합니다.
Q. Hashing과 Hash Function에 대하여
개념
해싱(Hashing)는 해시 함수(Hash Function)를 사용해 데이터를 고유한 식별자로 사용할 수 있는 비밀 키(Secret Key)에 매핑하는 기술이다.
이 때, 데이터로부터 이러한 키를 생성하는 함수를 해시 함수라고 하고, 해시 함수로 만들어낸 키를 해시 값(Hash-values) 혹은 해시 코드(Hash-code) 라고 한다. 또는 간단하게 해시라고 부르기도 한다.
해시 값은 배열 인덱스로 사용되는 정수일 수도 있고, 암호의 비밀 코드로 사용될 수도 있다.
해싱은 키가 크거나 정수가 아니어서 직접적으로 인덱스로 사용될 수 없는 경우에 사용할 수 있다.
자바에서의 해싱
자바에서는 데이터에 빠르게 접근하기 위해 해시 테이블이라는 배열에 Key(해시 값)와 Value(실제 데이터) 쌍으로 저장한다.
즉, 해시 테이블은 원래의 키를 해시 함수를 사용해 변환한 Key를 인덱스로 사용하고, 각 인덱스 위치에 저장된 값은 실제 데이터가 된다.
HashTable
해싱된 키에 해당하는 데이터에 대한 포인터를 보유하는 배열이다. 해시 값을 위치 인덱스로 사용하여 배열 내에 관련 데이터를 저장한다.
HashTable과 HashSet의 관계
둘 다 해시 기반의 자료 구조이지만, 아래와 같은 차이가 있다.
| HashTable | HashSet | |
|---|---|---|
| 구현한 인터페이스 | Map | Set |
| 저장하는 데이터 | 키-값 쌍 | 단일 값 |
| Thread Safe | O | X |
즉, 둘은 다른 자료구조지만 HashSet은 내부적으로 HashTable(실제로는 HashMap 인스턴스)을 이용해 데이터를 저장한다.
Hash Algorithm
해시 알고리즘은 해싱을 수행하기 위한 특정한 함수 혹은 알고리즘을 말한다.
빠르고 효율적인 핵심 작업을 위해 만들어진 알고리즘으로, 데이터의 특성에 따라 선택된다.
아래와 같은 알고리즘이 있다.
- MD5
- SHA-1
- SHA-256
Q. Load Factor란 무엇인가?
Bucket
그 전에 bucket을 먼저 알아야 한다. 해시 테이블의 bucket은 실제 데이터가 저장되는 공간이다. 주로 해시 테이블에서 충돌이 발생한 경우(아래 질문 참고) 동일한 해시 코드를 가진 데이터를 가리키는 용어로 사용한다.
1.HashMap에서 저장
예를 들어 키-값 쌍을 갖는 HashMap을 보자. 키-값 쌍에서 키의 해시 코드가 식별자(인덱스)인 bucket에 키-값 쌍을 저장한다.
bucket에 저장된 키-값 쌍을 슬롯이라고 하며, 하나의 bucket에는 여러 개의 슬롯이 저장될 수도 있다.
2.HahSet에서 저장
HashSet을 생성하면 HashMap의 인스턴스가 하나 생기고, 요소를 삽입하면 HashMap에 삽입된다.
HashMap은 내부적으로 HashTable을 사용하는 키-값 쌍의 자료구조이다.
이 때, HashMap의 요소를 해시 함수를 통해 해시 코드를 얻어내고, 이렇게 얻어낸 해시 코드를 HashMap의 Key로 저장한다.
그리고 HashMap의 Value에는 어떠한 상수(일반적으로 PRESENT 또는 null)가 들어간다. Key의 유일성만 보장되면 되므로, 이 상수는 그리 중요하지 않다.
Load Factor
로드 팩터(Load Factor)는 해시 테이블(혹은 HashSet)이 자동으로 증가하기 전에 얼마나 가득 차도록 허용했는지를 측정한 값이다.
일반적으로 로드 팩터는 해시 테이블에 저장된 원소의 수를 해시 테이블의 크기로 나눈 값을 나타내며, 기본 값은 0.75다.
로드 팩터는 임계값이라고 말할 수 있다. 해시 테이블에 저장된 데이터(원소)의 수가 이 임계값을 초과하면, 해시 테이블의 크기가 이전의 두 배로 조정된다.
HashSet의 16개의 공간과 0.75의 로드 팩터를 갖는다. 즉, 테이블의 12개의 원소가 있다면 32개로 늘어난다.
적절한 Load Factor의 사용
로드 팩터는 해시 테이블의 성능과 메모리 효율성 간의 균형을 조절하는데 도움을 준다.
로드 팩터가 높거나 낮으면
- 로드 팩터가 높으면(저장될 원소의 수가 커지면) 해시 충돌이 자주 발생할 수 있다.
- 로드 팩터가 너무 낮으면 메모리를 낭비하게 된다.
따라서, 적절한 로드 팩터를 설정해야 한다. 그러면 다음과 같은 효과를 얻을 수 있다.
- 메모리 공간을 효율적으로 사용할 수 있다.
- 해시 테이블은 일정 수준 이상으로 가득 차지 않도록 조절된다.
- 해시 충돌이 발생할 가능성을 낮춘다.
- 메모리 사용의 최적화
- 해시 테이블의 재정리(resize) 작업을 최소화하며 얻는 이점이다.
Q. 레드 블랙 트리란?
각 노드가 레드 혹은 블랙인 속성을 가지고 있는 이진 탐색 트리(Binary Search Tree, BST)이다.
조건
이진 탐색 트리의 조건에 다음과 같은 추가 조건을 만족해야 한다.
- 노드는 레드 혹은 블랙 중의 하나이다.
- 루트 노드는 블랙이다.
- 모든 리프 노드들(NIL)은 블랙이다.
- 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. (즉, 레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다)
- 어떤 노드로부터 시작되어 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.
특성
- 루트 노드부터 가장 먼 리프 노드까지의 거리가 가장 가까운 리프 노드까지의 거리의 두 배보다 항상 작다.
- 개략적으로 균형이 잡혀있다고 표현한다.
- 네번째 조건과 다섯번째 조건에 의해 띄는 특성이다.
- 삽입, 삭제, 검색에서의 시간 복잡도가 모두 O(log n)이다.
Q. Deque를 사용하는 경우
Deque는 양방향 큐로, 맨 앞의 값과 맨 뒤의 값을 추가하거나 제거하는 데 최적화되어 있다.
push나 pop 연산이 빈번한 알고리즘에서 리스트 보다 월등한 속도를 낸다고 한다.
Q. Iterator와 Enumeration의 차이
먼저, 둘 다 Collection을 순회하는데 사용되는 인터페이스이다.
- Iterator 는 Collection 인터페이스의 일부이다.
- 대부분의 자바 컬렉션에서 사용할 수 있다.
- 요소를 삭제하는 remove() 메소드를 지원해서, 순회하면서 요소를 삭제할 수 있다.
- Enumeration은 Java 1.0부터 있는 인터페이스다.
- 주로 Vector나 Properties와 같은 legacy 컬렉션에서 사용되며, 새로운 컬렉션에서는 더 이상 사용되지 않는다.
- 요소를 삭제하는 메소드를 제공하지 않아서, 순회하면서 요소를 삭제할 수 없다.
Q. Set의 중복과 해시 충돌
값의 중복
HashSet은 해시 함수를 이용하여 중복 여부를 빠르게 확인할 수 있다. 다만, 해시 충돌이 발생하면 선형 검색(처음부터 긑까지 하나씩 순서대로 비교)을 하기 때문에 성능이 떨어질 수 있다.
TreeSet은 이진 검색 트리를 기반으로 하므로, 보다 안정적인 성능을 유지한다.
Hash Collision
해시 함수로 키를 얻다 보면, 동일한 해시 코드가 반환될 수 있다. 이런 상황을 해시 충돌(Hash Collision)이라고 한다.
해시 충돌을 해결하는 여러 방법이 있는데, 대표적으로는 아래 두 가지가 있다.
- 선형 조사(Linear Probing): 충돌이 발생하면 다음 버킷으로 이동하여 비어있는 버킷을 찾아 요소를 저장
- 체이닝(Chaining): 각 버킷에 연결 리스트(Linked List)를 사용하여 충돌한 요소들을 순차적으로 저장
해시 충돌이 잦으면 해시 테이블의 성능이 떨어진다.
- 해시 충돌이 발생하면 추가적인 작업이 필요하다.
- 선형 조사에서는 다음 버킷을 찾을 때까지 선형 검색을 수행
- 체이닝에서는 연결 리스트에 요소를 추가
- 메모리 관리에서의 문제
- 체이닝 방식에서는 연결 리스트의 길이가 길어질 수록 메모리 소비가 더 커진다.
- 충돌이 발생하면 해시 테이블의 크기를 동적으로 관리해야 할 수 있다. 이렇게 크기를 동적으로 조절하면서 적절한 크기를 유지하기 위해 작업이 추가되며, 곧 성능 저하로 이어진다.
HashSet
- 삽입: 해시 함수로 해시 코드를 얻은 후, 해시 코드를 인덱스로 갖는 해시 테이블의 버켓에 저장한다.
- 해시 충돌이 발생하면 체이닝(Chaining) 방식으로 처리한다.
- 체이닝 방식: 동일한 해시 코드를 가진 요소들은 같은 버켓에 연결 리스트 형태로 저장한다.
참고 사이트
Hashing and its Use Cases in Java - Scaler Topics
