해시 테이블

처음 설명을 본 본인 표정:

그럴만 했다. 뭔 소린지 1도 모르겠거든...

---

일단 얘는 자료구조다. 이름이 테이블인데 왜 자료구조인지는 주변에 계신 개발자에게 물어보도록. 아무튼 이 테이블은 데이터를 key, value로 짝지어서 저장하는데 이제 중간에 해시 함수가 껴서 인덱싱을 하게 되는 뭐 그런 구조다.

 

예를 들어보자. 스칼렛/바이올렛에도 핸드폰이 있다. 이름하여 스마트로토무. 오도방구 타면서는 조작 못 하고 정차중일때만 조작 가능한데 아무튼... 운전중에 폰 하지 맙시다. 그러면 핸드폰에 전화번호부가 있을 거 아님? 그레이프 아카데미에 처음 전학와서 네모의 연락처를 받았다, 그러면 키는 네모(이름임)이고 값은 네모의 연락처가 된다. 그리고 네모를 해시 함수를 통해 고정된 값으로 만든 다음 인덱스를 만들고, 그 인덱스 위치에 네모의 연락처가 들어갈 양동이를 놓는 것이다. 아니, 진짜로 버킷이라고 함.

 

이 때 키를 고정된 값으로 만드는 무언가가 바로 해시 함수이다. 방법도 여러가지가 있는데 대표적으로는

1. Division Method: 나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나누어 계산한다.( 주소 = 입력값 % 테이블의 크기) 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 알려져 있다.
2. Digit Folding: 각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법이다.
3. Multiplication Method: 숫자로 된 Key값 K와 0과 1사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같은 계산을 해준다. h(k)=(kAmod1) × m
4. Univeral Hashing: 다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법이다.

 

이정도... 키가 한글이면 2번 못하는거 아님?

---

하다보면 해시 충돌이라는 게 난다. 서로 다른 키값을 통과시켰는데!!! 인덱스가 같아여!!! 그니까 양동이 칸 주소가 중복되는 걸 말한다. 이 때 해시 충돌에 대처하는 두 가지 방법이 있는데 하나는 분리 연결법, 하나는 개방 주소법이다.

 

자, 그러니까 내가 위에서 양동이가 들어갈 칸 번호가 겹친다고 했는데 이 때 분리연결법은 양동이가 들어갈 칸을 늘려서 양동이를 여러 개 넣을 수 있게 해 준다. 개방 주소법은 양동이가 들어갈 칸 옆에 있는 빈 칸에 양동이를 넣는다. 그리고 나중에 또 충돌나면 도 빈 칸 찾아서 넣고... 뭐 그런 식.

---

Reference

https://mangkyu.tistory.com/102

[자료구조] 해시테이블(HashTable)이란?