해시 테이블 : 빠르게 데이터 검색하기

으베베베

 

자료구조 세번 째 주인공은 해시 테이블 입니다. ~~

 

지난 시간에는 '링크드 리스트'에 대해서 알아보았지요. 

링크드 리스트 : 메모리 알뜰하게 사용하기

동적 배열을 사용하기 위해서는 '연속된 메모리 블록'이 필요하다는 제약'을 

링크드 리스트는 각 노드가 다음 노드를 가리키는 포인터를 사용함으로써 해결했어요. 

 

그렇다면 오늘 주인공 '해시 테이블'은 뭐 때문에 필요하게 되었는지 살펴봅시다. 

레츠 기딧 ~~~

 

배열과 링크드 리스트의 한계

배열과 링크드 리스트는 각각의 장점을 가지고 있지만, 공통적으로 갖고 있는 한계가 있어요.

 

뭘까영?

 

바로 "데이터 검색이 효율적이지 않다"는 것입니다. 

 

배열과 링크드 리스트는 데이터 구조 특성상 '선형 검색'을 할 수 밖에 없어요. 

선형 검색이란 쉽게 말해서

 박스를 하나씩 차례대로 열어보면서 원하는 값이 있는지 없는 지 확인하는 방법을 말해요. 

 

데이터 구조별로 정리해보면 아래와 같아요. 

 

배열의 검색 성능 

• 정렬된 배열 : 이진 검색을 사용해서 O(log n) 시간에 검색이 가능해요. 
• 정렬되지 않은 배열 : 모든 요소를 순회해야하므로 O(n)시간이 걸려요. 

링크드 리스트의 검색 성능 

• 첫 노드부터 하니씩 순회해야 하므로 항상 O(n) 시간이 소요되요. 
• 중간 삽입 / 삭제는 빠르지만, 그 위치를 찾는데 시간이 오래 걸려요. 

 

ID나 이메일을 이용해서 사용자 정보를 조회하는 것 처럼

데이터 검색은 매우 빈번하게 이루어지는 작업이에요. 

따라서 '검색 작업'을 O(1) 상수 시간에 가능하도록 하는 자료구조가 필요해졌어요. 

해시 테이블 등장 

우리가 전화번호부 앱을 만든다고 상상해 볼게요.  

그러면 이 앱은 아래와 같이 이름 그리고 이에 대응하는 전화번호 데이터가 필요하겠죠. 

김철수: 010-1234-5678
이영희: 010-8765-4321
박민수: 010-5555-6666
...

 

 

만약에 배열을 이용해 위의 데이터들을 구조화하면 아래와 같을 거에요. 

names = ["김철수", "이영희", "박민수", ...]
numbers = ["010-1234-5678", "010-8765-4321", "010-5555-6666", ...]

여기서 민수의 전화번호를 찾는다고 하면 

1. 이름 배열의 첫번째 요소부터 차례대로 확인해나가다 세번째 인덱스에서 "박민수"라는 이름을 찾을 거에요. 

2. 그러면 세번째 인덱스에 "박민수"의 전화번호가 있음을 알게 되었으니까 두번째 전화번호 배열의 3번째 인덱스를 조회해서 민수의 전화번호를 찾을 수 있어요. 

 

즉 배열을 사용하게 되면

찾으려는 값이 어디에 위치해 있는지(인덱스 값)를 찾기 위해서는 key 배열을 차례대로 뒤져봐야 돼요. 

 

그렇지만 해시 테이블을 사용하면 

"키"를 "배열의 인덱스로 "로 변환해서 바로 접근할 수 있게 해줘요. 

 

다시 정리해보면 배열을 사용하면 키의 인덱스 값을 찾는데 선형검색이 해야하지만 

해시 테이블을 사용하면 키를 바로 인덱스 값으로 바꿔주기 때문에 키의 인덱스 값을 찾는 절차가 필요없게 되는거죠. 

 

어떻게 중간과정 없이 바로 키의 인덱스 값을 찾을 수 있게 되었을까요?

 

바로 '해시함수' 덕분이에요. 

 

해시함수란?

