[알고리즘] 11. 해시 테이블(Hash Table)

• 공부한 날짜: 2021. 10. 28

• 해시: 데이터를 입력 받으면 완전히 다른 모습의 데이터로 바꾸어 놓은 작업
• 해시테이블: 데이터의 해시 값을 테이블 내의 주소로 이용하는 알고리즘/ 
• 데이터를 담을 테이블을 미리 크게 확보해 놓은 후, 입력받은 데이터를 해시하여 테이블 내의 주소를 계산하고 이 주소에 데이터를 담는 것
• 암호화: 데이터를 해시를 통해 변환하는 과정, 예시 SHA
• 데이터 축약: 해시를 통해 같은 길이의 데이터로 변환함으로써 데이터를 축약할 수 있음 

 

• 해시함수: 나눗셈법/ 자릿수 접기

1. 나눗셈법: 주소 = 입력값 % 테이블의 크기

가능한 주소는 0~N-1

테이블 크기는 소수 이용

문제점: 충돌 발생(다른 데이터, 동일한 주소값 가짐) & 클러스터 발생(데이터들이 한 곳에 모임)

 

**까먹고 구현 안해서 나중에 구현하고 붙여넣기 

 

2. 자릿수 접기: 숫자를 접어 일정한 크기 이하의 수로 만드는 방법 

접는 것: 숫자의 각 자릿수를 더해 해시 값을 만드는 것

 

• 충돌해결하기: 체이닝/ 개방 주소법(선형탐사, 제곱탐사, 이중해싱, 재해싱)

충돌 해결 하는 방법:

(1) 개방 해싱(open hashing): 해시 테이블 주소 바깥에 새로운 공간을 할당하여 문제 수습

(2) 페쇄 해싱(closed hashing): 처음에 주어진 해시 테이블 공간 안에서 문제 해결하는 방법

 

1. 체이닝: 충돌이 발생하면 각 데이터를 해당 주소에 있는 링크드 리스트에 삽입하여 문제를 해결하는 기법 

연산: 삽입은 앞으로 충돌할 것을 고려해서 작성, 탐색/삭제는 충돌했다는 가정하에 작성

 

*체이닝 기반 해시 테이블의 탐색

(1) 찾고자 하는 목표값을 해싱하여 링크드 리스트가 저장되어 있는 주소를 찾는다

(2) 이 주소를 이용하여 해시 테이블에 저장되어 있는 링크드 리스트에 대한 포인터를 생성

(3) 링크드 리스트의 앞에서부터 뒤까지 차례대로 이동하며 목표값이 저장되어 있는지 비교. 목표값과 링크드 리스트 내의 노드 값이 일치하면 해당 노드의 주소를 반환한다.

 

*체이닝 기반 해시 테이블의 삽입

: 충돌 발생 시 삽입은 같은 주소에 있는 링크드리스트의 헤드 부분에 새노드를 삽입하면 된다.(테일을 찾으려면 순차탐색을해야하므로 비효율적)