스터디 - 해시

해시함수

임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수

해시함수는 결정론적으로 작동해야한다.

f(x)=a, f(y)=b, a != b 이면 x != y 이어야 한다.

---

해시테이블

해시함수는 해시테이블 자료구조에서 데이터를 빠르게 찾아내는 데 사용된다.

예

학생 이름만으로 성적을 알고 싶다. 학생리스트를 처음부터 훑어보면
최대 학생수 N명만큼의 시간이 소요된다.

학생	성적
Kim	3.2
Park	2.9
Lee	3.4
Chung	3.9
Yoon	4.4

특정 학생의 성적 찾기

인간이면 문자를 보고 단번에 누가 성적이 몇인지 알겠지만 컴퓨터면 위에서부터 이름을 스캔할 것이다.

---

학생이름을 해싱

일반적으로 여러 데이터를 저장할 때 배열을 이용한다.
그리고 배열의 값을 알려면 배열의 인덱스를 이용한다.

배열의 인덱스는 메모리의 위치를 가리키고 있기 때문에 컴퓨터가 O(1)에 데이터를 조회할 수있다.

그렇다면 학생의 이름을 배열의 인덱스로 바꾸면 컴퓨터도 단번에 학생의 성적을 알 수 있지 않을까

---

해시함수 설정

학생이름의 각 알파벳순번을 제곱하여 더한 값을 반환하는 해시함수를 이용해보자.
아래는 해시함수의 스도코드이다.

function hash(String username){
	return username
    	.reduce(0,(hashValue, alphabet) => hashValue += alphabet.order()^2);
}

---

Kim을 해싱해보자.

• k는 알파벳의 10번째 숫자이다.
• i는 알파벳의 8번째 숫자이다.
• m은 알파벳의 12번째 숫자이다.

hash(kim)의 값은 10^2 + 8^2 + 12^2 = 308 이다.

다른 이름들도 해싱하면

hash(name)	학생	성적
308	Kim	3.2
614	Park	2.9
153	Lee	3.4
658	Chung	3.9
1137	Yoon	4.4

위와 같다.

---

배열에 맵핑

index	value
...	..
308	3.2
..	..
614	2.9
..	..
153	3.4
154	null
..	..

Lee의 성적을 알고 싶으면 해시값hash(lee)=153을 배열의 인덱스로 조회하면 된다.
array[153]은 3.4이므로 성적은 3.4점이다.

---

실제론 더 복잡함

앞의 예시는 정말 간단한 예로 해시에대한 개념을 위한 예시이다.

실제론 해시함수의 결과 같게 나올 수도(해시충돌) 있어서 이중해시를 하기도 한다.

문자열 해시의 전략도 정말 다양하다

---

Java의 유용한 해시 자료구조

자바에서 기본적으로 제공하는 java.util 라이브러리는 여러가지 해시 자료구조를 제공한다.

• HashSet<T> : Set의 구현체, 중복허용X, 순서보장X, 읽기/쓰기 O(1)
• HashMap<T,U> : Map<T,U>의 구현체, 키는 중복X, 순서보장X, 읽기/쓰기 O(1)
• LinkedHash.. : 순서가 보장되는 해시자료구조
• Concurrent.. : 멀티스레드에서 안전한 해시자료구조

HashSet<T>과 HashMap<T,U>은 모르면 알고리즘 문제를 못푸니 꼭 알아야한다.