자료구조 Map과 Set

Sorbet·2021년 3월 17일
0

codesquad

목록 보기
6/20

사실

  • 자료구조를 안배웠지만, 윤성우님의 "열혈 자료구조" 로 독학을 했습니다. 나름 꼼꼼하게 봤다고 생각하는데, Map 과 Set 자료구조는 없어서, 따로 공부 필요성을 느껴 정리해봅니다

map

map 자료구조의 특징

  • 탐색 가능하다(searchable)
  • 중복되지 않는 키들의 모임
  • key, value로 이루어지는 pair(쌍, 묶음)이다
  • 각각의 key는 반드시 unique하다 (똑같은 key를 가진 entry가 존재하지 않는다, 키는 중복을 허용하지 않음
    : 주민등록번호, 핸드폰번호가 key이다.
  • value는 중복이 가능하다, key 값은 중복 될 수 없지만
    : 다 key를 입력파라미터로 넣어줬을때, value 가 리턴되는 구조로 동작
    : 여담으로, 키로 벨류를 얻는게 있는데, 벨류에서 키를 얻어야 하는 경우가 있었는데, 의외로 간단하지 않았다
    • for문으로 선형탐색 돌리거나
    • 벨류도 중복되지 않는 전제조건이 있다면
      <Key,Value>
      <Value,Key>
      • 키와 벨류가 대칭되는 inversmap 을 만들어 쓰고 빨리 끝내버렸다. 근데 다시 돌아간다 해도 딱히 좋은 생각은 안나는데, 차라리 map 말고 set을 쓰면 어떨까?
  • 참고로, 99.9%확률로 map 자료구조도 Thread-Safe하지 않기때문에, mutilThread 환경에서 안전한 사용을 위해서는 synchronizedMap 이라는걸 사용해야 한다.

예제코드

public class HashMapTest {
public static void main(String[] args) {

    Map<Inteager, String> map = new HashMap<Inteager, String>();   
    
    //put을 사용해 데이터를 넣음
    testMap.put(123,"알래스카");
    testMap.put(456,"무한도전");
    testMap.put(789,"유재석");

    
    System.out.println(testMap.get(123));
    System.out.println(testMap.get(456));
    System.out.println(testMap.get(789));
    
    //containsKey로 특정 키가 존재하는지 확인 할 수 있다.
    //true, false로 리턴해준다
    int cadidiate_Key = 111;
    if(testMap.containsKey(cadidiate_Key)) {
        System.out.println(testMap.containsKey(cadidiate_Key));
    }
    }
}

사용가능한 메서드 목록

출처 : https://docs.oracle.com/javase/8/docs/api/java/util/Map.html

  • 많이 쓰는거 몇개 소개해보자면
    : 탐색(search), 삽입(insertion), 삭제(deletion) , equals, iscontain 등등..

SET 자료구조

출처 : https://velog.io/@taeha7b/datastructure-set

특징

  • 비순차적 Unorderd
  • 중복되지 않는 값들의 모임
  • 순열 Collection 방식이므로,
    : map과 달리 key, value로 이루어지는 pair(쌍, 묶음)일 필요가 없다
  • 삽입 순서대로 저장되지 않아 순서정보가 사라짐
  • 일반적으로는 중복을 허용하지 않아 동일한 값 입력시 마지막 값 하나만 저장됨
    • 하지만, 파이썬의경우 중복을 허용하는 SET이 기본이였던 적이 있고, 언어마다 구현이 다르므로 주의
  • 사용처
    • 중복된 값을 거를때(if문 등을 사용하지말고, 존재여부 판단을 위한 Lookup테이블 등에 사용
const nums = new Set();
nums.add('one');
nums.add('two');
nums.add('three');
nums.add('three'); // 중복된 값은 무시됨

console.log(nums.size) // 3 -> 중복 값은 안들어감

for(let v of nums) {
  console.log(v)
}
/*
one
two
three
*/
profile
Sorbet is good...!

0개의 댓글