✍️ HashTable이란..
해시 테이블(HashTable)은 키(key)와 값(value)을 저장하는 자료구조로, 키를 값에 매핑(mapping)하여 값에 대한 연산을 효율적으로 수행할 수 있습니다. 해시 테이블은 배열과 같은 구조를 가지고 있지만, 배열과 달리 인덱스가 정수가 아닐 수 있습니다. 해시 테이블은 주로 검색, 삽입, 삭제와 같은 연산이 빈번하게 일어나는 경우에 사용됩니다.
📝 HashTable 자료 구조의 특징
-
빠른 탐색 속도: 해시 테이블은 키(key)를 이용하여 값을 찾아내므로 매우 빠른 탐색 속도를 보입니다.
-
충돌 해결: 해시 테이블에서는 서로 다른 키(key)가 같은 해시 값(hash value)을 가질 수 있습니다. 이 경우 충돌을 해결하기 위한 다양한 기법들이 존재합니다.
-
크기 조절 가능: 해시 테이블은 동적으로 크기를 조절할 수 있으며, 필요에 따라 메모리를 할당하거나 해제할 수 있습니다.
-
순서 보장 안됨: 해시 테이블은 입력된 순서대로 값을 저장하지 않으므로, 순서를 보장하지 않습니다.
-
메모리 사용량 높음: 충돌을 해결하기 위해 여분의 메모리를 사용하므로, 메모리 사용량이 높을 수 있습니다.
📝 HashTable 구현 방식 및 작동 원리
해시테이블(Hashtable)은 키-값(key-value) 쌍의 데이터를 저장하는 자료구조로, 각각의 키에 대해 값을 매핑(mapping)하여 빠르게 접근할 수 있는 구조를 갖추고 있다. 해시테이블의 기본적인 아이디어는 입력된 값을 특정한 함수를 이용해 변환하고, 변환된 값을 인덱스로 사용하여 값을 저장하고 탐색하는 것이다. 이 때, 변환 함수를 해시 함수(hash function)라고 하며, 해시 함수는 입력 값에 대해 고정된 길이의 값을 반환한다. 해시테이블에서는 이 반환된 값을 인덱스로 사용하여 값을 저장하고 탐색한다. 이렇게 해시테이블은 키에 대한 해시 함수의 적용 결과를 인덱스로 사용하므로, 많은 양의 데이터를 빠르게 처리할 수 있는 장점을 갖는다.
✍️ HashTable의 장단점 및 예시
📝 장점
-
검색, 삽입, 삭제의 시간 복잡도가 O(1)로 매우 빠릅니다.
-
많은 양의 데이터를 빠르게 처리할 수 있습니다.
-
해시테이블을 이용하면 데이터의 중복을 피할 수 있습니다.
📝 단점
-
충돌이 일어날 경우 선형 검색 등의 추가 작업이 필요하므로 성능이 떨어집니다.
-
해시 함수의 충돌을 방지하기 위해 충분한 크기의 배열이 필요합니다.
-
해시테이블의 저장공간이 메모리를 많이 차지할 수 있습니다.
📝 예시
-
데이터베이스 인덱싱: 데이터베이스의 인덱싱은 해시테이블을 사용하여 더 빠른 데이터 검색을 가능하게 합니다.
-
검색 엔진: 검색 엔진에서 키워드를 검색할 때, 해시테이블은 더 빠른 검색을 가능하게 합니다.
-
캐시 메모리: 캐시 메모리에서도 해시테이블이 사용됩니다. 데이터를 캐시 메모리에 저장할 때, 해시테이블을 사용하여 더 빠른 검색을 가능하게 합니다.
-
보안: 암호화된 메시지의 전자 서명을 확인하거나 데이터 무결성을 보호하기 위해 해시테이블이 사용됩니다.
-
게임: 해시테이블은 게임에서도 사용됩니다. 예를 들어, 체스 게임에서 현재 게임 상태를 저장하고 검색할 때 해시테이블을 사용합니다.
✍️ JavaScript 내에서의 HashTable
자바스크립트 내에서 HashTable을 구현하는 방식은 Map을 구현하는 방식과 동일하다
그렇기 때문에 따로 코드를 적는것보다는 이전에 올렸던 Map의 게시글을 참가하는 것이 빠르다.
✍️ HashTable 시간 복잡도
해시 테이블의 시간 복잡도는 O(1)입니다. 삽입, 삭제, 검색 모두 상수 시간 내에 수행할 수 있습니다. 단, 해시 충돌이 발생하면 최악의 경우 선형 시간 복잡도인 O(n)이 될 수 있습니다.
