해시, 해시함수, 해시테이블 (Hash, Hash Table)

Goal 

 - 해시, 해시함수, 해시테이블의 개념을 이해한다.

 - 해시방식에서 일어나는 충돌개념을 이해한다.

 - 충돌 해결방식인 Chaining, Linear Probing 방식을 이해한다.

 - 테이블 리사이징을 이해한다.

1. 해시

 - 데이터를 관리하고 유지하는 자료구조

 - 리소스보다 속도를 우선시한다.

 

2. 해시의 데이터 저장 구조 

 - 똑같은 데이터가 올 때마다 똑같이 분류되는 규칙을 '해시함수'에 정의하여 데이터를 해시테이블에 저장함.

 

 

 

3. 해시함수

 - 데이터를 규칙에 맞추어 해시테이블로 뿌려줌

 - 사칙연산, 비트연산 또는 다양한 연산의 조합으로 이루어진 함수

 - 데이터를 해시함수로 처리하여 해쉬코드를 뽑고, 해시코드에서 다시 인덱스를 뽑은 후 해시테이블에 인덱스와 값을 저장함.

 

4. 해시테이블

 - 해시함수를 통해 분류된 데이터가 저장되는 테이블 

 - 버켓 : 인덱싱등 칸을 나누는 기준이자, 칸 자체를 의미함

 - 엔트리 : 버켓에 들어있는 자료

 - 인덱스가 주어지기 때문에 자료 검색에 용이하지만 리소스를 많이 이용한다.

 

 

5. 충돌

 - 해시방식을 사용하면, 같은 인덱스를 같는 다른 값이 존재할 경우 자료를 저장할 때, 같은 버켓에 동일한 형식의 자료가 들어가는 충돌이 발생할 수 있다.

 

6. 충돌대처

 

6-1 Chaining 구조

 - 해시함수를 통해 처리된 데이터와 중복된 인덱스를 갖는 값이 이미 해시테이블에 저장되어 있으면, Linked List등과 같은 자료 구조를 이용하여 값을 체인처럼 이어준다.

 

 - 이미 만들어 놓은 테이블의 버켓 공간을 소모하지 않고 계속 자료를 이을 가능성이 있기 때문에, 리소스를 많이 사용한다.

 - 삭제시에는 Linked List를 통해 연결된 노드를 찾아서 삭제하면 된다.

 

6-2 Linear Probing 구조

 - '버켓 공간을 우선사용' 하는 것을 목표로 새로들어올 값의 인덱스와 테이블의 인덱스가 달라도 새 값을 비어있는 가장 가까운 버켓 공간에 넣는다.

 - 인덱스와 값이 일치하지 않을 경우 자료찾는 방법 : 밑의 그림의 예에서 100의 값을 찾고 싶을 때는 먼저 100의 인덱스 결과값인 1을 조회하고, 1에 찾고자하는 자료가 없으면 다음 버켓을 조회하여 100을 찾아나아간다.

 - 값을 삭제하면, 버켓을 조회할 때, 삭제된 값에서 검색이 멈추기 때문에 오류가 발생할 수 있다. 따라서 값을 삭제한 뒤에는 삭제한 공간에 Dummy node를 삽입한다.

 - Dummy node가 일정량 이상 쌓일 경우 새로운 array를 만들어서, 다시 hash를 리빌딩 함으로써, Dummy Node를 주기적으로 없애 줘야 성능을 유지할 수 있다.

 

마지막에 들어올 값 100은 Chaining 방식이었다면, 1번 인덱스에 속하여 값 123뒤에 이어져야 했지만, Linear Probing 방식에서는 비어있는 2번 인덱스 공간에 값을 저장한다.

 

7. 테이블 리사이징

 - Linear Probing 방식을 사용할 때, 버켓공간을 다 소모하여 새 값이 들어갈 자리가 없을 때, 테이블의 공간을 늘려 값을 저장할 공간을 마련하는 기법

 - 테이블의 공간을 늘린 후, 기존의 데이터를 다시 해시함수에 보내고, 다시 테이블을 재정렬한다.

 - 결과적으로 공간이 늘어나고 테이블이 재정렬되어 Linear Probing방식을 계속 사용할 수 있게 된다.

 

 

 

 

 

 

* 내용 및 자료 출처

( https://www.youtube.com/watch?v=xls6jEZNA7Y ) 

* 좀더 깊게 이해하고 싶을 경우

( https://bcho.tistory.com/1072 )