Hash Table

21년, 노션에 정리했던 노마드코더 알고리즘 강의 요약노트

✔️ Hash Table?

Key & Value 형태 (python에선 Dictionary)

✔️ 배열과 해쉬테이블 비교

• 배열
  

선형검색, O(N), 아이템 많을수록 느려짐

• 해쉬테이블
  

O(1), 1step, 아이템 수 상관 없음

---

✔️ 원리 (어떻게 작동, Hash는 무엇인가!)

• 내부에 array구조

• 어레이 접근할때 인덱스로 접근

• 왜 해쉬테이블?! 해쉬함수가 있기때문!

• 아이템이름(key)를 가져다가 해쉬함수에 넣으면 글자 수 대로 index 반환, 그럼 거기에 value 저장!

  • 만약 글자수가 같다면?! 충돌(Collision)!
    • 여러 해결방법 중 1가지 예시 >> 한 곳에 여러개 저장. 찾을땐 인덱스 위치가서 이후 선형계산 (이와 같은 이유로 해쉬테이블이 항상 시간복잡도가 상수인것은 아님! 그래도 평균을 기준으로 시간복잡도는 O(1)임)

• 천재들이 이미 만들어놔서 직접 해쉬함수를 만들일은 거의 없을것~ㅎㅁㅎ