Data Structures - Hash Table

Hasing ? 

- 임의의 길이의 값을 해시함수를 사용하여 고정된 크기의 값으로 변환하는 작업

 

Hash Table ? 

- 해시 함수를 사용하여 변환 값을 Index 로 삼아 Key, Value를 저장하는 자료구조

- 기본연산으로는 탐색, 삽입, 삭제 등이 존재

 

 

해쉬 테이블과 해시 함수의 역할 개념도

 

- 저장된 데이터를 찾을 때, hash_function을 한번만 수행하면 array내 저장된 Index위치를 찾아낼 수 있어서 탐색이 O(1) 이다.

 

- 순차 검색에 비해 비교도 안될정도로 빠르다.

 

해쉬 함수의 알고리즘

- Division Method (나눗셈 법)

          입력 값을 테이블의 크기로 나누고 그 나머지를 테이블의 인덱스로 이용하는 알고리즘

          // 인덱스 (해시 값) = 입력 값 % 테이블의 크기

 

- Digit Folding (자릿수 접기)

          숫자의 각 자리수를 더해 해시값을 만드는 알고리즘

          // 4924 -> 4 + 9 + 2 + 4 -> 인덱스 (해시 값) : 19

 

 

 

문제점 ?

Hash Collision ?

          다른 Value를 갖고, 같은 Key 를 갖는 데이터가 Insert 될 시 일어나는 것 

          즉, 하나의 Buckets에 너무 많은 데이터가 몰릴때 일어나는 현상 

해시 충돌, 이를 해결하는 체이닝과정

Sandra Dee 와 John Smith 라는 사람은 Key 값이 같다. (Key 를 이용해 hash_function후 나온 인덱스 값이 같다라는 의미인것으로 이해된다.) 두 데이터 모두 152 인덱스를 바라보고 있는데, 이 둘사이에 충돌이 일어났다고 할 수 있다. 충돌 주소의 buckets에 레코드가 추가로 담긴것을 확인할 수 있다. (이는 John Smith  다음 원소에 담겨 있다고 판단된다.) 

만약 bucket에 충분한 공간이 준비가 되어있지 않다면, Overflow가 발생.

 

 

해결방안 ?

1. 체이닝(Chaining)

- buckets 내에 List를 할당하는 것, Buckets에 데이터를 삽입하다가, 해시 충돌이 발생하면 연결리스트로 데이터를 연결하는 방식

 

Q. 이 Chaining 방식에 의문이 든다. 

먼저 들어간 Data 는 Buckets 안에 들어가는지, 아니면 Buckets의 연결리스트 0번째 인덱스에 있는지 의문이 들음

 

먼저 등록된 데이터는 Buckets 에 따로 저장되는가?

 

아니면 먼저 들어오는 것은 0번, 후에는 1번으로 들어오는가?

 

사실 뭐가 들어오던, 문제 해결방법이기 때문에 작성하는 차이는 존재하겠지만, 편한쪽으로 커스텀해서 해쉬테이블을 만들어 쓰면 될 것 같다. 해결방안 개념만 보면 전자의 개념이 더 가깝다고 생각이 든다.

 

 

2. 개방 주소법(Open Addressing)

Chaining의 경우, 단순히 List 연결시켜서 거기에 넣고 하니까 구현은 어렵지 않다고 생각된다. 그러나, 중복될 때마다 별다른 처리를 안하고 List의 Index만 늘려나가기 때문에 기껏 탐색비용을 절감했는데, 해당 리스트를 가져와서 또 리스트 탐색시간으로 O(N) 탐색시간을 소요하고 그러다보면 분명 원하는 바가 아닐 것 인데, 개방주소법은 그것을 해결할 수 있는 방안이라고 한다.

 

해시 충돌이 일어나면 다른 버켓에 데이터를 삽입하는 방식. 그것이 개방 주소법이다.

여러가지 방법이 존재한다.

 

1) 선형 탐색 (Linear Probing) : 해시충돌 시, 다음 버켓 혹은 몇 개를 건너뛰어 데이터를 삽입

2) 제곱 탐색 (Quadratic Probing) : 해시충돌 시, 제곱만큼 건너뛴 버켓에 데이터를 삽입 (1,4,9,16,25,36 ...)

3) 이중 해시 (Double Hasing) : 해시충돌 시, 다른 해시함수를 한 번 더 적용한 결과를 이용

 

추가적으로 동적 해싱이라는 것도 있다고 한다.

 

Rainbow Table ? 

해시 함수를 사용하여 변환 가능한 모든 해시 값을 저장시켜 놓은 표.

보통 해시함수를 이용해 저장된 비밀번호로부터 원래 비밀번호를 추출하는데 사용한다고 함

(비밀번호 바꾸기 이전 비밀번호를 찾는다는 의미인지..)

 

해시 함수를 이용해도 이 표로 사용자의 정보를 얻을 수 있다고 함

단순히 표로 정보를 얻으면 안되기때문에 Salting, Key Stretching 기법을 사용함

 

Salting

          Rainbow Table의 의미를 없애기 위해 고안된 방법, 패스워드에 랜덤한 문자열인 Salt를 추가해서

          해시값을 생성한다. 이렇게 하면 표와 실제 해싱을 통해 얻는 Index값이 다르기 때문에 Value를

          비틀수 있다.

 

Key Stretching 

          짧거나, 예측하기 쉬운 유저 정보를 예측하기 힘들게 만들어주는 기법

          해시함수를 통해 나온 해시값을 여러번 반복해서 돌려 새로운 해시값을 생성

          ( 쉽게 나온거 돌리고 또돌리는 것 )

 

 

시간이나면 해쉬테이블은 원하는 알고리즘을 사용해서 만들어보는것이 좋을듯 하다.

 

 

 

 

 

 

 

 

 

 

참고 : 

preamtree.tistory.com/20

[IT 기술면접 준비자료] 해시(Hash)와 해시충돌(Hash Collision)

baeharam.netlify.app/posts/data%20structure/hash-table

[DS] 해쉬 테이블(Hash Table)이란? - 배하람의 블로그

hombody.tistory.com/267

[자료구조] - 해시 충돌과 해결 방안 / 해시함수