[Data Structure] 해시

해시란

임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것을 말한다.

데이터를 효율적으로 관리한다.

해시 함수를 통해 데이터 값을 해시 값으로 매핑한다.

 

해시 테이블을 사용하면 적은 자원으로 많은 데이터를 효율적으로 관리할 수 있다. 빠른 데이터 검색이 가능하다.

해시테이블의 시간 복잡도 : O(1)

 

해시의 특징

• 무결성
• 보안성 : 해시는 복호화가 불가능하다.

Collision 현상

데이터가 많아지면서 다른 데이터가 같은 해시 값으로 충돌나는 현상이다. 

 

충돌 문제 해결

• 체이닝 : 연결리스트로 노드를 계속 추가해나가는 방식
• Open Addressing : 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용
• 선형 탐사 : 정해진 고정 폭으로 옮겨 해기값의 중복을 피함
• 제곱 탐사 : 정해진 고정 폭을 제곱수로 옮겨 해시값의 중복을 피함