Hash 개념

Hash 예시

 

• 해시는 데이터를 다루는 기법 중의 하나로, 검색과 저장을 아주 빠르게하는 자료구조이다.
• 데이터를 저장할 때 Key-Value 형태로 데이터가 존재하고, Key값이 배열의 인덱스로 저장되기 때문에 검색과 저장이 빠르게 일어나게 된다.
• 해시 함수는 key값을 고정된 길이의 hash로 변환하는 역할을 한다.
• 해시 함수에서 hashing을 통해 해시값으로 변경하며, 이 해시값이 저장 위치가 된다고 생각하면 된다.
• 서로 다른 key가 같은 해시가 되는 경우를 해시 충돌이라고 하며, 이 충돌의 확률을 최대한 줄이는 함수를 만드는 것이 중요하다.

장점	단점
중복을 제거할 수 있다. 데이터 캐싱, 보안에 주로 사용된다. 배열의 인덱스로 접근하기 때문에 삽입, 삭제 등의 연산이 빠르다.	공간 복잡도가 커진다. 충돌이 발생할 수 있다. 충돌이 발생할 경우 시간 복잡도는 O(n)에 가까워진다. 순서가 있는 배열에는 어울리지 않는다.