[알고리즘 과제] 해싱(Hashing)

1. 해싱(Hashing)이란?

데이터를 해시 함수(Hash Function)를 이용하여 해시 테이블(Hash Table) 내에서 주소값 계산 후, 빠르게 저장하고 원하는 데이터를 빠르게 검색할 수 있도록 하는 알고리즘.

 

[해싱 알고리즘]
① 데이터를 매개 변수로 입력
② 데이터로부터 테이블 내의 주소를 해시
③ 주소를 이용하여 요소에 접근

 

2. 해싱(Hashing) 알고리즘 성능

• 일반적으로 O(1)
• Overflow 또는 Collision 발생 시에는 O(1)보다 성능이 떨어진다.
• 성능 향상을 위해 Hash Table의 크기를 적절히 크게 할 필요가 있다.

 

3. 해싱(Hashing) 의 활용

• 소량의 데이터를 처리할 때(데이터 개수가 많지 않을 때) 적합한 알고리즘
• 운영체제, DB, 네트워크 등 여러 분야에서 소량의 데이터를 처리할 때 사용
• 데이터의 위·변조를 막기 위해 전자서명이나 보안 알고리즘 등에 사용