[알고리즘] 해시

해시

; 다양한 길이를 가진 데이터를 고정된 길이의 데이터로 매핑한 값

- 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도 가짐

- 해시 알고리즘을 통해 고유한 인덱스를 얻음

- 적은 자원으로 많은 데이터를 효율적으로 관리하기 위해 사용

 

해시 함수

; 데이터를 효율적으로 관리하기 위해, 임의의 길이의 데이터를 수학적 연산을 통해 고정된 길이의 데이터로 매핑하는 함수

 

해시 테이블

; 키와 값을 매핑해둔 데이터 구조

 

충돌 해결법

1. 개방 주소법

; 해시 충돌이 발생하면 해시 함수로 얻은 주소가 아닌, 다른 주소 공간에 데이터를 저장하는 방식

2. 폐쇄 주소법

; 인덱스로 인해서 충돌이 발생하면 그 인덱스가 가리키고 있는 연결 리스트에 노드를 추가