해시 (Hash)

해싱 개념

• 데이터 관리/유지 자료구조
• 리소스 < 속도
• 임의의 크기를 가진 데이터(Key)를 고정된 크기의 데이터(Value)로 변환시켜 저장하는 것
• 키(key)란 매핑 전 원래 데이터 값
• 해시값(hash value)란 매핑 후 데이터 값
• 키에 대한 해시값을 구하는 과정이 hashing. 이때 사용하는 함수(알고리즘)를 해시함수라고 함
• 해시값 자체를 index로 사용하기 때문에 평균 시간복잡도가 O(1)로 매우 빠름

해싱 과정

• 키(key) -> 해시 함수(hash function) -> 해시 값(hash value)

해시테이블

• 해시 함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인(index) 혹은 주소 삼아 데이터의 값(value)을 키와 함께 저장하는 자료구조
• 데이터가 저장되는 곳을 버킷(bucket) 또는 슬록이라고 함
• 해시테이블의 기본 연산은 삽입, 삭제, 탐색
• key -> hash function -> buckets [index(hash value) : data]

해시 테이블 장점

• 해시 충돌 발생 가능성이 있지만, 적은 리소스로 많은 데이터를 효율적으로 관리할 수 있음
• 하드디스크, 클라우드에 존재하는 데이터(key)들은 무한에 가까운데, 이것들을 유한한 개수의 해시값으로 매핑하면서 작은 크기의 캐시메모리로도 프로세스를 관리할 수 있음
• index에 해시값을 사용하므로 모든 데이터를 살피지 않아도 검색과 삽입/삭제를 빠르게 수행가능
• 해시 함수는 언제나 동일한 해시값을 리턴하고, 해당 색인만 알면 해시테이블의 크기에 상관없이 데이터에 빠르게 접근 가능
• 데이터 엑세스(삽입, 삭제, 탐색) 시 시간복잡도 O(1)을 지향