Study

해시 테이블 & 트리

onetaek 2025. 6. 3. 14:18

해시테이블

해시 테이블

키-값으로 이루어진 자료구조.

버킷에 키를 통해 얻으려는 값이 저장된다.

해시 테이블에 값이 저장되는 과정

  1. 키 ="Hanbit"
  2. hashCode("Hanbit") = 8000002;
  3. index = 8000002 % 8 = 2
  4. table[2] = {"Hanbit", "010-1234"}

해시 함수

임의의 고정된 길이의 데이터를 고정된 길이의 데이터로 반환하는 단방향 함수.

단방향이기 때문에 변환된 데이터를 가지고 원래 데이터를 추적하기 어렵다.

해시 충돌

해시값은 임의의 키 값을 고정된 크기의 해시값으로 만들기 때문에 가능성은 낮지만 두 개의 다른 키 값이 같은 해시값을 생성할 수 있다.

'abc' -> 해시 함수 -> 'gotlrkqt'
'cba' -> 해시 함수 -> 'gotlrkqt' 

이럴 경우에 해시 충돌이 일어나고 해시 충돌이라고 했을 때 우리가 쉽게 생각할 수 있는 상황이다.

하지만 한 가지 경우의 해시 충돌이 더 존재하는데 이것을 학습하기 위해서 먼저 해시 테이블에 값이 어떻게 저장되는지 알아야한다.

해시 테이블에 값을 저장할 때는 키를 해시함수를 통해 해시값으로 변환한다. 이렇게 나온 해시 값을 모듈러 연산을 통해 배열에 값이 저장될 주소를 정한다. 이 때 배열의 크기에 들어갈 수 있도록 연산을 해준다. 여기서 동일한 주소 값이 나올 수 있다.

'qwer' -> 해시함수 -> 'abc' -> 모듈러 연산 -> 'wnth'
'asdf' -> 해시 함수 -> 'def' -> 모듈러 연산 -> 'wnth'

해시 충돌 해결 방법

체이닝

체이닝은 충돌이 발생한 데이터를 연결리스트로 묶는 것이다. 그림을 보면 3번 주소에 여러 개의 노드가 연결되어 있다.

3번 주소에 30 이라는 데이터가 추가되어야 한다면 55 뒤에 연결리스트로 이어주면 된다.

𝐐. 그럼 검색할 때는 어떻게 할까?

실제로 버킷에 데이터가 저장될 때는 아래와 같이 데이터가 저장된다. 키 값을 "banana" 해서 검색하면 6번 주소가 나오고 6번주소에서 키 값이 "banana"인 데이터를 찾아서 value 값을 반환한다.

table[6] = LinkedList.of(
  new Entry("apple", "사과 값"),
  new Entry("banana", "바나나 값")
);

이런 구조 때문에 만약 최악의 경우에 모든 데이터가 6번 주소에 저장되면 일반 배열과 똑같아지는 단점을 가지고 있다.

개방 주소법

개방 주소법은 충돌한 버킷의 인덱스가 아닌 다른 인덱스에 데이터를 저장하는 방식이다. 

다른 인덱스를 찾는 방법은 선형 조사법과 이차 조사법이 있다.

 

선형 조사법

충돌이 난 인덱스의 다음부터 순차적으로 데이터를 넣을 수 있는 주소를 찾는 것. 하지만 이 방법을 사용하면 6번에서 충돌이 일어났을 때 7번에 저장되고 실제 7번에 저장되어야 할 데이터가 들어오면 또 충돌이 나기 때문에 한번 충돌이 일어난 인덱스 근처에서 계속해서 충돌이 일어난다는 단점이 있다. 이러한 현상을 데이터 군집화 라고 한다.

 

이차 조사법

충돌이 발생했을 때 충돌이 발생한 인덱스에서 제곱수만큼 떨어진 거리에 위치한 인덱스를 찾는 방법이다.

6번에서 충돌이 일어나면 7(6 + 1)번을 찾고 7번에 들어가지 못하면 10(6 + 2^2)번, 다음으로는 15(6 + 3^2)번을 찾아가는 방법이다.

하지만 이것도 근본적인 해결책은 아니다.

이중 해싱

두 개 이상의 해싱을 사용하는 방식이다.

보조 해시 함수(g함수)를 지정해두고 기존 해시 함수(f함수)에서 충돌이 발생하면 보조 해시 함수를 사용한다.

f(key)에서 충돌 -> f(key) + g(key) -> f(key) + g2(key) 와 같은 방식으로 주소를 찾는다.

이 방식은 군집화를 해결할 수 있다.

트리

이진 탐색 트리

