7장 해시테이블

= 검색 방법임

• 선형 검색 방법(순차검색)은 정렬이 안된 걸 검색할 수 있기 때문에 하나씩 하나씩 정렬하면서 검색 → O(N)
• 이진 검색 방법은 정렬이 된 배열을 검색하는 것 → O(logN)

좀 더 빠르게 검색할 수 없을까 고민하던 찰나에 만든 거가 해시테이블 O(1)

해시테이블이란?

• 쌍으로 이루어진 값들의 리스트

  • 첫 번째 항목 : 키
  • 두 번째 항목 : 값

• 해시 함수를 사용하여 키를 해시 값으로 매핑하고,

  해시 값을 이용하여 데이터의 값을 키와 함께 저장하는 자료구조

• 시간 복잡도 : O(1)

• 파이썬에서는 딕셔너리라고 부른다.

해시함수로 해싱

A = 1

B = 2

C = 3

D = 4

E = 5

ACE = 135

CAB = 312

이런 식으로

...

해싱이란?