[CS/Computer Science][자료구조/Data Structure] 해시 테이블

이어서, 이번에는 해시 테이블에 대해 알아보겠습니다.

1. 해시 테이블

정의

Key와 Value의 쌍으로 구성된, 표와 유사한 형태의 자료구조

• Key: 해시 테이블에 대한 입력
• Value: Key를 통해 얻고자 하는 데이터
  
  운영체제 내에서 해시 테이블이 자주 이용 → 대응관계가 필요한 다양한 상황에 녹아들어 있음
  
  

구조

1. 해시함수: Key를 인자로 활용해 인덱스 반환
2. Key를 통해 얻고자 하는 데이터: Bucket에 저장
   • 여러 개의 Bucket이 모여서 배열 형성
3. Key를 해시 함수에 통과시켜 원하는 Bucket에 접근
   
   

장단점

장점 - "빠른 검색속도"(해시 테이블을 이용하는 명백한 이유)

• 입력과 무관하게, O(1)의 시간 복잡도를 보장함 (자료 구조들 중, 이례적인 검색 속도를 제공) 단점
  1. 검색 속도가 빠른 만큼, 데이터 규모가 매우 큼 → 공간 복잡도는 시간 복잡도만큼 우수하지 않음
  2. 해시 충돌 문제 발생
     
     

2. 해시 함수

정의

“임의 길이의 데이터 → 고정된 길이의 데이터” 변환해주는 단방향 함수

• 단방향 함수이기에, 해시 값을 토대로 어떤 데이터가 입력되었는지는 찾아내기 어려움
  
  

해시 알고리즘

• 해시 함수의 연산 방법을 일컫는다.
• 대표 알고리즘: MD5, SHA-1, SHA-256, SHA-512, HMAC
• 같은 데이터, 다른 해시 알고리즘 → 도출되는 해시 값 및 해시 길이가 달라짐
  
  

해시 함수의 용도

1. 무작위 값 생성
2. 단방향 암호 생성
3. 데이터 무결성 검증
   • A에서 B로 데이터를 보내는 상황을 가정할 때,
     1. A(송신)측이 보내는 데이터에 대한 해시 값 계산
     2. A측이 B측에 데이터 전달
     3. B(수신)측이 받은 데이터에 대한 해시 값 계산
     4. A측이 계산한 해시 값과 B측이 계산한 해시 값이 동일하다면, 바르게 전송
4. 비밀번호 저장
   • 웹 사이트에 로그인 시, 우리는 암호를 입력하지만 운영자가 알 수 있지는 않음 → 개인정보를 웹 사이트에 저장할 때에는, 단방향 암호화를 통한 저장을 하도록 규제
   • 비밀번호 암호화 용도의 해시 함수: bcrypt, PBKDF2, scrypt, argon2 등
     
     

3. 해시 충돌

정의

서로 다른 키에 대해, 같은 해시 값이 대응되는 현상 ex) 서로 다른 pdf 파일이 같은 해시 값을 갖는 현상 → 다른 파일을 같은 데이터로 판단 → “해시 충돌이 발생”

해결책

1. 체이닝
   • 충돌이 발생한 데이터에 대해, 연결 리스트로 추가
     • 하나의 인덱스에 대해, 여러 데이터가 연결 리스트의 노드로 존재
     • 이 경우, 검색속도가 빠른 해시 테이블의 장점을 살리지 못할 수 있음 (연결 방식이 연결 리스트와 동일해지므로)
2. 개방 주소법
   • 충돌이 발생한 버킷의 인덱스가 아닌, 다른 인덱스에 데이터 저장
     • “조사”의 과정을 통해, 비어있는 인덱스를 찾는 과정
     • 조사 방법 (f: 해시 함수, key: 키값)
       1. 선형 조사법(Linear probing)
          • 충돌이 발생한 다음 인덱스부터 순차적으로 탐색
          • f(key)에서 충돌이 발생했다면? → $f(key)+1$, $f(key)+2$,…순으로 가용한 버킷 인덱스 찾음
          • 단점: 군집화 현상 발생 → 충돌이 발생한 데이터들이 몰려서 저장될 수 있음
       2. 이차 조사법(Quadratic probing)
          • 충돌이 발생한 인덱스의 제곱수만큼 떨어진 거리에 위치한 인덱스 탐색
          • f(key)에서 충돌이 발생했다면? → $f(key)+1^2$, $f(key)+2^2$,…순으로 가용한 버킷 인덱스 찾음
          • 군집화 문제는 완화 가능하지만, 이것 또한 제곱수의 규칙성에서 비롯된 방법이기에, 근본적 해결이라 볼 수는 없음
       3. 이중 해싱(Hashing)
          • 두 개의 해싱 함수를 사용하여, f 함수에 대해 충돌이 발생하였다면 g 함수에 대한 해시 값만큼 떨어진 거리에 위치하는 인덱스를 탐색하는 방법
          • f(key)에서 충돌이 발생했다면? → $f(key)+g(key)$, $f(key)+2g(key)$, $f(key)+3g(key)$ …순으로 가용한 버킷 인덱스 찾음
          • 또 다른 해시 함수를 활용하여 무작위로 인덱스를 생성해 줌으로서, 군집화 문제 상당수 해결 가능
            
            

프로그래밍 언어 별 해시 테이블 구현