CS 지식/자료구조

[자료구조] 해시테이블

ghan2 2024. 10. 27. 00:45

 

🗄️ 해시 테이블이란?

 

 

해시 테이블(hash table)이란 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. 즉, 키를 사용하여 그 키에 해당하는 값을 찾기 위해 필요한, 빠른 속도로 키를 검색할 수 있는 자료 구조를 의미한다. 

 

위키위키

그림 자료를 바탕으로 다시 이해하면, 해시 테이블은 데이터를 저장하는 일종의 자료구조이다. 

 

예를 들어 각 사람의 전화번호를 저장하고자 할 때,

각 사람의 이름을 키(key) 값으로 사용하고 해당 사람의 전화번호는 키와 매칭되는 공간에 적재한다.

이 때 키를 인덱스로 사용하기 위해 해시 함수(hash function)를 거쳐 인덱스로 만드는 과정이 추가되는 것이다. 

 

 

 

해시 함수를 왜 사용할까?

 

여기서 사용하는 키 값은 문자열이 될 수도 있고 숫자나 파일 데이터가 될 수도 있다. 해시 함수는 어떤 특정한 규칙을 이용해서 입력받은 키 값으로 그 값이 얼마나 큰지 상관이 없이 동일한 해시 코드를 만들어 준다. 점(.) 하나만 추가되더라도 전혀 다른 해시 코드값이 나온다.  

 

해시 함수는 문자열 같은 키 값을 정수로 변환하는 과정이 핵심이다.

이 정수 값(해시 값)을 배열의 인덱스로 사용함으로써 데이터를 빠르게 저장하고 검색할 수 있게 된다.

이 과정이 없으면 문자열이나 객체를 배열에 직접 저장할 방법이 없기 때문에, 정수 변환은 필수적인 과정이 되는 것이다. 

 

 

해시 테이블의 성능

 

 

해시 테이블의 성능은 데이터의 삽입, 검색, 삭제가 얼마나 빠르게 이루어지는지에 따라 평가된다.

평균적으로 해시 테이블의 시간복잡도는 O(1)이다.

우리가 찾고자 하는 값(key)이 이미 배열의 인덱스로 있기 때문에

인덱스를 찾기만 하면 바로 원하는 데이터를 가져올 수 있기 때문이다.

 

하지만 이러한 해시 테이블도 충돌이나 부하율(load factor) 등에 따라 성능이 달라질 수 있다. 

😱 최악의 경우 (Worst Case)
-  삽입, 검색, 삭제 시간복잡도 : O(n)
최악의 경우는 모든 키가 같은 해시 값을 가져서 충돌(collision)이 발생할 때이다. 이 경우 해시 테이블은 리스트나 트리와 비슷한 성능을 보여서 O(n)의 시간 복잡도를 가질 수 있다. 

 

 

 

해시 충돌은 무엇인가? 🥊

 

두 개의 다른 key가 동일한 hash 값을 갖는 경우 "충돌이 발생했다"라고 말한다. 해시 테이블은 해시 함수를 사용해 데이터를 저장할 인덱스를 계산하는데, 해시 함수의 설계에 따라 두 개 이상의 키가 같은 인덱스로 매핑될 수 있다. 이때 발생하는 것이 충돌(collision)이다. 따라서 충돌을 피하는 방법은 충돌이 적은 좋은 해시 함수를 사용하는 것이다. 

 

물론 충돌이 발생하더라도 해시 테이블은 데이터를 올바르게 저장하고 검색할 수 있도록 여러 충돌 해결 전략을 사용한다. 

 

 

체이닝(Chaining)

  • 같은 해시 값을 가지는 항목들을 연결 리스트(Linked List)나 트리 형태로 저장한다. 
  • 충돌이 발생하면 해당 인덱스에 여러 개의 항목을 연결한다. 
  • 모든 항목이 하나의 리스트에 저장될 때 성능이 O(n)까지 떨어질 수 있다.
해시 테이블 (크기 5):
Index 0: (apple, 1) -> (orange, 2)
Index 1: (banana, 3)

 

 

