Hash Function

자료 구조의 필요성

• 프로그래밍에서는 데이터를 효율적으로 저장하고 검색하는 것이 매우 중요하다. 데이터를 저장할 때 적절한 자료 구조를 선택해야만 검색 및 처리 속도를 향상시킬 수 있다.
• 배열과 리스트는 직관적인 자료 구조이지만 데이터의 크기가 커지면 특정 데이터를 찾는 데 걸리는 시간이 데이터 양에 비례해서 증가하는 단점이 있다. 이때 대안으로 트리(Tree)나 해시 테이블(Hash Table) 같은 자료 구조가 필요하다.

 

트리(Tree) 구조

• 트리 자료 구조, 특히 레드-블랙 트리와 같은 균형 이진 트리는 검색과 삽입 작업에서 O(log n)의 시간 복잡도를 가진다. 이는 배열의 선형 탐색 O(n)보다 효율적이다.
• 트리를 사용하면 많은 데이터에도 불구하고 성능이 어느 정도 보장되지만 데이터의 양에 따라 성능 저하가 발생할 수 있다.

 

해시 테이블(Hash Table)

• 해시 테이블은 데이터를 해시 함수(Hash Function)를 통해 고정된 크기의 배열에 저장하고 나중에 검색할 때 해시값을 이용해 데이터를 빠르게 찾는 자료 구조이다.
• 해시 테이블의 주요 장점은 O(1)에 가까운 시간 복잡도로 데이터를 저장하고 검색할 수 있다는 것이다. 이는 배열이나 트리보다 훨씬 효율적이다.

 

 

해시 함수(Hash Function)

• 해시 함수는 임의의 길이의 데이터를 고정된 길이의 해시값으로 변환하는 함수이다. 예를 들어, 숫자 7을 입력받아 해시 함수를 통해 일정한 위치에 저장할 수 있는 주소로 변환한다.
• 좋은 해시 함수의 조건
  1. 빠른 계산: 해시값을 빠르게 계산할 수 있어야 함
  2. 균등한 분포: 데이터가 테이블에 고르게 분포되어야 충돌(Collision)이 적음
• 해시 함수는 입력값이 다르면 다른 해시값을 반환해야 하지만 드물게 같은 해시값을 반환하는 경우가 있는데 이를 해시 충돌이라 한다.

 

해시 충돌(Hash Collision) 해결 방법

• 해시 충돌이 발생하면 동일한 해시값을 가진 두 데이터가 같은 위치에 저장되려고 하기 때문에 충돌을 해결하는 방법이 필요하다. 주요 충돌 해결 방법은 다음과 같다.
  1. 체이닝(Chaining) : 충돌이 발생한 경우, 같은 해시값을 가진 데이터를 연결 리스트로 이어서 저장하는 방법. 해당 해시값에 접근한 후, 연결 리스트를 순차적으로 탐색해 원하는 데이터를 찾는다.
  2. 개방 주소법(Open Addressing) : 충돌이 발생했을 때 빈 자리를 찾아 데이터를 저장하는 방법. 여기에는 여러 변형 기법이 존재한다.
     • 선형 조사(Linear Probing) : 충돌이 발생하면 바로 다음 빈 공간에 데이터를 저장
     • 2차 조사(Quadratic Probing) : 충돌 시 더 큰 간격으로 빈 자리를 탐색해 충돌을 해결
     • 이중 해싱(Double Hashing) : 첫 번째 해시 함수로 충돌이 발생하면 두 번째 해시 함수로 새로운 해시값을 계산해 빈 공간을 찾는다

 

해시 함수의 특성

• 해시 함수는 결정적이어야 한다. 즉, 동일한 입력값에 대해 항상 동일한 출력값(해시값)을 반환해야 한다.
• 무결성 : 서로 다른 데이터에 대해 동일한 해시값을 반환할 확률은 매우 낮아야 한다. 따라서 해시값을 통해 데이터의 무결성을 확인할 수 있다.
• 1방향성 : 해시 함수는 해시값을 이용해 원래 데이터를 복원할 수 없다. 즉, 해시값만으로는 원본 데이터를 추출할 수 없다는 특성을 가진다.

 

SHA 해시 알고리즘

• SHA(Secure Hash Algorithm)는 널리 사용되는 암호학적 해시 함수이다. 특히 SHA-256은 256비트 해시값을 생성하는데, 매우 작은 변화에도 완전히 다른 해시값을 생성하는 특성을 가지고 있다.
• SHA-256은 2^256개의 가능한 해시값을 생성할 수 있어 충돌 가능성이 거의 없다. 이로 인해 데이터의 무결성 검증, 비밀번호 저장, 블록체인과 같은 보안이 중요한 시스템에서 많이 사용된다.

 

해시 테이블의 실제 활용

• 데이터베이스 : 데이터 검색과 조회 속도를 높이기 위해 인덱싱 기법으로 사용된다.
• 파일 무결성 검증 : 파일이 변조되었는지 확인할 때 해시값을 비교해 변조 여부를 판단한다.
• 클라우드 스토리지 : 해시값을 통해 중복 파일을 탐지하고 동일 파일을 효율적으로 관리할 수 있다.
• 암호 저장 : 비밀번호를 원본 데이터 대신 해시값으로 저장해 보안성을 높인다.
• 블록체인 : 블록의 고유한 식별자로 해시값을 사용해 데이터의 무결성과 변조 방지를 보장한다.

 

 

이와 같이 해시 함수와 해시 테이블은 자료 저장과 검색에서 매우 중요한 역할을 하며, 특히 충돌 해결 방법과 해시 함수의 설계는 시스템의 성능에 큰 영향을 미친다.