[TIL] 05/18 항해99 10일차 - 해시 테이블, 문제풀이

 

들어가며

해시 테이블은 개념이 연결리스트에 비해 크게 어렵지는 않았지만 여전히 코드 구현은 몇시간이고 붙잡고 있어도 해결이 안된다.

오늘 구현이 안됐던 이유는 문제 접근부터가 잘못되었어서였던거 같아서

 

오늘의 TIL은 문제를 풀면서 고민했던 것과 해시 테이블의 개념정리를 해보고자한다!

---

해시테이블

해시 테이블이란?

키에 값을 매핑할 수 있는 구조인, 연관 배열 추상 자료형(ADT)를 구현하는 자료구조이다.

‘키와 값을 매핑한다’ 비슷한게 생각이 난다. 바로 딕셔너리(dictionary)이다. (자바에서는 map, 자바스크립트에서는 object 등등)

 

해시 테이블을 사용하는 이유는 뭘까?

간단하게 레스토랑의 메뉴를 배열과 비교하여 예시로 생각해보자.

메뉴판에는 각 메뉴와 그 메뉴의 가격이 적혀있다. 이걸 배열로 나타내면 다음과 같이 나타낼 수 있을 것이다

menu = [
	{"name": "알리오올리오", "price": 12000},
	{"name": "고르곤졸라피자", "price": 21000},
	{"name": "스테이크", "price": 34000},
	{"name": "음료", "price": 5000},
]

 

이 메뉴에서 ‘스테이크'를 찾고 싶다면 앞에서부터 순서대로 찾아봐야한다.

이건 너무 시간이 오래걸리고 비효율적이다. 음식하나를 찾으려고 처음부터 끝까지 하나하나 메뉴를 읽어보는 사람은 많지 않을 것이다.

만약 이 메뉴를 해시 테이블로 나타내면 어떻게 생겼을까?

 

menu = {
	"알리오올리오": 12000,
	"고르곤졸라피자": 21000,
	"스테이크": 34000,
	"음료": 5000
}

 

훨씬 찾기가 쉬워졌다. 만약 ‘알리오올리오'의 가격을 알고싶다면 메뉴에서 ‘알리오올리오'만 찾으면 된다.

여기서 내가 찾으려는 key는 ‘알리오올리오'이고, 해시 테이블은 ‘12000’이라는 가격을 value로 제공해준다.

따라서, 배열과 해시 테이블의 시간복잡도를 비교하면 다음과 같다.

 

배열의 시간복잡도 O(n) / 해시 테이블의 시간복잡도 O(1)

 

배열의 시간 복잡도는 O(n)인 반면 해시테이블은 O(1) 즉, 상수시간으로 나타나고있다. 해시테이블은 어떤 값을 찾더라도 소요되는건 딱 1개의 스텝만이 필요하다.

 

이렇게 해시 테이블에 대해 이해를 했다. 그럼 이제 해시 테이블이 어떻게 작동하는 지 알아보자.

 

해시 테이블은 key의 해시값과 value를 매핑해서 저장하게 된다. 여기서 이 해시값은 해시 함수(Hash Function)를 적용하여 나온 고정된 길이의 값을 말한다.

 

 

해시 함수

위에서 말한 것처럼 해시 함수는 해시값을 만들어주는 녀석이다. 조금 더 자세하게 말하자면, 임의의 길이를 갖는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 함수를 말한다.

 

대표적인 해시함수는 나눗셈을 이용하는 모듈러 방식이다. 나눗셈의 나머지 값을 이용하는 방식으로, 테이블의 크기를 소수로 정하고 2의 제곱수와 최대한 먼 값을 사용해야 효과가 좋다고 알려져있다. 

그 외에도 여러가지 해시 함수가 있겠지만 사실 우리가 이걸 직접 구현할 일은 개발하면서 크게 많지 않을 것 같다. 세상에 많은 똑똑한 개발자님들이 구현해놓은 해시함수를 구글링해서 사용하자.

 

 

해시값이 충돌하는 경우

해시 테이블이 속도가 빠르기 때문에 좋은건 분명하지만 완벽한건 아니다.

만약에 책장에서 python이라는 key를 해시 함수에 돌려서 나온 값과 java라는 key를 해시 함수에 돌려서 나온 값이 같다면?

더 실감 나는 예시로는 비밀번호를 해시 함수에 돌려서 DB에 저장했는데 또 다른 비밀번호를 해시 함수에 돌려서 나온 값이 서로 같다면?

 

왜 충돌이 나서 날 괴롭게 하는거야...

 

충돌이 나면 해결해야지. 이런 충돌이 났을 때 어떤 식으로 처리하게 되는지 알아보자

 

개별 체이닝 (Separate Chaining)

출처 https://www.onlybook.co.kr/entry/algorithm-interview

개별 체이닝은 그림처럼 충돌 발생 시, 해당 해시값과 매핑되는 value를 연결 리스트로 연결하는 방식이다. 기본적인 자료구조와 임의로 정한 간단한 알고리즘만 있으면 구현할 수 있어서 이 방식은 인기가 높다고 한다.

 

다만, 한 해시값에 연결 리스트를 매핑하기 때문에 추가적으로 메모리 할당이 필요한데, 추가로 메모리를 할당하는 작업은 상대적으로 느리기 때문에 성능면에서는 오픈 어드레싱 방식이 보다 유용하다. 

 

개별 체이닝 방식으로 해시 테이블 구현하기

[leetcode] 706. 해시맵 디자인 (Design HashMap)

[leetcode] 706. 해시맵 디자인 (Design HashMap)

 

오픈 어드레싱

출처 https://www.onlybook.co.kr/entry/algorithm-interview

 

오픈 어드레싱은 충돌이 발생했을 때, 값이 저장되지 않은 빈 공간을 찾아서 그 곳에 저장하는 방식이다. 가장 간단하게는 선형 탐사(Linear Probing) 방식을 사용해서 충돌이 발생했을 때 해당 위치부터 순차적으로 탐사를 하나씩 진행한다. 탐사를 진행하다가 비어있는 공간을 발견하면 저장을 하게 된다. 선형 탐사 방식은 구현 방법도 쉽고 의외로 성능도 좋은 편이라고 한다.

 

개별 체이닝과 구별되는 차이점은, 공간의 제약없이 무한정 확장할 수 있는 것과 반대로 오픈 어드레싱은 빈 공간에 데이터를 끼워넣는 방식이기 때문에 할당된 크기 이상은 저장할 수 가 없다. 

 

즉, 확장성이 좋은 건 개별 체이닝이고, 성능이 비교적 좋은건 오픈 어드레싱이다!

 

 

문제 풀이

[leetcode] 29. 보석과 돌 (Jewels-and-stones)

[leetcode] 29. 보석과 돌 (Jewels-and-stones)

 

[leetcode] 3. 중복 문자 없는 가장 긴 부분 문자열 (Longest Substring WIthout Repeating Characters)

[leetcode] 3. 중복 문자 없는 가장 긴 부분 문자열 (Longest Substring WIthout Repeating Characters)

 

---

마치며

어제랑 엊그제 발표준비를 하느라 과제 중 거의 절반은 풀지도 정리하지도 못했다. 거의 밥먹고 씻는 시간 빼고 노트북 앞에 앉아있는데... 시간 활용을 더더 효율적으로 하도록 노력해서 최대한 나온 문제 정리 정도는 다 할 수 있게 해야겠다.

 

---

참고

개발자라면 꼭 알아야할 Hash Table 의 모든 것!

<파이썬 알고리즘 인터뷰>