📌 해시 테이블(Hash Table)이란?

해시 테이블(Hash Table)은 키(Key)와 값(Value)을 저장하는 자료구조 중 하나로, 키를 값에 대응시키는 해시 함수(Hash Function)를 통해 키를 고유한 인덱스로 변환하여 배열에 값을 저장합니다.

해시 함수 (Hash Function)

해시 함수는 데이터를 고유한 값으로 매핑하는 함수로, 해시 테이블에서 데이터를 빠르게 찾기 위해 사용됩니다.

• 나눗셈(Division)

  • 간단하게 키를 테이블 크기로 나눈 나머지를 해시 값으로 사용하는 방법입니다.
  • hash(key) = key % table_size

• 곱셈(Multiplication)

  • 키에 상수 A를 곱하고, 소수인 테이블 크기를 곱한 후 소수 부분을 취하는 방법입니다.
  • hash(key) = floor(table_size (key A % 1))

• 자리값 합(Additive)

  • 키를 문자열로 간주하여 각 문자의 ASCII 값을 더하는 방식입니다.
  • hash(key) = Σ(characters in key) ASCII_value

• SHA-256 등의 암호학적 해시 함수

  • 안전한 보안 목적으로 사용되는 해시 함수 중 하나입니다.
  • 예) SHA-256은 256비트 길이의 해시 값을 생성합니다.

배열(bucket)

배열은 해시 테이블의 기본 구조를 이루는 요소로, 데이터를 저장하는 단위입니다. 해시 테이블의 각 버킷은 해시 함수에 의해 생성된 해시 값에 해당하는 위치에 존재하며, 이 위치는 배열의 인덱스로 표현됩니다.

• 해시 값에 대한 인덱스

  • 해시 함수는 키를 해시 값으로 변환하고, 이 값은 배열의 인덱스로 사용된다.

• 배열의 크기

  • 해시 테이블의 크기를 나타내며, 배열의 각 인덱스는 버킷을 나타낸다.

• 연결 리스트 또는 값의 저장

  • 한 버킷에 여러 키-값 쌍이 충돌로 인해 저장될 수 있고, 이는 연결 리스트로 처리되거나 다른 충돌 해결 방법을 사용한다.

• 순회 및 검색

  • 각 인덱스는 고유한 해시 값에 대응하며, 이를 통해 데이터를 빠르게 검색할 수 있다.

• 메모리 공간

  • 배열은 연속된 메모리 공간에 저장되어 빠른 접근이 가능하다.
  • 충돌이 발생하면 추가 메모리가 사용될 수 있다.

충돌(Collision) 처리

서로 다른 키가 같은 해시 값으로 매핑될 수 있는데, 이를 충돌이라고 합니다.

충돌 해결 방법 2가지

1. 체이닝(Chaining)
2. 개방주소방식(Open Addressing)

체이닝(Chaining)

충돌이 발생하면 같은 해시 값에 속하는 모든 키를 연결 리스트로 연결하는 방식입니다.
각 버킷은 연결 리스트로 이루어지며, 충돌이 발생하면 해당 버킷의 연결 리스트에 새로운 항목을 추가합니다.

• 장점: 각 버킷은 독립적인 연결 리스트로 구성되어, 여러 키-값 쌍을 하나의 버킷에 저장할 수 있습니다.

• 단점: 연결 리스트가 길어질 경우 성능 저하가 발생할 수 있으며, 메모리를 추가로 사용하는 부분이 있습니다.

개방주소방식(Open Addressing)

충돌이 발생하면 다른 빈 버킷을 찾아서 데이터를 저장하는 방식입니다.
선형 조사(Linear Probing), 이차 조사(Quadratic Probing), 랜덤 조사(Random Probing) 등이 있습니다.

• 장점: 메모리를 효율적으로 사용하며, 연속된 메모리에 데이터를 저장하므로 캐시 효율이 높아집니다.

• 단점: 클러스터링(Clustering)이 발생하여 일부 영역에 데이터가 집중될 수 있습니다.

해시테이블(HashTable) vs 해시맵(HashMap)

해시테이블(HashTable)

• 동기화된 구조를 나타낸다.
• 동기화로 인해 멀티스레드 환경에서 안전하게 사용 가능하다.
• 성능 면에서는 최적화가 되어 있지만, 일부 언어에서는 제한적일 수 있다.
• 주로 안전한 멀티스레드 환경에서 사용할 때 추천된다.

해시맵(HashMap)

• 동기화를 가정하지 않는다.
• 동기화를 사용자가 직접 처리해야 하며, 단일 스레드 환경이나 명시적인 동기화를 필요로 하는 상황에서 사용된다.
• 성능 및 메모리 사용 면에서 최적화되어 있어 일반적으로 빠르고 효율적이다.
• 모던 싱글 스레드 또는 사용자가 동기화를 명시적으로 처리할 수 있는 상황에서 추천된다.