[JAVA 스터디] 250120 hash 함수

- 오늘의 학습 키워드

• 해시 함수 

 

 

해시는 저장 또는 검색 등에서 자주 활용되는 자료구조입니다. 정확하게는 특정한 함수(알고리즘)를 통해서 값을 추출하고 활용하는 것인데요. 함수(알고리즘)를 어떻게 구현하는지에 따라 사용 용도와 성능이 달라집니다.

이러한 해시는 더 나아가서 암호, 블록체인, 메시지 인증 코드 등에서도 활용됩니다.

---

해시(Hash)

---

해시(Hash)는 입력 데이터를 고정된 길이의 데이터로 변환된 값을 말합니다. 다른 말로는 '해시 값(Hash value), 해시 코드, 체크섬' 이라고도 합니다. 이러한 해시는 뒤에서 알아볼 '해시 함수'에 의해서 얻게 됩니다. 간단하게 말하자면, 데이터의 KEY 값이 해시 함수를 통해서 변환된 간단한 정수입니다. 이렇게 정수로 변환된 해시는 배열의 인덱스, 위치, 데이터 값을 저장하거나 검색할 때 활용됩니다.

 

 

 

01. 자료구조의 특징

• 키(KEY)에 데이터(Value)를 매핑할 수 있는 데이터 구조
• 해시 함수를 통해 키의 데이터를 배열에 저장할 수 있는 주소(인덱스 번호)를 계산
• 키를 통해서 저장된 데이터를 빠르게 찾고, 저장 및 탐색 속도가 획기적으로 빨라짐

 

02. 알아둘 용어

1) 해시 함수(Hash Function)

임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수

해시 함수(Hash function)는 입력받은 데이터를 해시 값으로 출력시키는 알고리즘을 말합니다. 이렇게 출력된 해시 값은 알고리즘에 따라 다양한 결과를 보입니다. 그렇기 때문에 함수는 목적에 맞게 다양하게 설계되고 자료구조, 캐시, 검색, 에러 검출, 암호 등으로 유용하게 사용됩니다.

// 해시 함수 예시
Integer hashFunction(String key) {
	
    return (int)(key.charAt(0)) % 100;
}

위 코드는 입력받은 키에서 문자의 0번에 해당하는 부분을 정수화하여 100으로 나눈 뒤, 나오는 나머지를 반환하는 함수(메서드)입니다. 이렇게 반환된 값은 배열의 인덱스가 되고, 해당 인덱스에 맞게 저장을 할 수 있게 되는 것입니다.
이처럼 함수의 로직은 단순할 수도 있고, 복잡할 수도 있습니다.

 

2) 해시 테이블(Hash Table)

키 값의 연산에 의해 직접 접근이 가능한 데이터 구조

해시 테이블(Hash table)은 키와 값을 함께 저장해 둔 데이터 구조입니다. 이는 데이터가 행과 열로 구성된 표에 저장되는 것과 유사합니다. 테이블에 데이터를 저장할 때 위치는 무작위로 지정되어 작성됩니다. 따라서 중간에 여유 공간이 발생할 수 있습니다.

 

표와 유사한 해시 테이블

 

추가 용어
- 버킷(bucket) : 하나의 주소를 갖는 파일의 한 구역, 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수
- 슬롯(slot) : 한 개의 레코드를 저장할 수 있는 공간, 한 버킷 안에 여러 개의 슬롯이 있음

 

03. 해싱(Hashing)

해싱은 해시 함수에서 해시를 출력하고, 해시 테이블에 저장하는 과정까지의 행위를 말합니다. 이 과정을 그림을 나타내면 아래와 같습니다.

 

해싱(Hashing)

 

 

04. 해시 자료구조의 장, 단점과 용도

1) 장점

• 데이터 저장 / 일기 속도가 빠름 ( 검색 속도가 빠름)
• 해시는 키에 대한 데이터가 있는지 확인이 쉬움

2) 단점

• 일반적으로 저장공간이 많이 필요
• 여러 키에 해당하는 주소(인덱스)가 동일한 경우 충돌을 해결하기 위한 별도 자료구조 필요

3) 주요 용도

• 검색이 많이 필요한 경우
• 저장, 삭제, 읽기가 빈번한 경우
• 캐쉬 구현

참고 : JAVA 에서는 주로 HashMap 클래스를 사용합니다.
→ 해시 테이블 구조를 활용하여 구현된 JAVA Collection Framework에 속한 클래스

 

 

 - 어떤 문제가 있었고, 나는 어떤 시도를 했는지

27160번  백준 

 

문제 링크 : https://www.acmicpc.net/problem/27160

할리갈리

 

import java.util.HashMap;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String a = kb.next();
            int b = kb.nextInt();
            map.put(a, map.getOrDefault(a,0)+b);
        }
        String answer = "NO";
        for (String key : map.keySet()) {
            if(map.get(key)==5) answer ="YES";
        }
        System.out.println(answer);
    }
}