💪🏻 programmers 고득점 Kit - 해시(Hash)

해시(Hash)

고정된 크기로 값을 바꾸는 함수나 알고리즘. 이 결과로 만들어진 값을 해시코드(hash code) 혹은 해시 값(hash value)라고 부른다.

해시는 왜 사용하는 것일까?

• 보통 책에는 목차가 존재한다. 예를들어 1,000페이지가 넘는 책에서 어떤 내용을 찾을 때 목차가 없거나 운이 나쁘다면 1,000페이지에서 해당 내용을 찾을 수 있다. 하지만 목차가 있다면 원하는 내용을 빠르게 찾을 수 있게된다.

-> 이처럼 쉽게 찾을 수 있도록 도와주는 목차는 해시코드(hash code)를 의미한다.

-> 고정된 크기는 목차의 개수를 의미한다.

즉, 해시는 보다 빠르게 찾기위해 존재한다.

해시 함수(hash function) : 해시 코드를 만들어내는 함수를 의미

🔊 좋은 해시 함수 조건

1. 계산 속도가 빨라야 한다.
2. 결과 값이 다양해야 한다.

🔊 해시 충돌

서로 다른 대상(key 값)이 동일한 해시 값을 가지는 현상

❓ 해시 충돌은 왜 발생할까?

해시 충돌은 완벽한 해시 함수 구현의 어려움에서 발생한다. 해시 함수는 입력값의 범위가 사실상 무한대에 가깝기 때문에, 다양한 입력값을 고정된 크기의 출력값으로 매핑하는 과정에서 충돌이 발생할 수 있다. 예를 들어, 입력값은 문자열, 숫자 등 다양한 데이터로 이루어질 수 있지만, 해시 함수는 고정된 크기의 출력값(예: 4바이트 정수형 또는 256비트 값 등)으로 변환한다. 이러한 제한된 공간 내에서 서로 다른 입력값이 동일한 출력값을 가질 수밖에 없는 경우가 생기는데, 이를 해시 충돌이라고 한다.

해시 충돌 해결 방법

📌 개별 체이닝(seperate chaining) : 분리연결법

• 충돌이 발생하면 연결된 새로운 공간을 사용하는 방법 -> LinkedList

이미지 출처

1. 키(key)의 해시 값을 계산한다.
2. 해시 값을 이용해 배열의 인덱스를 구한다.
3. 같은 인덱스가 있다면 LinkedList로 연결한다.

충돌이 발생한 '윤아', '서현'은 다음 아이템인 '서현'의 형태로 서로 연결 리스트로 연결된다.

-> 쉽게 아파트처럼 모여있다고 생각하면 좋다. '윤아'는 2층 1호, '서현'은 2층 2호

• LinkedList를 사용하기 때문에 보다 유연하게 사용할 수 있고 해시 값을 그대로 사용할 수 있지만 LinkedList를 사용한다는 것은 추가적인 공간이 필요하다는 의미이다. 따라서 연속된 데이터가 아니기 때문에 캐시의 도움을 받기 어렵다.

• LinkedList는 검색 시 O(n) 만큼의 시간이 소요된다.

📌 오픈 어드레싱(oepn addressing) : 개방주소법

• 충돌이 발생하면 다른 해시 코드(버킷)를 사용하는 방법. 인접한 빈 공간에 저장

이미지 출처

1. 선형 탐사(Linear Probing) : 충돌 시 다음 버킷, 혹은 몇개를 건너뛰어 데이터 삽입
2. 제곱 탐사(Quadratic Probing) : 충돌 시 제곱만큼 건너뛴 버킷에 데이터를 삽입
3. 이중 해시(Double Hashing) : 충돌 시 다른 해시 함수를 한번 더 적용한 결과를 이용

• 고정된 크기의 배열을 사용하기 때문에 추가적인 공간을 필요로 하지 않는다. 데이터가 적을 땐 개별 체이닝보다 좋은 성능을 보인다. 연속된 공간을 사용하기 때문에 CPU가 빠르게 찾을 수 있기 때문이다.

