Computer Science/Algorithm

[책] 누구나 자료구조와 알고리즘 - 8장 해시 테이블로 매우 빠른 룩업

지안22 2023. 11. 27. 15:33

 

 

누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고

누구나 자료 구조와 알고리즘 |

product.kyobobook.co.kr

배열에서 특정 요소를 검색할 때, 정렬된 배열이면 O(logN), 정렬되지 않은 배열이면 O(N) 단계가 걸린다.

이 때, 해시 테이블을 사용하면 O(1) 만에 데이터를 룩업할 수 있다.

 

해시 테이블

해시 테이블은 쌍(key, value)으로 이뤄진 값들의 리스트이다.

해시 , 맵, 해시 맵, 딕셔너리, 연관 배열 등의 이름을 갖는다.

 

해시 함수를 이용하여 key를 해싱한다.

이 해싱 된 key의 값이 value가 저장될 위치를 결정한다.

 

때문에 key로 검색 시, O(1)의 성능을 가진다.

value로 검색 시에는 일반 배열과 동일하게 O(N)의 성능을 가진다.

 

언어에 따라 다르지만, 어떤 언어는 value 옆에 key를 저장해 충돌 시에 유용하게 사용될 수 있도록 한다.

 

해시 충돌

key가 해싱되면 항상 동일한 해시 값을 가진다.

때문에 key로 검색 시, O(1)의 성능을 가질 수 있다.

하지만 다른 key여도 동일한 해시 값을 가지게 될 수 있다.

예시) 해시 함수
각각의 알파벳은 a, b, c, d, e = 1, 2, 3, 4, 5 의 값을 가진다.
parameter로 문자열이 들어왔을 때, 문자열의 알파벳을 모두 더한 수가 return 된다.

예시 상황)
해시 함수(abe) = 8
해시 함수(ce) = 8

문자열 abe와 ce는 같은 해시값을 가지게 되어 충돌이 일어나게 된다.

 

이 때, 충돌을 해결하는 고전적이 방법 하나가 분리 연결법(separate chaining) 이다.

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

key로 검색 시에 처음에는 O(1)로 찾지만, 내부적으로 배열이 들어 있어서 이 경우에는 사실상 O(N)의 복잡도를 가지게 된다.

때문에 해시 테이블에 충돌이 거의 없으며, O(N)이 아닌 O(1) 시간 내에 일반적으로 룩업을 수행하도록 디자인 해야한다.

 

효율적인 해시 테이블

효율적인 해시 테이블은 다음과 같은 세 요인에 따라 결정된다.

1. 해시 테이블에 얼마나 많은 데이터를 저장하는가 (저장할 수 있는 데이터의 양 ⬆️)

2. 해시 테이블에 얼마나 많은 셀을 쓸 수 있는가 (충돌 위험성 ⬇️, 경우의 수 ⬆️(중복이 나올 수 없도록 범위⬆️))

3. 어떤 해시 함수를 사용하는가(충돌 위험성 ⬇️, 해싱 시 중복이 나오지 않도록 함수 설계)

 

좋은 해시 함수란 사용 가능한 모든 셀에 데이터를 분산시키는 함수이다.

(특정 셀에만 몰리면 충돌 위험성 ⬆️, 검색 성능 ⬇️, 비어있는 셀 만큼 메모리 낭비)

 

좋은 해시 테이블은 많은 메모리를 낭비하지 않으면서(ex. 7개만 저장하는데 셀 1000개를 생성할 필요X) 균형을 유지하며 충돌을 피한다.

데이터와 셀 간 이러한 비율을 부하율(load factor)이라 부른다. (= 원소 개수 / 셀 개수)

 

해시 테이블 내부는 대부분 사용자가 쓰고 있는 컴퓨터 언어가 관리한다.

(해시 테이블의 크기, 해시 함수의 종류, 언제 해시 테이블을 확장할지 결정)

Java8에서는 해시 충돌이 일어났을 때, 6개까지는 링크드 리스트, 8개부터는 Red-Black-Tree로 자료구조를 바꿔 사용한다고 한다.
또한 해시 테이블 생성 시 기본(버킷) 크기 = 16bit,
해시 함수의 종류: MD5, SHA 계열
확장 시점은 부하율 0.75시 현재 버킷의 2배로 확장,
이후의 버전에서는 어떻게 해시 충돌을 해결하는지는 더 알아봐야 할 것 같다.

참고한 블로그: https://ash84.io/2012/11/26/java-hashmap-ec-97-90--eb-8c-80-ed-95-9c--ec-a0-95-eb-a6-ac/

 

해시 테이블로 속도 올리기

해시 테이블은 쌍으로 된 데이터에 적합하게 쓰이지만, 쌍이 아닌 데이터라도 코드를 빠르게 만들 때 쓰일 수 있다.

해당 요소가 배열에 들어있는지 확인 할 때, 배열이라면 O(N)의 시간 복잡도를 가진다.

해시 테이블을 이용하면 O(1)의 시간 복잡도를 가지도록 성능을 개선 할 수 있다.

 

해시 테이블로 사용할 때는 value에 true를 넣어서 판별할 수 있다.

hashTable = {a: true, b:true} 일 때,
파이썬의 경우 hashTable[c] 호출 시 false를 반환한다. (언어에 따라 다르다)

 

 hashTable에 키로 존재하는지 확인하도록 활용하여 사용할 수 있다.

 

마무리

지금까지는 효율성과 속도를 중심으로 자료구조를 분석했다.

9장에서는 속도 외의 장점인 코드의 간결성, 유지보수성을 향상시킬 수 있는 스택과 큐를 알아 볼 예정이다.