[240609] 배울 게 태산

🔶해시

---

≣ 목차

/ 오늘의 TIL /

---

해시

해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조이다.

해시는 키(key)를 활용해 데이터 탐색을 빠르게 할 수 있다.

키와 데이터를 일대일 대응하여 저장한다.

 

해시 함수

• 나눗셈법
• 곱셈법
• 문자열 해싱

해시는 단방향으로 동작한다.

해시테이블: 키와 대응한 값이 저장되어 있는 공간. 각 데이터를 '버킷' 이라고 한다.

 

충돌 처리

• 체이닝
  • 해시 테이블 공간 활용성이 떨어짐
  • 검색 성능이 떨어짐
• 개방 주소법
  • 선형 탐사 방식
• 이중 해싱 방식

 

자바에서 HashSet, HashMap 이라는 표준 API를 제공한다.

HashMap 클래스는 체이닝을 사용하여 해시 충돌을 처리하는데, 충돌 발생 시 데이터 접근 시간 복잡도가 O(N)으로 늘어나는 문제가 있으므로 LinkedList로 연결하는 데이터가 일정 개수가 넘어가면 자동으로 해당 LinkedList를 이진 탐색 트리(Binary Search Tree)로 변환하여 데이터 접근에 O(logN) 성능이 나오도록 개선해야 한다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/42576

프로그래머스

숏코딩

map.getOrDefault(p, 0): 값이 있으면 가져오고, 없으면 0으로 세팅하기

import java.util.HashMap;

class Solution {
    /**
     * @param participant 선수 이름
     * @param completion 완주한 선수 이름
     * @return 완주하지 못한 선수 이름
     */
    public String solution(String[] participant, String[] completion) {
        
        String mem = "";
        HashMap<String, Integer> map = new HashMap<>();
        
        for (String p : participant) map.put(p, map.getOrDefault(p, 0) + 1);
        for (String p : completion) map.put(p, map.get(p) - 1);

        for (String k : map.keySet()) {
            if (map.get(k) != 0) mem = k;
        }

        return mem;
    }
}

풀이

import java.util.HashMap;

class Solution {
    /**
     * @param participant 선수 이름
     * @param completion 완주한 선수 이름
     * @return 완주하지 못한 선수 이름
     */
    public String solution(String[] participant, String[] completion) {

        HashMap<String, Integer> map = new HashMap<>();

        //map 초기화
        for (String k : participant) {
            if (map.containsKey(k)) {
                int value = map.get(k) + 1;
                map.replace(k, value);
            } else {
                map.put(k, 1);
            }
        }
        
        for (String k : completion) {
            int value = map.get(k) - 1;
            map.replace(k, value);
        }

        //value가 0 이상이면 완주하지 못한 선수이다.
        String mem = "";
        for (String k : map.keySet()) {
            if (map.get(k) > 0) {
                mem = k;
            }
        }
        return mem;
    }
}