• 하지만 데이터가 많아지면 캐시에서 찾는 값을 꺼내올 확률이 줄어들어 좋은 캐시의 성능을 기대할 수 없다.

• 충돌이 발생했을 때 다음 빈 공간을 찾기 어려워지고 값이 자주 추가되고 삭제된다면 성능이 떨어진다.

HashMap

key의 중복을 피하기 위해 해시를 사용하는 Map 자료구조이다.

• Java의 HashMap은 해시 충돌을 개별 체이닝 방식으로 대응한다.

보조 해시 함수 : 해시 값이 더 균등하게 나올 수 있게 도와주는 함수

HashTable

• HashMap과 유사한 자료구조

• Map에서는 key와 value 모두 null을 사용할 수 있지만 Table에서는 사용할 수 없다.

-> 해당 문제를 해결하기 위해 Java 1.5 이후부터 ConcurrentHashMap을 지원한다.

• HashTable은 Thread-safe 하지만 성능이 부족해서 ConcurrentHashMap을 사용해서 쓰레드 안정성을 챙기면 된다.

HashMap과 HashTable 차이점

• HashTable은Java의 API. 컬렉션 프레임워크가 만들어지기 전에 존재하던 것이지만 호환을 위해 남겨둔 것이고 HashMap은 Java Collections Framework API이다.

• HashTable은 syncronized 키워드가 있어 동기화를 진행하지만 HashMap의 경우 syncronized 키워드가 없어서 멀티스레드 환경에서 데이터 무결성을 보장하지 않는다.

• HashTable은 Key에 null이 들어오면 NullPointerError를 던지지만 HashMap은 Key에 null이 들어오면 0으로 해싱하여 저장한다.

HashSet

• 내부적으로 HashMap을 사용한다.

• Map 자료 구조의 key가 중복될 수 없다는 점을 이용해 set이라는 자료 구조의 특징을 살렸다.

• key로는 저장할 데이터를, value 값은 내부적으로 생성되어 있는 dummy를 사용한다.

Red-Black Tree

LinkedList는 자료 구조 검색 시 O(n)의 시간을 소요한다. -> 이 문제를 해결하기 위해 Java는 Tree 자료 구조를 활용한다.

Java는 충돌이 발생한 경우 Seperate Chaining을 LinkedList로 구현해 충돌에 대응하였다. 그러나 Java 8부터 데이터의 개수가 일정 이상일 때는 기존에 사용하던 LinkedList 대신 Tree를 사용한다.

데이터가 n번 충돌해 연결 리스트의 n번째 노드에 저장된다면 해당 노드 탐색을 위한 시간복잡도는 O(n)이 된다.

따라서 충돌이 많아질수록 효율이 점점 떨어지기 때문에 일정 충돌 수가 넘어가면 트리 방식을 사용해 성능을 O(log n)으로 개선한다.

Java8의 HashMap에 들어가서 확인하면 상수로 기준이 정해져 있다.

하나의 해시 버킷에 8개의 key-value 쌍이 모이면 LinkedList를 Tree로 변경하고 데이터를 삭제해 개수가 6개가 되면 다시 LinkedList로 변경한다.

여기서 차이가 1이 아닌 2인 이유는 어떤 한 key-value 쌍이 반복되어 삽입/삭제가 되는 경우 불필요하게 Tree와 LinkedList를 반복적으로 변경해 성능 저하가 발생할 수 있기 때문이다.

또, 데이터의 개수가 6 이하일 때 LinkedList로 다시 변경하는 이유는 데이터 개수가 적을 때 LinkedList의 최악의 경우 수행 시간 차이가 많지 않고 Tree는 LinkedList보다 메모리 사용량이 많기 때문이다.

특히 Red-Black Tree 라는 검색에 최적화된 트리 구조를 사용한다.

이미지 출처

• Java는 데이터의 일정 충돌 수가 넘어가면 Red-Black Tree로 데이터를 저장한다. 우선 데이터 개수가 많기 전에는 Node 객체로 LinkedList를 구현했지만 Red-Black Tree는 단순 Node 객체로 구현할 수 없다.

