39강 컬렉션 프레임 웍4 / Map

<복습>
컬렉션 프레임웍(Collection Framework)이란?
       : 데이터를 효율적으로 다루기 위한 클래스들의 집합
- 자료구조(Data Structure)
       : 자료들을 저장할 때, 효율적인 구조로 저장하는 것(데이터의 구조)
- 컬렉션 프레임워크
       : 자바에서 제공하는 자료구조
<컬렉션 프레임워크의 종류>
- Set 인터페이스 
       : 집합, 중복된 데이터를 갖지 않으며 저장 순서를 유지하지 않은 자료구조
        -> 대표클래스 : HashSet, TreeSet
- List 인터페이스 
       : 데이터를 일렬로 늘어놓은 구조, 허용하고 저장 순서를 유지
        -> 대표클래스 : ArrayList, LinkedList
- Queue 인터페이스
       : 선입선출의 구조, front에선 삭제 rear에선 삽입 발생
        -> 대표클래스 : ArrayList, LinkedList(List 클래스 활용)
- Stack 클래스
       : 후입선출의 구조, top에서 삽입과 삭제 발생
        -> Vector 클래스를 상속받아, 필드 사용 가능, Stack 자체 클래스 사용

39-1 ) Map 
       Map?
              : 키를 통해서 값을 참조할 수 있는 구조
       특징
              - 인터페이스이기 때문에 사용하려면 업캐스팅이 필요
              - Map를 구현한 대표클래스 : HashMap, TreeMap

       <Map에서 제공하는 메서드>

39-2 ) HashMap
       HashMap
              : Key와 Value값으로 데이터를 저장하는 형태
       특징
              - Map 인터페이스의 한 종류
              - Map의 모든 속성을 갖고 있으며 저장 방식 동일
              - 해싱(Hashing)이라는 검색 알고리즘 사용
              - key의 중복은 허용하지 않으나 value의 중복은 허용

       <HashMap 구조>

       해싱(Hashing)이란? -> 검색알고리즘이다!
              - 알고리즘
                       : 문제를 해결하기 위한 절차적인 해결과정
              - 검색알고리즘 
                       : 자료구조 내의 데이터 중 원하는 데이터를 찾는 과정
              - 배열에 저장된 데이터를 가장 빨리 찾는 방법?
                       : 저장된 데이터가 몇 번째 위치하는지를 알아오는 것

       다음 배열[10, 0, 0, 14, 20]에서 20을 찾기 위해선?
           => 20이 저장된 위치를 모를 경우, 처음 위치부터 끝까지 비교
                따라서, 데이터를 넣을 때 해당 데이터의 값을 위치 값으로 하면
                가장 빠르게 데이터를 찾아올 수 있다.

                즉, 20번을 찾을 경우, "20번째 위치에서 가져와"라고 한다면 제일 빠름

                하지만, 입력개수 < 입력최댓값 일 때는, 메모리낭비가 심하다는 단점 발생
                따라서 찾을 값(key)를 갖고 저장된 위치를 알수 있고,
                메모리 낭비를 최소화해주는 방법이 바로 "해싱"이다.

        따라서 해싱이란?
                메모리낭비를 최소화하기 위해 저장할 값 입력 받을 시,
                연산을 통해 새로운 주소 값을 생성하여 메모리에 저장(매핑, mappint)하는 기법

        해싱의 구조
                 - 키 값을 해시 값으로 변경해주는 해시 함수
                 - 변경된 해시 값으로 저장할 공간인 해시 테이블


        <실습>Map1
        HashMap을 사용하여 간단하게 사전(dictionary) 프로그램을 만들어보기