누구나 자료구조와 알고리즘 - (7) 해시 테이블

 

 

 

 

 

 

대부분의 프로그래밍 언어는 해시 테이블이라는 자료 구조를 포함하는데 빠른 읽기라는 엄청난 능력이 있다.

해시 테이블은 쌍으로 이뤄진 값들의 리스트로 키를 사용하여 값을 찾는다.

• 해시 테이블은 프로그래밍 언어에서 서로 다른 이름으로 불린다. 해시, 맵, 해시 맵, 딕셔너리, 연관 배열 등이다.
• 딱 한 단계만 걸리므로 평균적으로 효율성이 O(1)이다.
• 룩업 시 단방향(one-directional)이다.
• 해시 함수를 만드는 대표적인 방법으로는 나누기, 곱하기가 있다.

 

---

 

 

1.1. 곱하기 시의 문제

곱하기 시 만약 키 값이 동일할 경우 문제가 생긴다. 알파벳 순서대로 숫자로 변환하여 해싱하고(A는 1, B는 2..) 문자열을 특정 숫자로 변환한다고 쳤을 때, BAD는 2 x 1 x 4로 8이라는 키 값을 가진다. 하지만 DAB도 8이라는 동일한 키를 가질 수 있고 이런 현상을 충돌이라고 부른다.

 

이를 해결하는 고전적인 방법 중에 "분리 연결법(separate chaining)"이 있다.

각 셀에 하나의 값을 넣는 대신 '배열로서의 참조'를 넣는 방법이다.

 

예를 들어 key에 대해 동음이의어를 넣을 때 dab에 해당하는 8에는 이미 값이 들어있는 상태이다.

6 key: cab value: taxi

8 key: bad value: evil

 

8에 배열로 추가한다.

6 key: cab value: taxi

8 [     { key: bad     value: evil },     { key: dab     value: pat } ]

 

 

 

 

1.2. 효율적인 해시 테이블 만들기

해시 테이블은 다음 3가지 요인에 따라 효율성이 정해진다. 좋은 해시 테이블은 많은 메모리를 낭비하지 않으면서 균형을 유지하며 충돌을 피한다.

• 해시 테이블에 얼마나 많은 데이터를 저장하는가
• 해시 테이블에서 얼마나 많은 셀을 쓸 수 있는가
• 어떤 해시 함수를 사용하는가

 

 

 

 

1.3. 해시 테이블로 속도 올리기

예를 들어 어떤 배열이 다른 배열의 부분 집합인지 알아내야 한다고 치자.

배열 1 - ['a', 'b', 'c', 'd', 'e']

배열 2 - ['a', 'c']

 

중첩 루프를 사용하여 모든 배열을 순회하는 방법이 있을 것이다.

이는 첫번째 배열의 항목 수에 두번째 배열의 항목 수를 곱한만큼 실행하므로 O(N X M)이다.

 

해시테이블을 이용하는 방법으로 변경해보자.

가장 많은 값이 있는 배열을 해시테이블에 저장하고 다른 배열의 수 만큼만 해시테이블을 순회하므로 O(N)이 된다.

 

 

 

---

출처

제이 웹그로우, 누구나 자료구조와 알고리즘 (길벗, 2021)

 

 

 

 

---

개인적으로 공부한 내용을 정리하는 블로그로
잘못된 개념을 게시하지않도록 주의하고 있으나 오류가 있을 수 있습니다.