📖 해시(Hash)의 정의
-
해시는 데이터를 저장하고 검색할 경우 사용하는 자료 구조 중 하나입니다.
-
정확하게는 특정한 함수를 사용하여 추출한 값을 활용하는 것입니다. 여기서 말하는 함수는 입력되는 데이터들끼리 충돌이 발생하지 않게 정리하는 알고리즘입니다.
-
실제로 이 알고리즘을 어떻게 구현하는지에 따라 사용 용도와 성능이 달라집니다.
📖 해시는 어떻게 접할까?
-
해시는 주로 방대한 양의 데이터를 저장하거나, 검색할 경우, 해시를 암호처럼 사용하여 데이터를 보호하는 경우에 접하게 됩니다.
-
즉 위의 말은 메시지 인증 코드, 디지털 서명, 비밀번호 등 암호학, 검색 자료 구조를 다룰 경우 접하는데, 이는 소프트웨어의 변경을 검출할 경우 활용되는 방법입니다.
-
응용 소프트웨어를 배포할 경우 어떤 공격자에 의해 파일이 변조되는 경우가 종종 있습니다. 소프트웨어 최초 개발자는 이를 해결하기 위해 해시 값을 비교하여 파일이 변경되었는지 검사합니다.
📖 해시 알아보기
📌 해시의 개념
-
해시는 입력데이터를 고정된 길이의 데이터로 변환한 값입니다.
-
해시 값, 해시 코드, 체크섬이라고도 부르며 이 값들은 해시 함수에 의해서 얻어디는 결과인 것이죠.
-
간단하게 설명하자면, 데이터의 키 값이 해시 함수를 통해서 변환된 간단한 정수입니다. 이렇게 정수로 변환된 해시는 배열의 인덱스, 위치 데이터 값을 저장하거나 검색할 경우 활용됩니다.
📌 해시 함수
-
해시 함수는 입력받은 데이터를 해시 값으로 출력시키는 알고리즘입니다.
-
이렇게 출력된 해시 값은 알고리즘에 따라 다양한 형태를 보이기 때문에 목적에 맞게 다양하게 설계되고 자료 구조, 캐시, 검색 등등 여러 분야에서 유용하게 사용됩니다.
-
보통 복잡하지 않은 알고리즘으로 구현되기 때문에 메모리 시스템 자원을 덜 소모한다는 특징 역시 가지고 있습니다. 입력된 데이터가 같으면 해시 값도 항상 같으며, 고른 범위에 균일하게 분포합니다.
📌 해시 테이블
-
해시 테이블을 키와 값을 함께 저장해 둔 데이터 구조입니다.
-
데이터가 행과 열로 구성된 표에 저장되었다고 이해하면 쉽습니다. 여기서 값이 저장되는 공간을 버킷 또는 슬롯이라고 부릅니다.
-
해시 테이블은 신속한 저장 및 검색을 위해 만들어졌습니다. 해시 값을 인덱스로 환산해서 저장하는 것이 기본 원리이며, 필요한 데이터를 찾을 경우 순서를 지킬 필요없이 저장 위치를 즉시 알아낼 수 있습니다.
-
그렇기 때문에 데이터의 양이 방대해져도 검색에 소요되는 시간은 항상 같습니다.
-
해시테이블의 데이터를 저장할 경우 위치가 무작위로 지정되기 때문에 여유 공간이 생기는데, 이 점은 장점으로 작용할 수 있습니다. 데이터가 입력되지 않은 여유 공간이 많을수록 문제없이 좋은 성능을 발휘하기 때문입니다.
📌 해시의 장점
-
빠른 검색 속도: 해시 테이블은 해시 함수를 사용하여 데이터에 대한 인덱스를 생성하므로 데이터를 빠르게 검색할 수 있습니다. 이는 평균적으로 O(1)의 시간 복잡도를 가집니다.
-
유연성: 해시 테이블은 다양한 데이터 유형을 저장할 수 있습니다. 문자열, 숫자, 객체 등 다양한 데이터 유형을 해싱하여 저장할 수 있습니다.
-
메모리 효율성: 적절한 해시 함수를 선택하면 충돌을 최소화하여 메모리 공간을 효율적으로 사용할 수 있습니다.
-
캐시 지원: 해시 테이블은 캐시 지원 구조로 사용될 수 있어, 캐시 작업에 효과적입니다.
📌 해시의 단점
-
충돌 가능성: 해시 함수는 서로 다른 입력에 대해 동일한 출력을 생성할 수 있습니다. 이로 인해 충돌이 발생할 수 있으며, 충돌이 자주 발생하면 검색 속도가 저하될 수 있습니다.
-
해시 함수 선택의 어려움: 적절한 해시 함수를 선택하는 것이 중요합니다. 특정 데이터 세트에 대해 최적의 해시 함수를 찾는 것은 어려울 수 있습니다.
-
순서 보장의 어려움: 해시 테이블은 데이터를 키-값 쌍으로 저장하며, 일반적으로 삽입 순서를 보장하지 않습니다. 이는 데이터를 순서대로 유지해야 할 때 문제가 될 수 있습니다.
-
메모리 요구량: 해시 테이블은 충돌을 최소화하기 위해 일정한 크기의 메모리를 요구합니다. 데이터의 양이 많을 경우에는 메모리 요구량이 증가할 수 있습니다.