개방 주소법(Open Addressing)

  • 충돌이 발생하면 다른 빈 슬롯을 찾아 데이터를 저장한다. 
  • 탐색 알고리즘에 따라 빈 공간을 찾는 방식이 달라진다. (선형탐사, 이차탐사, 이중해싱 등)
  • 모든 데이터가 동일한 배열에 저장되므로 메모리 사용량이 절감된다. 
  • 부하율이 높아지면 성능이 급격히 떨어진다. 
  • 충돌 시 빈 슬롯을 찾기 위해 여러 번의 탐색이 필요하다. 

 

질문으로 정리하기

 

1. 해시 테이블의 시간 복잡도는?

 

  • 평균 시간 복잡도:
    • 삽입(Insertion): O(1)
    • 검색(Search): O(1)
    • 삭제(Deletion): O(1)
  • 최악의 경우 시간 복잡도: O(n) (충돌이 많이 발생할 때)
  • 부하율(Load Factor)에 따른 성능 영향

2. 해시 충돌(Hash Collision)이란 무엇이며, 어떻게 해결하나?

 

  • 해시 충돌: 서로 다른 키가 동일한 해시 값을 가질 때 발생
  • 충돌 해결 기법:
    • 체이닝(Chaining): 각 해시 값에 연결 리스트나 트리를 연결
    • 개방 주소법(Open Addressing): 빈 슬롯을 찾는 방법
      • 선형 탐사(Linear Probing)
      • 이차 탐사(Quadratic Probing)
      • 이중 해싱(Double Hashing)

3. Load Factor란 무엇이며 왜 중요한가?

 

 

 

  • 부하율(Load Factor) = 저장된 항목 수 / 해시 테이블 크기
  • 부하율이 높으면 충돌이 늘어나고 성능 저하
  • 보통 부하율이 0.75를 넘으면 테이블을 리사이즈(Resize)
  • 리사이즈 시 복잡도: O(n)

4. 파이썬의 딕셔너리와 자바의 해시맵의 차이는?

 

  • 파이썬 dict: 체이닝 방식 사용, 삽입 순서 유지 (Python 3.7+)
  • 자바의 HashMap: 개방 주소법 사용, null 키와 값 허용
  • 자바의 Hashtable: 스레드 안전(Thread-safe)하나 성능이 느림
  • 자바의 ConcurrentHashMap: 멀티스레드 환경 최적화

 

자바에서 HashTable과 HashMap의 차이는 동기화 여부이다. 해시테이블은 기본적으로 동기화되어 있어, 여러 스레드가 동시에 접근할 때 안전하다. 그러나 이로 인해 성능이 저하될 수 있다. 반면, 해시맵은 동기화되지 않아 멀티스레드 환경에서 직접적인 접근이 이루어지면 데이터 무결성 문제가 발생할 수 있으나 성능적으로 우수하다. 

 

5. 어떤 경우에 해시 테이블을 사용하지 않는 것이 좋을까?

 

  • 정렬된 데이터가 필요할 때 (해시 테이블은 정렬을 지원하지 않음)
  • 데이터 양이 크고 해시 함수 계산 비용이 높을 때
  • 메모리가 제한적인 환경 (해시 테이블은 리사이즈와 빈 공간을 유지해야 함)
  • 충돌 가능성이 높은 경우 (부적절한 해시 함수 사용 시)

6. 해시 테이블의 응용 예시

 

  • 캐시(Cache) 구현 (웹 브라우저, 메모리 캐시 등) : URL을 키로 사용하고 페이지 내용을 값으로 저장하여 빠르게 검색할 수 있도록 도와준다.
  • 중복 데이터 탐지 (예: 문자열이나 배열의 중복 원소 탐지)
  • 데이터베이스 인덱스 (빠른 검색을 위한 인덱싱)
  • 패턴 매칭 알고리즘 (Rabin-Karp 알고리즘 등)
  • 집합(Set) 연산 (집합 연산 최적화) : 두 집합의 교집합을 구할 때, 하나의 집합을 해시테이블에 저장하고 두 번째 집합의 원소를 순회하면서 해시테이블에 존재하는지 확인