💡 해시 알고리즘(Hash Algorithm) - 데이터를 빠르게 저장하고 검색하기 위한 알고리즘으로 ‘키(key)’를 사용하여 ‘데이터 값(value)’을 조회하는 방법을 의미합니다. 이러한 ‘키-값’을 ‘해시 테이블’이라는 데이터 구조에 저장하여 키에 매핑되는 인덱스 값으로 빠르게 찾을 수 있습니다.
- 키는 해시 함수를 통과하여 해시 값으로 변환되며 이 해시 값은 데이터가 저장되는 배열의 인덱스를 결정합니다.
[ 더 알아보기 ] 💡Java의 Collection Framework에 Map이 그럼 해시 알고리즘으로 구성되어 있는 건가?
- Java Collection Framework의 Map의 경우도 키(key)와 값(value)의 쌍 형태로 저장을 하는 형태입니다. - 키(key)는 해시 함수를 통해 고유한 해시 코드로 변환되고, 이 해시 코드는 데이터가 저장되는 배열의 인덱스를 결정합니다. 따라서, 키를 통해 해당 값을 빠르게 검색할 수 있습니다.
- key, value의 형태의 해시는 해시 함수를 통해서 key의 값은 ‘고유한 해시값’으로 변환이 됩니다. - 이 변환된 해시 값을 기반으로 ‘해시 인덱스’를 결정하여 해시 테이블에는 해시 인덱스와 고유한 해시 값이 저장이 됩니다. - 탐색을 위해서는 key를 호출하면 인덱스를 찾아서 값을 반환해 주기에 빠르게 조회가 가능합니다.
1. 키(Key)
- 문자열 혹은 정수 형태로 구성된 키이며, key-value 형태로 실제 데이터 구조를 가지고 있습니다. 이 중 키는 실제 데이터를 찾기 위해 사용되는 고유 식별자를 의미합니다. - 해당 과정에서는 Key 값은 해시함수(Hash Function)로 전달되어 처리가 됩니다.
2. 해시 함수(Hash Function)
- 전달받은 키(Key) 값을 통해서 해시 함수가 수행이 됩니다. 이 해시 함수 내에서는 키를 ‘고유한 해시값’으로 변환합니다. - 또한 변환된 해시 값은 해시 테이블(Hash Table)의 해시 인덱스(Hash Index)로 저장이 됩니다.
3. 해시 테이블(Hash Table)
- 해시 함수로 전달받은 ‘고유한 해시값’을 기반으로 ‘해시 인덱스(Hash Index)’를 결정하고, 해시 값(Hash Value)은 실제 값이 들어갑니다. - 고유한 해시값을 가지고 있기에 ‘키’를 통해서 빠르게 값을 검색할 수 있습니다.
[ 더 알아보기 ] 💡 Hash Function이 처리된 값을 Hash Table에 저장하는 과정을 보면 저장 순서가 보장되지 않는 거네?
- 해시 알고리즘은 데이터를 빠르게 검색하고 찾기 위한 목적으로 설계된 알고리즘입니다. 이 알고리즘은 키(key)를 해시 함수를 통해 고유한 해시 값으로 변환하는 방식으로 작동합니다. 이 과정에서 키(key)의 원래 순서는 사라지게 됩니다.
- 결과적으로, 해시 알고리즘과 해시 기반의 데이터 구조는 데이터의 빠른 검색과 접근을 우선시하며, 이를 위해 데이터의 입력 순서나 정렬 상태를 보장하지 않습니다. 이러한 특징은 알고리즘의 효율성과 속도를 높이는 데 중요한 역할을 합니다.
2. 해시 함수(Hash Function)
💡 해시 함수(Hash Function)
- 입력된 키 값(Key)을 받아서 해시 함수가 수행이 됩니다. 이 해시 함수 내에서는 키 값을 기반으로 ‘고유한 해시값’으로 변환을 시킵니다.
- 이 변환된 값은 해시 테이블의 해시 인덱스로 저장이 되며, 해시 인덱스는 데이터의 저장 및 검색에 활용이 됩니다. - 고유한 해시값 데이터는 고정된 길이의 동일한 크기의 데이터로 매핑을 수행합니다. 즉, 키(key)는 고유한 값과 동일한 크기를 갖는 해시로 변환됩니다. - 하나의 키가 항상 동일한 해시 값을 생성하도록 설계하게 되어 있어서 데이터 검색 시 원하는 데이터를 빠르게 찾아낼 수 있습니다. - 하지만, 다른 키가 동일한 해시 값을 생성하게 되면 해시 충돌이 발생하게 되며, 이를 처리하기 위한 여러 방법들이 존재합니다.
https://www.geeksforgeeks.org/consistent-hashing/
[ 더 알아보기 ] 💡 해시 키 값이 인덱스와 같이 00, 01로 들어가는 건 예시로 보여주는 거지?
- 맞습니다. 해시 값은 예시로 보여주기 위한 것이며 실제는 '해시 값'이 들어가게 됩니다.
3. 해시 테이블(Hash Table)
💡 해시 테이블(Hash Table)
- '키(key)'와 '값(value)'을 매핑하는 데이터 구조를 가집니다. 이 구조에서 해시 함수를 사용하여 키를 ‘고유한 해시 값’으로 변환되고 이 해시 값은 배열의 ‘인덱스’로 사용됩니다. 따라서 키를 통해 값을 빠르게 검색할 수 있습니다.
- 하지만 서로 다른 키가 동일한 해시 값을 가질 경우, 즉 해시 충돌이 발생할 경우, 체이닝과 같은 방법을 사용하여 충돌을 해결할 수 있습니다.
요소
설명
키(Keys)
해시테이블에서 각 값에 대한 고유 식별자로 사용되는 요소. 키는 해시 함수를 통해 고유한 해시 값으로 변환되며, 이 해시 값은 데이터가 저장되는 배열의 인덱스를 결정합니다.
인덱스(Index)
해시 값에 따라 결정되는 데이터의 위치. 데이터를 빠르게 찾기 위한 참조 포인트입니다.
버킷(Buckets)
해시 테이블에서 해시 값이 동일한 항목들을 저장하는 공간. 버킷은 하나 이상의 키-값 쌍을 저장할 수 있으며, 버킷 안의 키-값 쌍들은 일반적으로 연결 리스트로 관리됩니다.
4. 해시 충돌(Hash Collision)
💡 해시 충돌(Hash Collision)
- 서로 다른 키가 동일한 해시 값을 가질 때 발생하는 현상입니다. 이는 해시 함수의 특성상 피할 수 없는 문제로 이를 해결하기 위한 다양한 기법들이 존재합니다.
💡 해시 충돌(Hash Collision) 예시
- key = 10, key = 15인 값이 두 개가 존재한다고 가정할 때, 이를 해시 함수(Hash Function)를 통해서 수행을 하면 ‘해시 값’으로 변환이 됩니다. - 이 변환된 해시 값은 해시 테이블(Hash Table) 내의 해시 인덱스(Hash Index)로 저장이 되는 시점에 ‘동일한 해시 값’을 가지는 문제가 발생합니다.
Map<String, Integer> hashMap = new HashMap<>();
// 1. [추가] 키(key) - 값(value) 추가 : HashMap 내에 값을 추가합니다.
hashMap.put("test1", 1);
hashMap.put("test2", 2);
hashMap.put("test3", null);
// 2. [조회] 키(value) 값을 기반으로 값 조회 : HashMap 내에 값을 조회합니다.
int value1 = hashMap.get("test1");
int value2 = hashMap.get("test2");
int value3 = hashMap.get("test3");
System.out.println("test1 : " + value1 + " test2 : " + value2 + " test3 : " + value3);
// 3. [조회] 전체 해시맵의 요소 개수 조회
System.out.println("size :: " + hashMap.size());
// 4. [조회] 키(value) - 값(value) 조회 : HashMap 내에 키와 값을 조회합니다.
for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {
System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}
// 5. [조회] 전체 해시맵 중 Key 조회 : HashMap 내에 동일한 키 값이 있는지 조회합니다.
if (hashMap.containsKey("test1")) {
System.out.println("test1 exists.");
}
// 6. [조회] 전체 해시맵 중 value 조회 : HashMap 내에 동일한 값이 있는지 조회합니다
if (hashMap.containsValue(100)) {
System.out.println("Value 100 exists.");
}
// 7. [수정] 키(key) - 값(value) 변경 : HashMap 내에 키를 기반으로 값을 변경합니다.
hashMap.put("test1", 100);
hashMap.put("test2", 101);
hashMap.put("test3", 102);
System.out.println("test1 : " + hashMap.get("test1") + " test2 : " + hashMap.get("test2") + " test3 : " + hashMap.get("test3"));
// 8. [삭제] 키(key) 값을 기반으로 요소 삭제 : HashMap 내의 요소를 삭제합니다
hashMap.remove("test1");
hashMap.remove("test2");
hashMap.remove("test3");
System.out.println("test1 : " + hashMap.get("test1") + " test2 : " + hashMap.get("test2") + " test3 : " + hashMap.get("test3"));
// 9. [삭제] 해시맵의 모든 요소를 삭제합니다.
hashMap.clear();
System.out.println("test1 : " + hashMap.get("test1") + " test2 : " + hashMap.get("test2") + " test3 : " + hashMap.get("test3"));
2. HashTable
💡 HashTable
- Map 인터페이스를 구현한 클래스 중 하나로 ‘구현체’를 의미합니다. HashMap과 마찬가지로 Hashing 기법을 사용하여 Key와 value를 저장합니다.
- HashMap과 다르기게 스레드에 안전(thread-safe)한 동기화된 메서드를 제공합니다. 이는 멀티 스레드 환경에서 여러 스레드가 동시에 HashTable을 수정하지 못하도록 합니다. 따라서 HashTable은 동시성 문제에 대해 더 안전하게 사용할 수 있습니다. - 또 다른 차이점은 HashTable이 null key 또는 null value를 허용하지 않는다는 점입니다. 이는 HashMap이 null key와 null value를 모두 허용하는 것과 대조적입니다.
💡 Hashtable 주요 메서드
메서드
리턴 값
설명
put(K key, V value)
V
키와 값을 맵에 추가
get(Object key)
V
주어진 키에 해당하는 값을 반환
size()
int
맵의 요소 개수를 반환
keys()
Enumeration<K>
맵에 있는 모든 키를 Enumeration 형태로 반환
containsKey(Object key)
boolean
주어진 키가 맵에 있는지 확인
containsValue(Object value)
boolean
주어진 값이 맵에 있는지 확인
remove(Object key)
V
주어진 키에 해당하는 키-값 쌍을 삭제
clear()
없음
맵에서 모든 키-값 쌍을 삭제
💡 Hashtable 활용 예시
Hashtable<String, Integer> hashtable = new Hashtable<>();
// 1. [추가] 키(key) - 값(value) 추가 : Hashtable 내에 값을 추가합니다.
hashtable.put("test1", 1);
hashtable.put("test2", 2);
hashtable.put("test3", 3);
hashtable.put("test4", null); // ** 오류 발생 : Key에 NULL을 허용하지 않음
hashtable.put(null, 4); // ** 오류 발생 : Value에 NULL을 허용하지 않음
// 2. [조회] 키(value) 값을 기반으로 값 조회 : Hashtable 내에 값을 조회합니다.
int value1 = hashtable.get("test1");
int value2 = hashtable.get("test2");
int value3 = hashtable.get("test3");
System.out.println("test1 : " + value1 + " test2 : " + value2 + " test3 : " + value3);
// 3. [조회] 전체 테이블의 요소 개수 조회
System.out.println("size :: " + hashtable.size());
// 4. [조회] 키에 대해 Enumeration을 얻음 : Hashtable 내에 키를 조회합니다.
Enumeration<String> keys = hashtable.keys();
while (keys.hasMoreElements()) {
String key = keys.nextElement();
System.out.println("Key: " + key + ", Value: " + hashtable.get(key));
}
// 5. [조회] 전체 테이블 중 Key 조회 : Hashtable 내에 동일한 키 값이 있는지 조회합니다.
if (hashtable.containsKey("test1")) {
System.out.println("test1 exists.");
}
// 6. [조회] 전체 테이블 중 value 조회 : Hashtable 내에 동일한 값이 있는지 조회합니다.
if (hashtable.containsValue(100)) {
System.out.println("Value 100 exists.");
}
// 7. [수정] 키(key) - 값(value) 변경 : Hashtable 내에 키를 기반으로 값을 변경합니다.
hashtable.put("test1", 100);
hashtable.put("test2", 101);
hashtable.put("test3", 102);
System.out.println("test1 : " + hashtable.get("test1") + " test2 : " + hashtable.get("test2") + " test3 : " + hashtable.get("test3"));
// 8. [삭제] 키(key) 값을 기반으로 요소 삭제 : Hashtable 내의 요소를 삭제합니다.
hashtable.remove("test1");
hashtable.remove("test2");
hashtable.remove("test3");
System.out.println("test1 : " + hashtable.get("test1") + " test2 : " + hashtable.get("test2") + " test3 : " + hashtable.get("test3"));
// 9. [삭제] 테이블의 모든 요소를 삭제합니다.
hashtable.clear();
System.out.println("test1 : " + hashtable.get("test1") + " test2 : " + hashtable.get("test2") + " test3 : " + hashtable.get("test3"));
💡 [참고] HashMap과 HashTable의 차이는 뭘까? 1. 동기화
- Hashtable은 동기화되어 Thread-safe 합니다. 즉, 멀티스레드 환경에서 한 번에 하나의 스레드만 Hashtable에 변경을 가할 수 있습니다. - 반면에, HashMap은 비동기화되어 있어 Thread-safe 하지 않습니다. 이로 인해 HashMap이 Hashtable보다 빠르며, 동시성을 요구하지 않는 경우에는 HashMap이 더 적합합니다.
2. NULL 허용 여부
- Null Key 및 Null Value: HashMap은 하나의 Null Key와 여러 개의 Null Value를 허용합니다. 반면에 Hashtable은 Null Key 또는 Null Value를 허용하지 않습니다.
import java.util.*;
public class Main {
public static void main(String[] args) {
// HashMap 예제
HashMap<Integer, String> hmap = new HashMap<Integer, String>();
hmap.put(1, "Apple");
hmap.put(null, "Orange"); // Null key를 허용
hmap.put(2, null); // Null value를 허용
System.out.println("HashMap: " + hmap);
// Hashtable 예제
Hashtable<Integer, String> htab = new Hashtable<Integer, String>();
htab.put(1, "Apple");
// htab.put(null, "Orange"); // Null key를 허용하지 않아, 이 코드는 에러를 발생시킴
// htab.put(2, null); // Null value를 허용하지 않아, 이 코드는 에러를 발생시킴
System.out.println("Hashtable: " + htab);
}
}
3. LinkedHashMap
💡 LinkedHashMap
- Map 인터페이스의 하나인 HashMap의 하위 클래스로, '키(key)'-'값(value)' 쌍을 해시맵에 저장하는 동시에 더블 링크드 리스트에도 입력 순서에 따라 저장합니다. 이로 인해 원소들의 삽입 순서를 기억하는 특징이 있습니다.
- 키와 값에 NULL을 허용하며 키는 중복되지 않습니다. 만약 동일한 키로 데이터를 저장하면, 기존 데이터를 덮어쓰게 됩니다. - LinkedHashMap은 해시맵의 빠른 접근성을 유지하면서도 더블 링크드 리스트로 인해 입력 순서대로 데이터를 반복할 수 있는 기능을 제공합니다.
// LinkedHashMap 생성
LinkedHashMap<String, Integer> scores = new LinkedHashMap<String, Integer>();
// 값 추가
scores.put("David", 85);
scores.put("Jane", 95);
scores.put("Susan", 84);
scores.put("Brenda", 92);
// 값 출력 (삽입 순서대로 출력됨)
for(Map.Entry<String, Integer> entry : scores.entrySet()) {
String key = entry.getKey();
Integer value = entry.getValue();
System.out.println(key + " : " + value);
}
💡 프로그래머스 : 폰켓몬 💡 문제 설명 - 당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다.
홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.
1. 첫 번째(3번), 두 번째(1번) 폰켓몬을 선택 2. 첫 번째(3번), 세 번째(2번) 폰켓몬을 선택 3. 첫 번째(3번), 네 번째(3번) 폰켓몬을 선택 4. 두 번째(1번), 세 번째(2번) 폰켓몬을 선택 5. 두 번째(1번), 네 번째(3번) 폰켓몬을 선택 6. 세 번째(2번), 네 번째(3번) 폰켓몬을 선택
이때, 첫 번째(3번) 폰켓몬과 네 번째(3번) 폰켓몬을 선택하는 방법은 한 종류(3번 폰켓몬 두 마리)의 폰켓몬만 가질 수 있지만, 다른 방법들은 모두 두 종류의 폰켓몬을 가질 수 있습니다. 따라서 위 예시에서 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 됩니다.
당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.
💡 제한사항
- nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다. - nums의 길이(N)는 1 이상 10,000 이하의 자연수이며, 항상 짝수로 주어집니다. - 폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타냅니다. - 가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 return 하면 됩니다.
- 최대 가질 수 있는 폰켓몬의 종류를 구하기 위해서 hashMap의 put()를 이용하여 고유한 폰켓몬의 종류(key)와 폰켓몬의 개수(value)를 hashmap에 저장할 수 있습니다.
import java.util.*;
class Solution {
public int solution(int[] nums) {
int answer = 0;
// key(폰켓몬 번호), value(폰켓몬 번호 별 개수)
Map<Integer, Integer> resultMap = new HashMap<>();
// 폰켓몬 번호 별 개수를 Map 요소 값에 추가합니다.
for (int num : nums) {
resultMap.put(num, resultMap.containsKey(num) ? resultMap.get(num) + 1 : 1);
}
// 폰켓몬의 종류 별 개수
answer = resultMap.size();
// 최대로 얻을수 있는 폰켓몬 개수
int obtainCnt = Math.abs(nums.length / 2);
// 폰켓몬의 종류 보다 얻을 수 있는 개수가 많은 경우 폰켓몬 종류 반환
// 폰켓몬의 종류 보다 얻을 수 있는 개수가 적은 경우 얻을 수 있는 개수 반환
return answer < obtainCnt ? answer : obtainCnt;
}
}
2. 프로그래머스 : 완주하지 못한 선수
💡 프로그래머스 : 완주하지 못한 선수 💡 문제 설명
- 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 💡 제한사항
- 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. - completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. - 참가자 중에는 동명이인이 있을 수 있습니다.
1. Map 내에 참가자 목록(participant)을 추가합니다. 참가자 이름(key), 참가여부 체크(value) - 0: 참가, 1: 미 참가 2. 완주 한 인원을 체크 Key 값에 따라 업데이트 수행, 참가여부에 따라 참가여부 체크(value)를 -1로 참가 체크를 수행합니다. 3. Map을 순회하면서 0이 아닌 값을 찾아서 결과로 반환합니다. 값이 0이 아니면 미 참가로 간주하고 key 값을 반환합니다.
import java.util.*;
class Solution {
public String solution(String[] participant, String[] completion) {
String answer = "";
Map<String, Integer> pHashMap = new HashMap<>();
// Map 내에 참가자 목록(participant)을 추가합니다. 참가자 이름(key), 참가여부 체크(value) - 0: 참가, 1: 미 참가
for (String participantItem : participant) {
pHashMap.put(participantItem, pHashMap.getOrDefault(participantItem, 0) + 1);
}
// 완주 한 인원을 체크 Key 값에 따라 업데이트 수행, 참가여부에 따라 참가여부 체크(value)를 -1로 참가 체크를 수행합니다.
for (String completionItem : completion) {
pHashMap.put(completionItem, pHashMap.get(completionItem) - 1);
}
// Map을 순회하면서 0이 아닌 값을 찾아서 결과로 반환합니다.
for (Map.Entry<String, Integer> entry : pHashMap.entrySet()) {
if (entry.getValue() != 0) {
answer = entry.getKey();
}
}
return answer;
}
}
[ 더 알아보기 ] 💡getOrDefault(Object key, V defaultValue)
- Map 내에 key 값이 존재하는지 여부를 체크하여, 존재하지 않는 경우 defaultValue 값을 반환합니다. 존재하는 경우 본래의 value 값을 반환합니다.
Map<String, Integer> fruitMap = new HashMap<>();
fruitMap.put("바나나", 10);
// "사과"라는 키가 없으므로, 기본값인 0을 반환
int appleCount = fruitMap.getOrDefault("사과", 0);
System.out.println(appleCount); // 출력: 0
