선형자료구조 - 해시, 해시테이블, 해시맵, 해시표

해시 테이블(Hash Table) = 해시맵, 해시표

해시함수를 사용하여 키를 해시 값으로 매핑하고, 이 해시 값을 색인(index)삼아 
데이터의 값(Value)를 키(key)와 함께 저장하는 자료구조를 해시 테이블 이라고 함
이 때 데이터가 저장되는 곳을 버킷(bucket) 또는 슬롯(slot) 이라고 함

해시테이블(= 해시맵, 해시표)은 키를 통해 해당 데이터에 빠르게 접근이 가능함.

해시 충돌

해시 테이블에 같은 공간에 서로 다른 값을 저장하려는 경우
-> 서로 다른 키의 해시 함수를 통한 해시 값이 동일한 경우
해시 충돌이 일어나 원하는 결과를 얻을 수 없음

해시 충돌을 해결하는 방법에는 선형탐사법, 제곱탐사법, 이중해싱, 분리연결법 등 방법으로 해결할 수 있음
이와 관련된 내용은 추후에 정리할 예정 이미지만 잘 기억해 놓기

해시테이블(해시맵) 주요 메서드

package day018;

import java.util.HashMap;

public class HashMapReviewTest {
    public static void main(String[] args) {
        // 해시맵 선언
        // public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
        // K: 지도에서 관리하는 키의 데이터 유형입니다. 키는 고유해야 합니다.
        // V: 유지되는 값의 데이터 타입입니다. 값은 고유하지 않아도 됩니다. 중복될 수 있습니다.
        HashMap<String, Integer> memberInfo = new HashMap<>();

        // 데이터 삽입
        memberInfo.put("loopy", 1001);
        memberInfo.put("dooly", 1002);
        memberInfo.put("ddochi", 1003);
        memberInfo.put("michael", 1004);
        System.out.println(memberInfo); // {michael=1004, loopy=1001, dooly=1002, ddochi=1003}

        // map 정보 확인
        System.out.println(memberInfo.entrySet()); // [michael=1004, loopy=1001, dooly=1002, ddochi=1003] , Set으로 반환
        System.out.println(memberInfo.keySet()); // [michael, loopy, dooly, ddochi] , key만 Set으로 반환
        System.out.println(memberInfo.values()); // [1004, 1001, 1002, 1003] , 모든 요소의 값만 묶어서 반환

        // key의 값 반환 못찾으면 null
        System.out.println(memberInfo.get("loopy")); // 1001

        // getOrDefualt - 지정된 키의 값을 반환, 키를 못찾으면 기본값으로 지정된 객체를 반환
        System.out.println(memberInfo.getOrDefault("nobody", -9999)); // -9999
        System.out.println(memberInfo.getOrDefault("ddochi", -9999)); // 1003

        // 삭제 - HashMap에 지정된 키로 저장된 값(객체)를 제거
        memberInfo.remove("michael"); // 1003
        System.out.println(memberInfo); // {loopy=1001, dooly=1002, ddochi=1003}


    }
}

 

해시맵과 관련 문제 - 한 번만 등장한 문자

문제 설명

문자열 s가 매개변수로 주어집니다. s에서 한 번만 등장하는 문자를 사전 순으로 정렬한 문자열을 return 하도록 solution 함수를 완성해보세요. 한 번만 등장하는 문자가 없을 경우 빈 문자열을 return 합니다.

    

import java.util.Arrays;
import java.util.HashMap;

public class ProgrammersTest1 {
    public static String solution(String s) {
        HashMap map = new HashMap<>();
        for (char ch : s.toCharArray()) {
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }
        StringBuilder sb = new StringBuilder();
        for (char key : map.keySet()) {
            if (map.get(key) == 1) {
                sb.append(key);
            }
        }
        System.out.println(map);
        String result = sb.toString();
        char[] answer = result.toCharArray();
        Arrays.sort(answer);
        return String.valueOf(answer);
    }

    public static void main(String[] args) {
        System.out.println(solution("abcabcadc"));
        System.out.println(solution("abdc"));
        System.out.println(solution("hello"));
    }
}

    
  

문제출처 : https://school.programmers.co.kr/learn/courses/30/lessons/120896