[DataStructure] 해시 테이블

[해시 테이블]

해시 테이블

• 해시 테이블(hash table) : 키(key)와 값(value)의 대응으로 이루어진 테이블과 같은 형태의 자료구조

• 키(key) : 해시 테이블에 대한 입력

• 값(value) : 키를 통해 얻고자 하는 데이터

• 버킷(bucket) : 값이 저장되어 있는 곳

  • 여러 개 존재 → 여러 버킷이 배열 형성

• 로드 팩터(load factor) : 해시 테이블에 저장된 데이터 수를 버킷의 수로 나눈 값

  • 테이블이 얼마나 가득 차 있는지에 대한 지표
  • 로드 팩터가 클수록 해시 테이블 성능 ↓

• 구조

  

• 검색, 삽입, 삭제 연산의 시간 복잡도 : O(1) → 입력과 무고나하게 항상 일정한 속도 보장

• 단점

  • 속도 ↑ but, 메모리 공간 소모 多
  • 공간 복잡도가 시간 복잡도만큼 우수하지 X
  • 충돌 문제 해결 필요

---

[해시 함수]

해시 함수

• 해시 함수(hash function) : 임의의 길이를 지닌 데이터를 고정된 길이의 데이터로 변환하는 단방향 함수

• 특정 입력 데이터를 고정된 길이의 해시 값으로 변환 가능

• 해시 값을 토대로 어떤 데이터가 입력 되었는지 도출 어려움

• 무작위 값을 만들거나 단방향 암호를 만들 때, 데이터 무결성을 검증하기 위해 사용

  

해시 알고리즘

• 해시 알고리즘(hash algorithm) : 해시 함수의 연산 방법
• 같은 데이터여도 적용된 알고리즘에 따라 도출되는 해시 값의 길이나 값이 달라짐
• 종류
  • MD5
  • SHA-1
  • SHA-256
  • SHA-512
  • SHA3
  • HMAC

---

[해시 충돌]

해시 충돌

• 해시 충돌(hash collision) : 서로 다른 키에 대해 같은 해시 값이 대응되는 상황

해결 방법 - 체이닝

• 체이닝(chaining) : 충돌이 발생한 데이터를 연결 리스트로 추가

  • 단순 노드 추가이기 때문에 서로 다른 키가 같은 위치로 해시
  • 하나의 테이블 인덱스에 여러 데이터가 연결리스트로 존재 가능

  

해결 방법 - 개방 주소법

• 개방 주소법(open addressing) : 충돌이 발생한 버킷의 인덱스가 아닌 다른 인덱스에 데이터를 저장하는 방법
• 조사(probe) : 충돌 발생 시 비어 있는 다른 버킷의 인덱스 찾는 과정
• 선형 조사법(linear probing) : 충돌이 발생한 인덱스의 다음 인덱스부터 순차적으로 가용한 인덱스 찾는 방법
  • 단점
    • 군집화 될 수 있음
• 군집화(clustering) : 충돌 시 발생하는 인덱스 인근에 충돌이 발생한 여러 데이터가 몰려 저장되는 것
  • 오랜 순차 탐색 필요 → 성능 악화 가능성 高
• 이차 조사법(quadratic probint) : 선형 조사법 완화, 총돌 발생 시 인덱스에서 제곱수만큼 떨어진 거리에 위치한 인덱스 찾는 방법
  • 군집화 문제 완화 O → 근본적인 해결 방법 X

해결 방법 - 이중 해싱

• 이중 해싱(double hashing) : 2개의 해시 함수 사용, 충돌 발생 시 다른 해시 함수(보조 해시 함수)에 대한 해시 값만큼 떨어진 거리에 위치한 인덱스 찾는 방법
  • 무작위 인덱스 생성 → 선형 조사법의 군집화 문제 대부분 해결 가능

---

💡 참고 자료

• Hash Table
• Hash Function
• Open addressing