#8. 해시테이블_누구나 자료구조 와 알고리즘(제이 웬그로우)

bien·2023년 3월 21일
0

8장. 해시 테이블로 매우 빠른 룩업

해시 테이블: 데이터를 O(1)만에 룩업 할 수 있는 특수한 자료 구조

8.1 해시 테이블

해시 테이블(hash table) = 해시, 맵, 해시 맵, 딕셔너리, 연관 배열

  • 쌍으로 이뤄진 값들의 리스트. (키(key), 값(value))
  • 해시 테이블의 값 룩업은 딱 한 단계만 걸림 = 평균적으로 O(1)

8.2 해시 함수로 해싱

해싱(hasing): 문자를 숫자로 변환하는 과정
해시함수(hash function): 글자를 특정 숫자로 변환하는데 사용한 코드
ex) 각 문자에 해당하는 숫자를 가져와 모든 수를 합쳐 변환.
문자에 해당하는 모든 수를 곱해서 변환.
ex) A=1, B=2. C=3, D=4일 때, BAD=2+1+4=7. / BAD=214=8
단, 동일한 문자열을 해시 함수에 적용할 때 동일한 숫자로 변환한다.

8.3 해시 테이블 룩업

컴퓨터는 키를 해싱하여 해당 인덱스에 값을 넣는다.
ex) “bad":”evil“ => 8번 인덱스에 ”evil“값을 넣어둔다.

따라서, 컴퓨터가 키를 이용해 룩업 시 두 단계를 거친다.
1. 룩업하고 있는 키를 해싱한다. BAD=214=8
2. 결과가 8이므로 셀 8을 찾아가서 저장도니 값을 반환한다. 여기서는 문자열 “evil"이다.

단방향(one-directional) 룩업

  • 키를 사용해 값을 찾을 때만 O(1)룩업이 가능하다.
    값을 이용해 연관된 키를 찾을 때, 키를 모를 때는 빠른 룩업 기능을 활용할 수 없다.
    (이 경우 모든 값을 확인해야 하므로 O(N)이 된다.)

8.5 충돌 해결

해시 테이블에는 결함이 있다. 키를 해싱했을 때 동일한 값이 나올 수 있다는 점이다. 이러한 충돌을 다루기 위한 2가지 방법이 있다.

분리 연결법(Separate Chaning, 개별 체이닝)

충돌 발생 시 하나의 값을 넣는 대신 배열로의 참조를 넣는 방법.
ex) index 8에 {“bad":evil", "dab","pat”}이 들어 있고, 키 "dab“의 값을 찾는 경우
1. 컴퓨터는 키를 해싱한다. DAB=412=8,
2. 셀 8을 룩업한다. 컴퓨터는 셀 8이 하나의 값이 아닌 배열들의 배열을 포함하고 있음을 알게된다.
3. 각 하위 배열의 인덱스를 0부터 찾아보며 룩업하고 있는 단어인 (“DAB")을 찾을때까지 배열을 차례대로 검색한다. 일치하는 하위 배열의 인덱스 1에 있는 값을 반환한다.

오픈 어드레싱(Open Addressing)

충돌 발생 시 재해시(rehashing)을 수행하여 비어 있는 버킷을 찾아내는 방법으로, 닫힌 해시법이라고도 한다. 빈 버킷을 만날때까지 재해시를 여러번 반복하므로 선형 탐사법(linear probing)이라고도 한다.
해시 테이블의 각 요소를 버킷이라 한다

각 언어별 해시 테이블의 구현 방식

언어방식
C++개별 체이닝
자바개별 체이닝
고(Go)개별 체이닝
루비오픈 어드레싱
파이썬오픈 어드레싱

최악의 경우, 해시테이블의 룩업에는 O(N)이 요구된다. 해시 테이블의 충돌을 최소화하려면 어떻게 하면 될까?

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

해시 테이블은 다음의 세 가지 요인에 따라 효율성이 결정된다.

  1. 얼마나 많은 데이터를 저장하는가.
  2. 얼마나 많은 셀을 사용할 수 있는가.
  3. 어떤 해시 함수를 사용하는가.

1,2. 데이터의 수 & 사용가능한 셀의 수

한 예시로, 5개의 항목에 1000개의 셀을 할당하는 경우, 충돌 가능성은 낮으나 메모리 낭비가 심하다.
=> 좋은 해시 테이블은 많은 메모리를 낭비하지 않으면서 균형을 유지하며 충돌은 피하는 테이블이다.
=> 데이터와 셀 간의 비율을 부하율(load factor)이라 하는데, 이상적인 부하율은 0.7(원소 7개/셀 10개)다.

3. 해시 함수

ex) 각 문자에 해당하는 숫자로 변환해서, 하나의 숫자가 될 때까지 결과값을 계속 더하는 해시 함수인 경우, 모든 데이터는 셀 1에서 9 사이로 채워진다.
=> 좋은 해시 함수란 사용 가능한 모든 셀에 데이터를 분산시키는 함수다.

해시 테이블 내부는 대부분 컴퓨터 언어가 관리한다. 프로그래밍 언어가 최고의 성능을 내도록 해시 테이블을 구현했다고 가정해도 무방하다.

8.7 해시 테이블로 데이터 조직

해시 테이블을 통해 다양한 시나리오의 데이터를 조직할 수 있다.

1. 딕셔너리(dictionary)

: 단어-정의가 쌍으로 연결된 데이터 형태
ex) HTTP 상태 코드 번호

STAUS_CODE = {200:"OK", 301:"Moved Permanently"...}

2. 다양한 속성을 갖는 객체를 표현하는 경우.

ex) 강아지 표현

[
	{name:Fido, Breed:Pug}
	{name:Happy, Breed:Poodle}
]

8.8 해시 테이블로 속도 올리기

해시 테이블을 인덱스로 사용하기

배열의 특정 값 포함 여부 확인하기.
ex) array=[61, 30, 82, 72, 14, 52].
각 값들을 키로, value에 true(어떤 값이든 가능하다)을 넣어 Map 생성.
-> 특정 값을 key로 Map에 검색하여 한 단계만으로 포함 여부를 확인할 수 있다.

한 배열이 다른 배열의 부분 집합인지 확인하기
ex) ["a", "b", "c", "d", "e"], ["b", "d", "f"]
이 중 for문을 돌려서 확인하는 경우, O(NM=53)이 소요된다.
그러나, 더 큰 배열을 map에 넣고 작은 배열을 key값으로 이용하여 확인하는 경우 O(M=3)으로 줄일 수 있다.

이처럼, 해시 테이블을 “인덱스”로 사용하는 기법은 배열을 여러 번 검색해야 하는 알고리즘에 자주 사용된다.


참고문헌)

0개의 댓글