[ 자료구조 ] Hash

해시(hash)

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

• 보통은 인덱스를 활용하지만 해시는 key를 활용해 데이터 탐색을 빠르게 함
• 키와 값를 일대일 대응해 저장함

 

해시의 특징

1️⃣ 단방향

키를 통해 값을 찾을 수 있지만 값을 통해 키를 찾을 수는 없음

 

2️⃣ 찾고자 하는 값을 $O(1)$에서 바로 찾을 수 있음

키 자체가 해시 함수에 의해 값이 있는 인덱스가 되므로 값을 찾기 위한 탐색 과정이 필요 없음

 

3️⃣ 값을 인덱스로 활용하려면 적절한 변환 과정이 필요

 

❓ 해시를 사용하지 않으면…

 

1. 전체 데이터를 확인해야하므로 위에서부터 순차적으로 이름을 확인하고
2. 이름4 가 있는 위치 3을 반환
3. 해당 위치의 전화번호를 읽음

 

❗ 해시를 사용한다면…

 

• 순차 탐색할 필요 없이 해시 함수를 활용해 특정 값이 있는 위치를 바로 찾을 수 있음
• 해시 테이블(hash table) : 키와 대응한 값이 저장되어 있는 공간
• 버킷(bucket) : 해시 테이블의 각 데이터

 

해시의 활용

단방향으로만 검색할 수 있는 대신 빠르게 원하는 값을 검색 가능, 데이터를 저장하거나 보안이 필요할 때 활용됨, 코딩 테스트에서는 데이터를 탐색하는 횟수가 많을 경우 해시를 고려하면 좋음

• 비밀번호 관리
• 데이터베이스 인덱싱
• 블록체인

 

---

 

해시 함수

 

해시 함수를 구현할 때 고려할 내용

1️⃣ 해시 함수가 변환한 값은 해시 테이블 크기를 넘으면 ❌

• 해시 함수가 변환한 값은 인덱스로 활용되기 때문에 해시 테이블의 크기를 넘으면 안됨
• 해시 테이블 크기가 $N$이라면 인덱스는 $0$ ~ $N-1$ 사이의 값을 내야 함

 

2️⃣ 해시 함수가 변환한 값의 충돌은 최대한 적게

• 충돌 : 서로 다른 두 키에 대해 해싱 함수를 적용한 결과가 동일한 것
• 해시 함수가 계속해서 같은 위치에 데이터를 저장하면 문제가 발생하므로 이에 따른 다양한 전략이 있음

 

---

 

자주 사용하는 해시 함수

 

1️⃣ 나눗셈법(division method)

$$h(x)=x\text{ mod } k \\x : \text{키, } k\text{ : 소수 }$$

 

 

• $k$ 가 소수인 이유 : 소수가 아니면 약수에 의해 계속해서 충돌이 발생하기 때문
• 테이블 크기 : $k$ ( $0$ ~ $(k-1)$ )
• 단점 : 크기가 $k$ 이므로 상황에 따라 많은 데이터를 저장해야 한다면 큰 소수 필요할 수 있음

 

 

2️⃣ 곱셈법(multiplication method)

$$h(x)=(((x*A)\text{ mod }1)*m)\\x \text{ : 키}\\ A \text{ : 황금비(약 1.618033)}\\m\text{ : 최대 버킷의 개수 }$$

 

 

1. 키에 황금비를 곱함
2. 구한 값에서 모듈러 1을 해서 정수부분을 버리고 소수부분만 가지고 감
3. 2번 값에 $m$ 을 곱하면 테이블의 인덱스 ( $0$ ~ $(m-1)$ ) 에 매치할 수 있음

※ 황금비를 사용하므로 나눗셈법 처럼 소수가 필요없음, 즉 테이블 크기가 커져도 추가작업 필요 없음

 

 

3️⃣문자열 해싱1

$$hash(s)=(s[0]+s[1]*p+s[2]*p^2 + ... +s[n-1]*p^{n-1} )\text{ mod } m \\ s\text{ : 문자열}\\m\text{ : 해시 테이블 최대 크기 }\\ p\text{ : 31(메르센 소수)}$$

※ 메르센 소수 : 일반적으로 $2^{N-1}$ 으로 표시할 수 있는 숫자 중 소수인 수, 해시에서 충돌을 줄이는데 효과적

 

 

• 나눗셈, 곱셈법은 키의 자료형이 숫자인 것에 반해 키의 자료형이 문자열일떄도 사용 가능한 문자열 해싱
• 문자열의 문자를 숫자로 변환하고 이 수들을 다항식의 값으로 변환해서 해싱함
• polynomial rolling method 사용
• 단점 : “apple” 이라는 간단한 문자열을 해싱했는데도 결과값은 4,990,970 으로 굉장히 크므로 오버플로우가 발생할 여지가 있음

 

 

4️⃣ 문자열 해싱2

$$(a+b)\%c=(a\%c+b\%c)\%c$$

• 좌변 처럼 덧셈을 전부한 다음 모듈러 연산을 하는 대신 우변처럼 중간 중간 모듈러 연산하면 오버플로우 최대한 방지 가능
• 이를 활용한 문자열 해싱 공식은 아래와 같음

