[2019.04.03] 자료구조-해시테이블

해시함수란 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 이때 매핑 전 원래 데이터의 값을 키, 매핑 후 데이터의 값을 해시값, 매핑하는 과정 자체를 해싱 이라고 한다. 만약 두개의 키가 동일한 해시값을 가지게 되면, 해시충돌이 일어난다.

# 해시 테이블의 장점

• 적은 리소스로 많은 데이터를 효율적으로 관리가 가능하다.
• 모든 데이터를 살피지 않고도 검색, 삽입, 삭제가 빠르게 수행가능하다.

hash테이블게 key값을 넣으면 hash에 저장된 index값이 반환된다. bucket영역에서 index값에 매칭되는 value값을 찾아낸다.

이렇게 key값으로 인해서 value값을 가져올 수 있다.

hashTable에서는 인덱스값을 고유하게 만드는 것이 중요하다. 데이터를 삽입 중에 특정 키가 같은 인덱스 번호를 가리키고 있게 되면 해쉬 충돌을 일으키기 때문에, 데이터를 삽입 시 각 키가 하나의 인덱스만 가리키게 해야한다. 

# 해쉬 충돌을 피하기 위한 여러가지 방법

1. 개방주소법 : 해시 충돌이 발생하면, 다른 해시 버킷에 해당 자료를 삽입하는 방식. 해쉬 버킷이 채워질수록 개방주소법을 쓸 일이 잦아지므로 비효율적. ex) 순차적 탐색, 2차함수를 이용한 탐색, 2차함수 탐색으로 충돌 후 한번 더 2차 해쉬함수 이용

순차적 탐색 방식

2. 분리 연결법 : 해시충돌이 잘 발생하지 않도록 보조 해시함수를 통해 조정.

 -링크드리스트 방식 : 충돌이 나면 해당 index의 bucket에 링크드리스트처럼 추가를 하는 방식이다.

링크드리스트 방식

 hashing 부분 수도코드