[알고리즘 개념] Map, Set, Queue

 

HashMap

TreeMap

HashSet

TreeSet

PreorityQueue

 

HashMap

• HashMap는 해싱을 기본으로 데이터를 저장한다. HashMap에는 (Key,Value) 형태로 데이터가 저장된다.
• HashMap은 삽입, 삭제, 탐색 등 모든 함수의 시간복잡도가 전부 O(1)이라는 장점이 있다.
• HashMap는 TreeMap과는 다르게 데이터의 순서는 고려하지 않는다.

 

<HashMap에서 자주 이용되는 코드>

 

1. HashMap 선언하기

 HashMap<Key의 자료형, value의 자료형> hashmap이름 = new HashMap<>();

 

2.HashMap에 데이터 넣기

m.put(Key, Value)

 

3.HashMap에 있는 데이터 제거하기

m.remove(Key)

 

4.HashMap에서 특정 key의 value값 받기

m.get(Key)

 

5. 특정 key가 HashMap에 존재하는지 확인하기

m.containsKey(Key)

 

6.특정 key가 존재하면 그 value값을 받고, 아니면 정해둔 값 입력받기

m.getOrDefault(Key, 존재x이면 반환하는 값)

 

 

TreeMap

TreeMap는 HashMap과 다르게 균형잡힌 이진트리로 데이터를 저장한다. 때문에 TreeMap에서 저장, 삭제등을 하려면 시간복잡도는 O(logN)입니다.

 

1. 선언방법

TreeMap<key자료형, value자료형> treemap명 = new TreeMap<>();

 

<TreeMap에서 자주 이용되는 코드>

 

1. TreeMap 선언하기

 HashMap<Key의 자료형, value의 자료형> hashmap이름 = new HashMap<>();

 

2. TreeMap에 데이터 넣기

m.put(Key, Value)

 

3. TreeMap에 있는 데이터 제거하기

m.remove(Key)

 

4. TreeMap에서 특정 key의 value값 받기

m.get(Key)

 

5. 특정 key가 TreeMap에 존재하는지 확인하기

m.containsKey(Key)

 

6.특정 key가 존재하면 그 value값을 받고, 아니면 정해둔 값 입력받기

m.getOrDefault(Key, 존재x이면 반환하는 값)

 

7. TreeMap 순회하기

 

Java에서는 vector, stack등의 컨테이너들을 iterator라는 반복자를 이용해 순회가 가능하다

 

iterator 참고

https://ethereal-coder.tistory.com/151

[알고리즘 개념] iterator

 

import java.util.*;
import java.io.*;
import java.math.*;


public class Main {
  public static void main(String[] args) {
      
      TreeMap<Integer, Integer> t = new TreeMap<>();
      t.put(1, 2);
      t.put(3, 4);
      t.put(5, 6);          

      // Iterator선언
      Iterator<Entry<Integer, Integer>> it = t.entrySet().iterator();
      // key 기준 오름차순으로 순회
      
      while(it.hasNext()) {
          Entry<Integer, Integer> entry = it.next();
          System.out.println(entry.getKey() + " " +  entry.getValue());
      }
  }
}

여기서 entry는 key와 value를 출력하기 위한 함수입니다.

위와 같이 하면 key값이 오름차순으로 정렬된 상태로 출력되게 key와 value가 출력됩니다.

Entry는 import java.util.Map.Entry; 를 꼭 해줘야 한다.

 

HashSet

• HashSet는 해싱을 기본으로 데이터를 저장한다
• HashSet은 삽입, 삭제, 탐색 등 모든 함수의 시간복잡도가 전부 O(1)이라는 장점이 있다.
• HashSet는 TreeSet과는 다르게 데이터의 순서는 고려하지 않는다.
• Set는 Map와 다르게 단일 데이터만 저장한다(key,value X)

 

<HashSet에서 자주 이용되는 코드>

 

1.HashSet 선언하기

HashSet<데이터의 자료형> HashSet명 = new HashSet<>();

2. HashSet에 데이터 넣기

s.add(데이터)

 

3. HashSet에 있는 데이터 제거하기

s.remove(데이터)

 

4.HashSet에 해당 데이터 있는지 확인하기

s.contains(데이터)

 

TreeSet

HashSet와 다르게 균형잡힌 이진트리로 데이터를 저장한다.

 

<TreeSet에서 자주 이용되는 코드>

 

1.TreeSet 선언하기

TreeSet<T> s = new TreeSet<>();

2. TreeSet에 데이터 넣기

s.add(데이터)

 

3. TreeSet에 있는 데이터 제거하기

s.remove(데이터)

 

4.TreeSet에 해당 데이터 있는지 확인하기

s.contains(데이터)

 

5. 특정 수보다 같거나 큰/ 작은 값중 가장 가까이 있는 값

s.ceiling(E)  // 크거나 같은
s.floor(E)  // 작거나 같은

 

없으면 Null을 반환한다.

 

6. 특정 수보다 큰/작은 값 중 가장 가까이 있는 값

s.higher(E) // 큰
s.lower(E) // 작은

없으면 Null을 반환한다.

 

7.가장 작은/큰 숫자 반환하기

s.first() //가장 작은 값
s.last() //가장 큰 값

 

PreorityQueue

Queue는 가잠 먼저 온 값이 먼저 나오는 선입선출 방식이다. 

PreorityQueue는 이와 달리 Queue내에 있는 값 중 가장 작은 값을 반환한다.

 

<PreorityQueue에서 자주 이용되는 코드>

 

1.PreorityQueue 선언하기

PriorityQueue<자료형> pq = new PriorityQueue<>();

 

2.PreorityQueue에 데이터 저장하기

pq.add(데이터)

 

3.PreorityQueue 데이터 삭제하기

pq.remove(데이터)

 

4.PreorityQueue가 비었는지 확인하기

pq.isEmpty()

 

5.PreorityQueue에서 가장 작은 데이터 확인하기

pq.peek()

 

6.PreorityQueue에서 가장 작은 데이터 내보내기

pq.poll()

 

출처

https://www.codetree.ai/missions/8/problems/hashmap-basic/introduction