$$hash(s)=(s[0]\%m+s[1]*p\%m+s[2]*p^2\%m + ...  +s[n-1]*p^{n-1}\%m )\%m$$

 

⚠️ 모듈러 연산이 있는 문제 중 큰 수를 다르는 문제는 오버플로우 함정이 있는 경우가 있음, 난이도가 높은 문제는 대부분 이러한 함정을 포함하고 있으므로 주의

 

---

 

충돌 처리

 

체이닝으로 처리

충돌이 발생하면 해당 버킷에 링크드리스트로 같은 해시값을 가지는 데이터를 연결함

※ LinkedList : 데이터 요소들을 연결하여 구성한 선형 데이터 구조

 

 

• 장점 : 간단함
• 단점① : 해시 테이블 공간 활용성 떨어짐
  • 충돌이 많아지면 Linked List 길이가 길어지고 다른 해시 테이블의 공간은 덜 사용하게 됨
• 단점② : 검색 성능이 떨어짐
  • Linked List 로 연결한 값을 찾으려면 Linked List의 맨 앞 데이터부터 검색해야함
  • $N$ 개의 키가 있고 모든 키가 충돌해 체이닝 되었다면 검색 시간 복잡도는 $O(N)$

Java의 HashMap클래스는 체이닝을 사용하여 해시 충돌을 처리하지만
• 충돌 발생 시 데이터 접근 시간 복잡도가 $O(N)$ 이므로 일정 개수가 넘어가면
• 자동으로 해당 LinkedList를 이진탐색트리(binary search tree)로 변환하여 데이터 접근에 $O(\log N)$ 의 성능이 나오도록 함 

 

개방 주소법으로 처리

개방주소법(open addressing)은 빈 버킷을 찾아 충돌 값을 삽입함

• 장점 : 해시 테이블을 최대한 활용하므로 체이닝보다 메모리를 더 효율적으로 사용함

 

1️⃣ 선형 탐사 방식(Linear Probing)

충돌이 발생하면 다른 빈 버킷을 찾을 때 까지 일정한 간격으로 이동함(보통 간격은 1)

• 테이블의 범위를 넘지 않기 위해 모듈러 연산을 적용

$$h(k,i)=(h(k)+i)\text{ mod }m\\m\text{ : 수용할 수 있는 최대 버킷 }$$

 

 

• 단점 : 충돌 발생 시 1 칸씩 이동하며 해시 테이블 빈 곳에 값을 넣으면 해시 충돌이 발생한 값끼리 모이는 영역이 발행 → 클러스터 형성 ⇒ 군집이 생성되면 해시값이 겹칠 학률이 더 올라감

※ 이를 해결하기 위해 제곱수만큼 이동하며 탐사하는 방법도 있음

 

 

2️⃣ 이중 해싱 방식

해시 함수를 2개 사용하거나 때로는 $N$개로 늘려서 하는 방법

• 두 번째 해시함수($h_2$) : 첫 번째 해시 함수($h_1$)로 충돌이 발생하면 해당 위치를 기준으로 어떻게 위치를 정할 지 결정
• 클러스터를 줄이기 위해 $m$ 을 제곱수로 하거나 소수로 함

$$h(k,i)=(h_1(k)+i*h_2(k))\text{ mod }m\\m\text{ : 수용할 수 있는 최대 버킷 }$$

 

---

 

해시맵

 

Java에는 HashTable 클래스와 HashMap 클래스가 있지만 HashTable은 자바의 초기버전과 호환성을 위해 남겨두었을 뿐 최근에는 잘 사용되지 않음

해시맵의 ADT

 

구분	정의	설명
연산	ValueType put(KeyType key, ValueType value)	key: value로 데이터 저장/동일한 key가 이미 있었다면 그 key의 value값을 반환
	ValueType get(KeyType key)	key에 대한 value값을 반환
	ValueType getOrDefault(KeyType key, ValueType defaultValue)	key에 해당하는 value가 없으면 defaultValue 값으로 저장
	ValueType remove(KeyType key)	key에 해당하는 데이터 삭제
	ValueType containsKey(KeyType key)	해당 key가 있다면 true, 없다면 false 반환
	void clear()	해시맵 안의 모든 데이터 삭제
상태	int isEmpty()	해시맵 안에 데이터가 없다면 true, 있다면 false 반환
	int size()	데이터 개수 반환

import java.util.*;
public class hashMap {
    public static void main(String[] args) {
        // HashMap<KeyType, ValueType>
        HashMap<String,Integer> map=new HashMap<>();

        // 해시맵에 데이터 추가
        map.put("ABC",10);
        map.put("BBB",20);
        map.put("AAA",30);
        map.put("ABC",15);

        System.out.println(map.isEmpty()); // false
        System.out.println(map.getOrDefault("ABC",40)); // 15
        System.out.println(map.containsKey("ABC")); // true

        map.remove("ABC"); // 해시맵에서 키가 "ABC"인 데이터 제거
        System.out.println(map.size()); // 2

        map.clear(); // 해시맵의 모든 데이터 삭제
        System.out.println(map.isEmpty()); //true
    }
}