[자료구조] Hash

Hash란?

데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것
해시 함수를 구현하여 데이터 값을 해시 값으로 매핑함.
그래서 데이터가 많아지면 다른 데이터가 같은 해시 값으로 충돌나는 현상이 발생함

해시는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 가짐. 그래서 average case에 대해서 시간복잡도가 O(1)임.

해시 자료구조에 대해 설명해 주세요.

데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것. 그래서 데이터가 많아지면 다른 데이터가 같은 해시 값으로 충돌나는 현상이 발생함

해시값이 충돌했을 때, 어떤 방식으로 처리할 수 있을까요?

체이닝, 개방주소법 등이 있음. 체이닝은 연결리스트로 중복된 값을 저장하는 방법임. 개방 주소법은 충돌이 발생한 경우, 다른 빈 슬롯을 찾아 데이터를 저장하는 방법임. 선형 탐사, 제곱 탐사, 더블 해싱이 이에 해당함
주로 구현이 간단한 체이닝 방법을 사용함

값이 주어졌을 때, 어떻게 하면 충돌이 최대한 적은 해시 함수를 설계할 수 있을까요?