1. Node 객체를 treeifyBin 메서드를 통해 TreeNode 객체로 바꿔준다.

2. treeify 메서드를 통해 parent, left, right 필드와 Red-Black Tree 로직을 위한 적절한 값을 넣어준다.

🔊 Java 8 이후로, 기존에 LinkedList로 Chainning 기법을 사용한 TreeMap을 Red-Black Tree로 변경하여 시간복잡도를 O(n)에서 O(logn)으로 줄일 수 있다.

포켓몬 - 프로그래머스

해당 문제는 매개변수로 입력 받는 정수에서 N/2 마리를 선택할 때 가장 많은 종류의 포켓몬을 선택하는 방법을 구하는 문제이다.

[3, 1, 2, 3] 일 경우

• (3, 1)
• (3, 2)
• (3, 3)
• (1, 2)
• (1, 3)
• (2, 3)

으로 6가지의 경우이지만 포켓몬 종류 수의 최대값은 2이다.

[3, 3, 3, 2, 2, 2] 일 경우

• (2, 3) 으로 최대값은 2이다.

여기서 HashSet은 중복을 허용하지 않는다.

즉, [3, 1, 2, 3]의 set.size()는 3이다.

import java.util.*;
class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        int num = nums.length/2;
        
        HashSet<Integer> set = new HashSet<>();
        
        for(int i=0;i<nums.length;i++)
        {
            set.add(nums[i]);
        }
        
        if(num < set.size())
        {
            answer = num;
        }
        else{
            answer = set.size();
        }
        
        return answer;
    }
}

1. 먼저 HashSet을 선언하고 nums를 set에 추가한다.

2. num의 값이 set의 사이즈보다 작다면 num이 답이 된다.

• [3, 1, 2, 3] 에서 num = 2, set.size() = 3인데, num < set.size()이므로 num이 닶

1. num의 값이 set의 사이즈보다 크다면 set.size()가 답이 된다.

• [3, 3, 3, 2, 2, 2] 에서 num = 3, set.size() = 2 인데, num > set.size()이므로 set.size()가 닶

완주하지 못한 선수 - 프로그래머스

해당 문제는 마라톤에 참여한 선수들의 이름이 담긴 배열 participant, 완주한 선수들의 이름이 담긴 배열 completion, 완주하지 못한 선수의 이름을 구하는 문제이다.

여기서 참가자 중에 동일한 이름이 있을 수 있고 key-value를 사용하여 빠르게 찾아야 되므로 HashMap을 사용한다.

import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        
        Map<String, Integer> map = new HashMap<>();
        
        for(String s : participant)
        {
            map.put(s, map.getOrDefault(s, 0)+1);
        }
        
        for(String s : completion)
        {
            map.put(s, map.get(s)-1);
        }
        
        for(String s : map.keySet())
        {
            if(map.get(s) > 0)
            {
                answer = s;
             //   break;
            }
        }
        
        return answer;
    }
}

1. 먼저 HashMap을 선언한다.

2. 향상된 for문을 이용해서 s에 participant의 값을 대입하고 map에 put 메서드를 이용해 추가한다. 여기서 map.getOrDefault(s, 0)는 해당 이름 s가 이미 저장되어 있으면 그 값을 가져오고 그렇지 않을 경우 0을 반환한다. +1을 해준 이유는 횟수를 세기 위함이다.

3. 향상된 for문을 이용해서 s에 completion 값을 대입하고 map에 put 메서드를 이용해 추가한다. 여기서 map.get(s)-1은 현재 map에 저장된 s를 가져와서 -1을 수행한다.

4. map.keySet()은 map의 모든 키를 순회한다.

전화번호 목록 - 프로그래머스

해당 문제는 전화번호부에 적힌 전화번호를 담은 배열이 주어지고 어떤 번호가 다른 번호의 접두어에 있을 경우 false, 그렇지 않을 경우 true를 반환하는 함수를 구하는 것이다.

