[Algorithm Study] Hash 자료구조

해시란?

- (key,value) 쌍으로 이루어진 자료구조

 

 

해시의 구현 방식

1. 배열 생성

2. Hash(key) 반환값에 해당하는 인덱스에 value를 저장한다

 

 

충돌 해결 방식

- 개별 체이닝 방식 : Linked List 방식으로 해결

- 오픈 어드레싱 방식 : 빈 공간을 찾아 해결

 

개별 체이닝(Separate Chaning) 방식

 

오픈 어드레싱(Open Addressing) 방식

 

해시를 사용하는 이유?

- 배열의 경우 데이터의 연속성이 그 목적이므로 (key,value)의 key가 연속된 정수로 설정된 것

- 해시의 경우 목적에 따라 key 값을 설정할 수 있다

- 선형 탐색에 비해 탐색의 속도가 매우 빠르다