특정 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값을 지닌 노드들이 있고, 오른쪽 서브트리에는 해당 노드보다 큰 값을 지닌 노드들이 있는 구조의 이진 트리를 의미한다.

쉽게 말해, 특정 노드의 왼쪽에는 해당 노드보다 작은 값, 오른쪽에는 해당 노드보다 큰 값이 있는 트리가 이진 탐색 트리이다.

이진 탐색 트리를 활용하면 o (log n)으로 원하는 값을 탐색할 수 있다는 장점이 있다.

힙

탐색에 특화된 트리.

완전 이진 트리의 종류 중 하나인 힙은 주로 최댓값과 최솟값을 빠르게 찾기 위해 사용된다. 이진 탐색 트리와 유사하게 일반적으로 탐색에

O (log n)의 시간 복잡도가 소요된다.

Red Black Tree

이진 트리의 문제점은 트리가 한쪽으로만 치우쳐질 가능성이 있다는 것이다. 한쪽으로 편향된 트리는 리스트와 차이점이 없어지고 결국 트리를 사용하는 장점이 없어지게 된다.

이 문제를 해결하기 위해서 루트 노드를 기준으로 왼쪽 서브 트리와 오른쪽 서브트리의 높이의 균형을 맞추도록 하는 것이 자가 균형 이진 탐색 트리이고, 이 트리 중 대표적인 것이 레드 블랙 트리이다.

 

레드 블랙 트리에는 5가지 규칙이 있다.

  • 노드는 레드(Red) 또는 블랙(Black) 중 하나의 색을 가진다.
  • 루트 노드는 항상 블랙이다.
  • 모든 리프(Leaf) 노드 (NIL 노드)는 블랙이다.
  • 레드 노드의 자식은 모두 블랙이다. (즉, 레드 노드는 연속으로 나타날 수 없다.)
  • 어떤 노드로부터 그 노드의 후손 리프 노드까지의 모든 경로에는 동일한 수의 블랙 노드가 존재한다.

레드 블랙 트리의 장점: 검색, 삽입, 삭제가 모두 O(log n)의 시간복잡도를 보장한다.

B-Tree

B-Tree도 균형을 유지하는 트리이다. 레드 블랙 트리와 다른 점은 레드 블랙 트리는 이진 탐색 트리 였다면 B-Tree는 다진 탐색 트리 라는 것이다.

M차 B-Tree는 최대 자식 개수가 M개인 B-Tree이다. M차 B-Tree가 가질 수 있는 최소 자식 노드는 [M/2]개이다.

 

B-Tree의 장점: 하나의 노드에 저장할 수 있는 데이터의 양이 많다. (5차 B-Tree라면 key값 4개, 자식 5개를 하나의 노드에 저장 가능.)

 

이런 장점 때문에 B 트리는 파일 시스템, 데이터베이스와 같이 대량의 데이터를 기반으로 탐색, 접근, 저장을 수행할 때 활용된다. 파일 시스템, 데이터베이스와 같은 프로그램을 실행할 때는 입출력 연산 횟수를 최소화하는 것이 좋다. 입출력 연산은 일반적으로 메모리 접근에 비해 수행 속도가 느리기 때문이다.

운영 체제는 블록 단위로 데이터를 읽는데 한 블록은 여러 데이터를 포함할 수 있다. 이진 탐색 트리는 하나의 노드에 하나의 데이터만 저장되기 때문에 입출력이 많이 필요하다. 그렇기 때문에 하나의 노드에 많은 정보가 있는 B-Tree가 성능이 좋다.

𝐐. 하나의 블록에 하나의 노드만 저장할 수 있나? 그게 아니라면 이진 탐색 트리를 사용하면서 하나의 블록에 여러개의 노드를 저장하면 되는거 아닌가?

하나의 블록에 여러개의 노드를 저장할 수 있다. B-Tree를 사용하면 하나의 블록에 하나의 노드가 저장된다.

B-트리 설계의 핵심은 '하나의 B-트리 노드'의 크기를 '운영체제의 디스크 블록 크기'에 맞추거나 그 배수로 설정한다는 점이다.

 

이진 탐색 트리를 사용하면서 하나의 블록에 여러개의 노드를 저장할 수 있지만 B-Tree 만큼 효율적이지 않다.

𝐐. 데이터베이스에서 B-Tree를 주로 사용하는데 데이터베이스에서 내 운영체제의 블록 크기를 어떻게 아는걸까

수동으로 설정할 수 있고, 설정하지 않으면 기본값이 사용된다. 가장 많이 기본값으로 사용되는 크기는 8KB와 16KB 이다.