1. HashMap을 선언한다.

2. map에 phone_book 배열의 값을 추가한다.

3. 이중 for문을 사용하여 map에 특정 키가 존재하는지 확인한다. 여기서 substring을 사용하여 0부터 자기자신까지 확인한다.

• [12, 13, 123]을 예시로 든다면 phone_book[2] 일 때, substring(0,1) -> 1, substring(0,1) ->2 이므로 “12”와 겹치므로 false가 된다.

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
       
        Map<String, Integer> map = new HashMap<>();
        
        for(String s : phone_book)
        {
            map.put(s, map.getOrDefault(s,0));
        }
        
        for(int i=0;i<phone_book.length;i++)
        {
            for(int j=0;j<phone_book[i].length();j++)
            {
                if(map.containsKey(phone_book[i].substring(0,j)))
                {
                    return false;
                }
            }
        }
        
        return true;
    }
}

배열의 length : 상수 값으로 저장된 크기를 단순히 읽음. 자바에서 속성으로 구현되어 있고 이는 배열의 크기를 상수 값으로 저장하고 반환하는 방식.

문자열의 length() : 문자열의 길이를 계산하거나 반환하는 로직이 포함될 수 있음. 메서드로 구현되어 있고 내부적으로 문자열의 길이를 계산해서 반환함.

그 외의 신박했던 풀이

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        Arrays.sort(phone_book);
        
        for(int i=0;i<phone_book.length-1;i++)
        {
            if(phone_book[i+1].startsWith(phone_book[i]))
            {
                return false;
            }
        }
        
        return answer;
    }
}

의상 - 프로그래머스

해당 문제는 각 종류별로 최대 1가지 의상만 착용할 수 있으며 옷을 조합하여 나오는 경우의 개수를 구하는 것이다.

[["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]

해당 예제를 보면 headgear이 (yellow_hat, green_turban) 2개, eyewear이 (blue_sunglasses) 1개이다. 그러면 나오는 경우는 다음과 같다.

1. yellow_hat
2. blue_sunglasses
3. green_turban
4. yellow_hat + blue_sunglasses
5. green_turban + blue_sunglasses

이는 headgear 개수 2와 eyewear의 개수 1에 1씩 더한 뒤 곱하고 마지막에 모두 안 입는 경우(1)를 빼주면 된다.

• headgear: 2개의 아이템 + 1 (아무것도 안 입음) → 3가지 선택
• eyewear: 1개의 아이템 + 1 (아무것도 안 입음) → 2가지 선택

조합의 전개

1. yellow_hat을 선택했을 때:

   • yellow_hat + blue_sunglasses
   • yellow_hat + 아무것도 안 입음

2. green_turban을 선택했을 때:

   • green_turban + blue_sunglasses
   • green_turban + 아무것도 안 입음

3. 아무것도 안 입음을 선택했을 때:

   • 아무것도 안 입음 + blue_sunglasses
   • 아무것도 안 입음 + 아무것도 안 입음

(2+1)×(1+1)=6이고 아무것도 입지 않는 경우를 제외해야 하므로 1을 빼준다. 6−1=5가 된다.

import java.util.*;
class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        
        Map<String, Integer> map = new HashMap<>();
        
        for(String[] s : clothes)
        {
            map.put(s[1], map.getOrDefault(s[1], 0)+1);
        }
        
        for(String s: map.keySet())
        {
            answer *= map.get(s) + 1;
        }
        
        return answer-1;
    }
}

• map.put(s[1], map.getOrDefault(s[1], 0)+1); 를 보면 map에 key 부분에는 s[1]의 값을 넣고, value 부분에는 s[1]이 있으면 그 값을 넣고 없으면 0+1을 대입한다.

• map.keySet()은 map의 모든 키를 순회

• map.get(s) 는 map에 저장된 s를 가져옴.

달리기 경주 - 프로그래머스

