Map
java에서 Map 인터페이스를 구현한 클래스들은 key, value 형식으로 데이터를 하나의 쌍으로 저장한다**.**
- 요소의 순서를 유지하지 않는다.
- key의 중복을 허용하지 않는다.
HashMap
HashMap은 Map 인터페이스의 구현체이고 해싱(hashing)을 사용한다.
해싱(hashing) : 해시 함수를 사용하여 입력 값을 고정된 크기의 문자열로 만든다.
순차적 접근 방식을 사용한다면 O(N)의 시간 복잡도가 필요하다.
만약 배열을 사용하여 인덱스로 접근을 한다면 O(1)의 시간 복잡도가 필요하다.
HashMap에 들어온 key 값을 해시 함수로 정수로 바꾸어서 배열의 인덱스로 사용한다면 O(1) 시간 복잡도로 값을 찾을 수 있다.
해시 함수로 변환한 정수의 값이 너무 클 경우 배열의 크기가 너무 크기 때문에 처음에는 크기가 16인 배열을 사용한다.
해시 함수로 변환한 정수를 바로 사용하지 않고 15(1111)와 비트 단위의 AND 연산을 적용하여 크기가 16인 배열에 들어갈 수 있도록 한다.
만약 인덱스의 중복이 발생할 경우 연결 리스트로 연결해서 사용한다.
충돌이 많아서 버킷의 데이터 개수가 늘어나면 연결 리스트에서 tree 구조로 변경하여 사용한다.
즉, key에 해시 함수를 적용하여 정수로 바꾸고 15와 비트 단위 AND 연산을 적용하여 배열의 인덱스로 사용한다.
배열의 크기가 어느 정도 차면 배열의 크기를 늘린다.
삽입과 조회 모두 O(1)의 시간 복잡도가 필요하다.
- put : O(1)
- get : O(1)
- containsKey : O(1)
- containsValue : O(1)
import java.util.HashMap;
import java.util.Map;
public class Main{
public static void main(String[] args){
Map<String, String> map = new HashMap<>();
map.put("key", "value");
map.get("key");
}
}
Set
java에서 Set 인터페이스를 구현한 클래스들은 key, value 형식으로 데이터를 하나의 쌍으로 저장한다**.**
- 객체를 저장할 수 있다.
- 객체가 중복될 수 없다.
HashSet
HashSet은 내부적으로 HashMap을 사용한다.
HashSet에 넣으려는 Object를 key로 사용하고 value는 특정 상수 값을 사용하기 때문에 HashSet 내부 HashMap의 모든 value는 동일한 상수 값을 가진다.
HashMap의 key는 중복될 수 없기 때문에 HashSet에 들어가는 Object도 중복될 수 없다.
import java.util.HashSet;
import java.util.Set;
public class Main{
public static void main(String[] args){
Set<String> set = new HashSet<>();
set.add("hello");
set.add("world");
set.remove("hello");
}
}
삽입과 조회 모두 O(1)의 시간 복잡도가 필요하다.
- add : O(1)
- remove : O(1)
- contains : O(1)
Queue
LinkedList
import java.util.LinkedList;
import java.util.Queue;
public class Main{
public static void main(String[] args){
Queue<String> queue = new LinkedList<>();
queue.add("hello");
String s = queue.remove();
}
}
- 객체의 순서가 보장된다.
- 먼저 넣은 객체가 먼저 나온다.
- add : O(1)
- remove : O(1)
PriorityQueue
우선순위에 따라 저장된 객체가 나온다.
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;
public class Main{
public static void main(String[] args){
Queue<Integer> queue = new PriorityQueue<>();
queue.offer(3);
queue.offer(5);
queue.offer(2);
queue.offer(1);
while (!queue.isEmpty()){
System.out.println(queue.poll());
}
}
}
default는 우선 순위가 낮은 객체부터 나온다.
우선 순위를 변경할 수 있다.
Queue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
만약 커스텀 클래스가 들어간다면 Comparable과 Comparator를 통해 우선 순위를 정할 수 있다.
우선 순위를 정할 때 overflow를 고려해야 한다.
<Comparable>
public static class Node implements Comparable<Node> {
int x;
int y;
Node(int x, int y){
this.x = x;
this.y = y;
}
@Override
public int compareTo(Node node){
// 같으면 y 내림차순
if (this.x == node.x){
return Integer.compare(node.y, this.y);
}
// x 오름차순
return Integer.compare(this.x, node.x);
}
}
댓글