선형 자료구조 - 해시

• key : 고유한 값이며, 해시 함수의 input이 된다. 다양한 길이의 값이 될 수 있다. 이 상태로 최종 저장소에 저장이 되면 다양한 길이 만큼의 저장소를 구성해 두어야 하기 때문에 해시 함수로 값을 바꾸어 저장이 되어야 공간의 효율성을 추구할 수 있다.
• Hash: Hash function의 결과물. bucket에서 value와 매칭되어 저장
• Hash function : key를 Hash로 바꿔주는 역할.
• value : baucket에 최종적으로 저장되는 값으로 키와 매칭되어 저장

1. 해시 함수

해시 테이블의 고유한 인덱스 값을 설정하는 함수

1.1 Division Method

• 나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나우어 계산

h(x) = x mod m

• 테이블의 크기(m)를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다.

  

해쉬 테이블의 크기(m) = 13
x = 25 13 16 5 7

1.2 Multiplication Method

• 입력값을 0과 1 사이의 소수로 대응시킨 다음 해시 테이블의 크기(m)을 곱하여 0 ~ m-1 범위로 팽창시킨다.
• 해쉬 함수의 특성을 결정짓는 상수 A가 필요하다.

h(x) = m(xA mod 1)

• 해쉬 테이블의 크기는 아무거나 상관 없지만, 컴퓨터 환경에 맞게 2의 제곱 수로 하는 것이 자연스럽다.

  

m = 65536
xA = 1,025,390 x 0.6180339887 = 633,725.871673093
주소 = 0.871673093 x 65536 = 57,125

1.3 Digit Folding

• key의 문자열을 아스키 코드로 바꾸고 합한 데이터를 테이블 내의 주소로 사용하는 방법
• 문자열을 key로 사용할 경우 잘 어울린다.

H	e	l	l	o
72   +  101  +	108  +	108  +	111 = 500

1.4 Univeral hasing

• 다수의 해시함수를 만들고, 이 중 하나를 골라 해시값을 만드는 기법

2. 삽입, 탐색, 삭제

• 해시는 고유한 key를 가지고 있으므로 삽입, 탐색, 삭제의 경우 보통 O(1) 시간 복잡도를 갖는다.

3. 해시 충돌

서로 다른 key값에 대해서 같은 값을 출력하는 것. 무한한 값(key)에 대해서 유한한 값(hash)으로 표현하면 서로 다른 두 개 이상의 유한한 값이 동일 출력을 갖게 된다.

3.1 분리 연결법(Separate Chaining)

bucket에 자료구조인 연결리스트를 이용해서 관리하는 것

John과 Sandra가 충돌이 생기지만 연결리스트를 이용해서 관리하고 있다.

• 삽입 : 연결리스트의 Head에 저장할 경우 O(1), Tail에 저장할 경우 O(a)
• 탐색 : Head부터 탐색해서 하므로 O(a)
• 삭제 : 탐색과 유사한 구조 O(a)
• 하나의 해시에 모든 자료가 저장되어 있을 경우(최악의 경우) O(n)

3.2 개방 주소법(Open Addressing)

• 비어 있는 해시 테이블을 찾아서 데이터를 저장하는 기법
• key와 value의 1:1 대응이 유지된다.
• 새로운 저장공간이 불필요하다.
• 데이터가 삭제되면 그 공간은 Dummy space로 활용되기 때문에, Hash Table 재정리가 필요하다

  
  Sandra를 저장하려고 한 해시에 John이 저장되어 있어 그 아래애 저장하여 충돌을 피했다.

3.2.1 선형 탐색(Linear Probing)

현재 버킷의 index로부터 고정폭(ex. +1, +n)씩 이동하며 빈 공간을 탐색

3.2.1 제곱 탐색(Quadratic Probing)

충돌이 생길 때마다 1^2, 2^2, 3^2 씩 칸을 증가시키며 빈 공간을 탐색

3.2.1 이중 해시(Double Hashing)

충돌 시 한번 더 해시를 적용해 새로운 주소를 할당

• 삽입, 삭제, 탐색 모두 O(1)에서 O(n)의 시간 복잡도를 가진다

4. 해시의 사용

• 순서가 없는 데이터를 저장할 경우
• 주소록과 같이 key : value 매칭으로 빠른 탐색이 필요할 경우

출처

• https://itstory.tk/entry/%ED%95%B4%EC%8A%81Hashing-%ED%95%B4%EC%89%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%95%B4%EC%89%AC-%ED%95%A8%EC%88%98
• https://luyin.tistory.com/191
• https://m.blog.naver.com/cestlavie_01/220941175483
• https://mangkyu.tistory.com/102
• https://velog.io/@cyranocoding/Hash-Hashing-Hash-Table%ED%95%B4%EC%8B%9C-%ED%95%B4%EC%8B%B1-%ED%95%B4%EC%8B%9C%ED%85%8C%EC%9D%B4%EB%B8%94-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%9D%98-%EC%9D%B4%ED%95%B4-6ijyonph6o