import java.util.*;
class Solution {
    public String[] solution(String[] players, String[] callings) {
        Map<String, Integer> map = new HashMap<>();
        
        for(int i=0;i<players.length;i++)
        {
            map.put(players[i], i); // 이름, 순위
        }
        
        for(String calling : callings)
        {
            int grade = map.get(calling); // 호출된 이름의 현재 순위
            
            String forwardCalling = players[grade-1]; // 해당 순위 직전의 players 이름을 가져옴
            
            players[grade-1] = calling; // 호출한 플레이어를 앞으로 이동
            map.put(calling, grade -1); // map에서 순위 한칸 앞으로 이동
            
            players[grade] = forwardCalling; // 앞에 있던 플레이어 뒤로 이동
            map.put(forwardCalling, grade); //map에서 순위 업데이트
        }
        return players;
    }
}

베스트 앨범 - 프로그래머스

아래는 제공된 Java 코드에 대해 한 줄씩 주석을 추가하여 해석한 것입니다. 그리고 Entry에 대한 설명도 포함하였습니다.

---

코드 설명 및 주석

import java.util.*; // 다양한 Java 유틸리티 클래스들(ArrayList, HashMap, Entry 등)을 사용하기 위해 import
import java.util.Map.Entry; // Map의 내부 인터페이스 Entry를 사용하기 위해 import

class Solution {
    public int[] solution(String[] genres, int[] plays) { // 장르 배열과 재생 수 배열을 입력받아 베스트 앨범에 포함된 노래 인덱스를 반환하는 함수
        int[] answer = {}; // 최종 결과를 담을 배열 선언
        
        ArrayList<Integer> answerList = new ArrayList<>(); // 결과를 저장할 ArrayList(동적으로 크기를 관리 가능)
        Map<String, Integer> map = new HashMap<>(); // 장르별 총 재생 수를 저장할 HashMap
        
        for(int i = 0; i < genres.length; i++) { 
            // 각 장르별로 재생 수 합계를 계산하여 HashMap에 저장
            map.put(genres[i], map.getOrDefault(genres[i], 0) + plays[i]); 
            // map.getOrDefault(key, defaultValue)는 key가 존재하면 값을 반환하고, 없으면 기본값(defaultValue)을 반환
        }
        
        // map의 entrySet()을 사용해 장르와 재생 수를 List로 변환
        List<Entry<String, Integer>> genresList = new ArrayList<>(map.entrySet()); 
        // 장르별 총 재생 수를 기준으로 내림차순 정렬
        Collections.sort(genresList, new Comparator<Entry<String, Integer>>() {
            public int compare(Entry<String, Integer> o1, Entry<String, Integer> o2) {
                return o2.getValue().compareTo(o1.getValue()); 
                // o2의 값(재생 수)이 더 크면 앞에 오도록 정렬
            }
        });
        
        // 정렬된 장르별로 반복
        for (Entry<String, Integer> entry : genresList) {
            Map<Integer, Integer> temp = new HashMap<>(); // 현재 장르에 속한 곡의 인덱스와 재생 수를 저장할 임시 HashMap
            for (int i = 0; i < genres.length; i++) { 
                if (entry.getKey().equals(genres[i])) { 
                    // 현재 장르(entry.getKey())에 속한 곡인지 확인
                    temp.put(i, plays[i]); // 해당 곡의 인덱스(i)와 재생 수(plays[i])를 저장
                }
            }
            
            // 장르 내 곡들을 재생 수 기준으로 내림차순 정렬
            List<Entry<Integer, Integer>> songsList = new ArrayList<>(temp.entrySet());
            Collections.sort(songsList, new Comparator<Entry<Integer, Integer>>() {
                public int compare(Entry<Integer, Integer> o1, Entry<Integer, Integer> o2) {
                    return o2.getValue().compareTo(o1.getValue()); 
                    // 재생 수 기준 내림차순 정렬
                }
            });
            
            // 상위 두 곡의 인덱스를 answerList에 추가
            for (int j = 0; j < songsList.size() && j < 2; j++) { 
                answerList.add(songsList.get(j).getKey()); 
                // 노래의 인덱스를 추가
            }
        }
        
        // ArrayList를 배열로 변환하여 반환
        answer = new int[answerList.size()];
        for (int i = 0; i < answerList.size(); i++) {
            answer[i] = answerList.get(i);
        }
        
        return answer; // 최종 결과 반환
    }
}

