08 해시테이블로 매우 빠른 룩업

해시테이블

• 해시테이블은 다양한 프로그래밍 언어에서 서로 다른 이름으로 불린다 (해시, 맵, 해시맵, 딕셔녀리)
• 해시테이블은 키와 값의 쌍으로 이뤄진 값들의 리스트다.
  • 각 값의 위치는 키로 결정되기 때문에 키 자체를 해싱해 인덱스를 계산할 수 있다.
• 해시테이블의 값 룩업은 딱 한단계만 걸리므로 평균적으로 효율성이 O(1)이다

해싱

• 문자를 가져와 숫자로 변환하는 과정

해시함수

• 글자를 특정숫자로 변환하는데 사용한 코드
• 동일한 문자열을 해시함수에 적용할 때 마다 동일한 숫자로 변환 해야한다.

단방향 룩업

• 키를 모른채 값을 찾으려면 효율성이 O(N)
• 키를 사용해 값을 찾을 때 효율성은 O(1)
  • 값으로 키를 찾을 때는 룩업 기능 활용 x

충돌

• 이미 채워진 셀에 데이터를 추가하는 것

분리연결법

• 춛올을 해결하는 고전적인 방법
• 충돌이 발생했을때 셀에 값을 넣는 대신 배열로서의 참조를 넣는 방법
• 다수의 값이 들어있는 배열을 선형검색 해야하므로 검색에 단계가 더 걸린다
  • 최악의 경우 해시테이블 룩업성능은 O(N)

---

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

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

• 다음 요인에 따라 효율성이 정해진다.
• 사용 가능한 모든 셀에 데이터를 분산시키는 함수가 좋은 함수다.
  • 데이터를 넓게 퍼트릴수록 충돌이 적다.

효율적인 충돌조절

• 많은 메모리를 낭비하지 않으면셔 균형을 유지하며 충돌을 피하는 것이 좋은 해시테이블이다.
  • 최선의 방법은 해시테이블에 많은 셀을 두는 것이지만
  • 메모리를 많이 잡아먹지 않도록 균형을 잡아야한다.→ 부하율
• 이상적인 부하율 = 0.7 (원소 7개/ 셀 10개)
• 데이터를 더 추가하기 시작하면 새 데이터가 새로운 셀에 균등하게 분산되도록 컴퓨터는 셀을 더 추가, 해시함수를 바꿔서 해시테이블을 확장한다.
  • 컴퓨터 언어는 해시테이블이 얼마나 커야하는지, 어떤 해시함수를 쓰는지, 어떤 해시테이블을 확장할지 결정한다.

해시테이블로 데이터 조직

• 데이터를 쌍으로 저장하므로 데이터를 조직하는 많은 시나리오에 유용하다.
• 조건부 로직을 간소화 할 수도 있다.

해시테이블로 속도올리기

• 쌍이아닌 데이터라도 코드를 빠르게 만들 때 쓰일 수 있다.
• 배열을 해시테이블로 변환하면 O(N) → O(1)로 바뀐다.
  • 해시테이블을 인덱스로 사용하는 것

배열부분집합

O(N)

1. 빈 해시테이블을 생성,
2. 각 값을 순회하며 배열의 항복을 해시테이블에 추가
3. 항목자체를 키, true를 값으로 추가한다
4. 해시테이블이 생기면 작은 배열을 순회한다
5. 각 항목에 대해 해시테이블의 키인지 검사,