해시 함수는 임의의 크기를 가진 데이터(예: 문자열, 객체 등)을 고정된 크기 값( 보통 정수)로 변환하는 함수에요. 

결국은 해시함수가 키를 바로 인덱스 값으로 연결(매핑)해주는 역할을 하기 때문에 바로 키에 맞는 값을 검색할 수 있게 되는 것이죠. 

 

 이해를 위해 문자열을 숫자로 변환한다고 해볼께요. 

제일 간단한 방법은 각 문자의 ASCII 값을 더하는 것이에요. 

예를 들어 "CAT"이라는 문자열을 해싱해 보면 

• 'C'의 ASCII 값: 67
• 'A'의 ASCII 값: 65
• 'T'의 ASCII 값: 84
• 합계: 67 + 65 + 84 = 216

그리고 이 합계를 테이블 크기(예: 10)로 나눈 나머지를 사용한다 하면  216 % 10 = 6

 "CAT"은 인덱스 6에 저장되요. 

 

실제 구현은 더 복잡하지만 매커니즘은 위와 같아요. 

 

그렇다면, 다른 키를 넣었는데 같은 값이 나올 수도 있지 않나요?

 

맞아요. 그런 경우를 '해시 충돌'이라고 해요. 

 

해시함수가 아무리 좋아도, 서로 다른 키가 같은 인덱스로 매핑되는 '충돌'은 피할 수가 없어요. 

따라서 기본적으로는 충돌이 많이 발생하지 않도록 해시함수를 설계하는 것이 중요하고요. 

충돌할 경우를 대비해 다음과 같은 방법들도 이용해 볼 수 있어요. 

 

체인닝(Chaining) 

각 배열 요소(버킷)에 링크드 리스트를 사용하여 충돌하는 모든 키-값 쌍을 저장해요.

index 0: → (key1, value1) → null
index 1: → (key2, value2) → (key3, value3) → null
index 2: → null
index 3: → (key4, value4) → null
...

충돌이 발생하면 해당 인덱스의 링크드 리스트에 새 노드를 추가하는 방식이에요. 

 

개방 주소법(Open Addressing)

충돌이 발생하면 비어있는 다음 슬롯을 찾아 저장해요.

index(key) → occupied → index(key)+1 → occupied → index(key)+2 → empty (저장!)

이 방법은 메모리를 더 효율적으로 사용할 수 있지만, 클러스터링(clustering) 문제가 발생할 수 있어요.

 

마지막으로 해시 테이블이 가지는 장점을 정리해 볼께요. 

 

해시 테이블 장점 

 

• 빠른 검색: 평균적으로 O(1) 시간에 데이터 접근 가능 (배열은 O(n), 정렬된 배열은 O(log n), 링크드 리스트는 O(n))
• 효율적인 삽입/삭제: 평균적으로 O(1) 시간 소요 (배열의 중간 삽입/삭제는 O(n), 링크드 리스트는 위치를 찾는 데 O(n))
• 유연한 키: 문자열, 객체 등 다양한 타입을 키로 사용 가능 (배열은 정수 인덱스만 가능)

 

작업	배열 ( 정렬 X )	배열 ( 정렬 O )	링크드 리스트	해시 테이블
검색	O(n)	O(log n)	O(n)	O(1) 평균
삽입	O(n) ( 끝에 삽입시 )	O(n)	O(1) 위치를 알때	O(1) 평균
삭제	O(n)	O(n)	O(1) 위치를 알때	O(1) 평균

 

지금까지 해시 테이블의 개념, 구현 방법, 장단점에 대해 알아보았어요.

해시 테이블은 특히 검색 속도가 중요한 상황에서 배열이나 링크드 리스트의 한계를 뛰어넘는 훌륭한 자료구조예요.

O(1)의 평균 검색 시간은 대규모 데이터를 다루는 현대 애플리케이션에서 매우 중요한 특성이죠.

 

모든 자료구조가 그렇듯이, 해시 테이블도 만능은 아니에요. 사용 사례에 맞게 적절한 자료구조를 선택하는 것이 중요해요.

순서가 중요하거나 메모리가 매우 제한적인 환경에서는 다른 자료구조가 더 적합할 수 있어요.