---

Entry란?

• Entry는 Map 인터페이스의 내부 인터페이스로, Map에 저장된 키-값 쌍(key-value pairs)을 나타낸다.

• 예를 들어, HashMap에서 entrySet() 메서드를 호출하면 모든 키-값 쌍이 포함된 Set<Entry<K, V>>를 반환한다.

• Entry<K, V> 객체는 두 가지 주요 메서드를 제공함

  1. getKey(): 현재 Entry 객체의 키를 반환.
  2. getValue(): 현재 Entry 객체의 값을 반환.

Entry의 사용 이유

HashMap의 데이터를 정렬하거나 특정 조건으로 처리할 때, key와 value를 함께 사용해야 하는 경우가 많다. 이때, entrySet()을 통해 모든 키-값 쌍을 쉽게 가져와 정렬이나 필터링을 수행할 수 있다.

Map<String, Integer> map = new HashMap<>();
map.put("Pop", 500);
map.put("Rock", 300);

// entrySet()으로 키-값 쌍을 가져옴
for(Entry<String, Integer> entry : map.entrySet()) {
    System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}
// 출력:
// Key: Pop, Value: 500
// Key: Rock, Value: 300

1) 장르별 재생 횟수를 HashMap에 저장하고 내림차순 정렬

2) 내림차순으로 정렬된 장르별로 고유번호와 재생횟수를 HashMap에 저장

3) HashMap을 내림차순으로 정렬, 재생횟수가 많은 2개으,ㅣ 고유번호를 리스트에 저장

import java.util.*;
import java.util.Map.Entry;
class Solution {
    public int[] solution(String[] genres, int[] plays) {
        int[] answer = {};
        
        ArrayList<Integer> answerList = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        
        for(int i=0;i<genres.length;i++)
        {
            map.put(genres[i], map.getOrDefault(genres[i],0)+plays[i]);
        }
        
        // 장르와 재생 수를 List로 변환
        List<Entry<String, Integer>> genresList = new ArrayList<Entry<String, Integer>>(map.entrySet());
        // 장르별 총 재생 수를 기준으로 내림차순 정렬
        Collections.sort(genresList, new Comparator<Entry<String, Integer>>(){
            public int compare(Entry<String, Integer> o1, Entry<String, Integer> o2)
            {
                return o2.getValue().compareTo(o1.getValue());
            }
        });
        
        // 정렬된 장르별로 반복
        for(Entry<String, Integer> entry : genresList)
        {
            Map<Integer, Integer> temp = new HashMap<>();
            for(int i=0;i<genres.length;i++)
            {
                if(entry.getKey().equals(genres[i]))
                {
                    temp.put(i,plays[i]);
                }
            }
            // 장르 내 곡들을 재생 수 기준으로 내림차순 정렬
            List<Entry<Integer,Integer>> songsList = new ArrayList<Entry<Integer, Integer>>(temp.entrySet());
            Collections.sort(songsList, new Comparator<Entry<Integer, Integer>>(){
                public int compare(Entry<Integer,Integer> o1, Entry<Integer, Integer> o2)
                {
                    return o2.getValue().compareTo(o1.getValue());
                }
            });
            
            // 상위 두 곡의 인덱스를 answerList에 추가
            for(int j=0;j<songsList.size() && j<2; j++)
            {
                answerList.add(songsList.get(j).getKey());
            }
        }
        
        // ArrayList를 배열로 변환하여 반환
        answer = new int[answerList.size()];
        for(int i=0;i<answerList.size();i++)
        {
            answer[i] = answerList.get(i);
        }
        
        return answer;
    }
}

참고 🙇🏻‍♀️

블로그 - https://codinghejow.tistory.com/408

블로그 - https://chaewsscode.tistory.com/183