[TIL] 내배캠4기 React 15일차

복습

• 정렬 알고리즘 - 노마드코더 영상
• 해쉬테이블 - 노마드코더 영상
• 자바스크립트 - 영상 강의

자습

• 프로그래머스 Lv.0
• 깃허브 강의 1주차 예습

알고리즘 강의는 막바지를 달려가고... DP가 나오길래 화들짝..!(ptsd..)
그래서 잠시 도피성 예복습을 하게되었다.. 이번 프로젝트 협엽을 원활히 하기위해 깃헙도 보고 또보고.. 소스트리까진 안해봐서 도움이 많이 됐다. 혹시 팀원들이 물어본다면 뚝딱거리지 않도록 정리도 해보고.

알고리즘은 1,2,3주차 복습하며 이번주 안에 완강을 목표로 하자..!!
해쉬테이블 파트는 저번에 들을 땐 문제풀이가 '뭔소리고' 였다면 오늘 다시 들으니 '아 알겠어 응응' 이 되어 참..네.. 기뻤다구여..

---

Hash Table

• 데이터 검색과 저장이 빠른 자료구조
• key와 value를 저장(딕셔너리와 비슷함)
  ➡ 내부적으로 배열 사용

배열은 Linear Search여서 시간복잡도가 O(n)이다
해쉬테이블은 키값으로 검색하기에 상수 시간만큼 소요 O(1).

Q. 내부는 배열의 구조라면서? 배열이랑 뭐가 다르길래 더 빨라?
A. hash함수 덕분이얌

hash function

• 임의의 길이를 갖는 메세지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수

해쉬테이블 내부구현
* hash(key) -> 임의의 값 -> 배열 인덱스로서 값을 저장

• ⚠ : 인덱스 값이 동일하게 나와 같은 곳에 덮어씌워져버리는 경우가 발생 ➡ Hash Collision
  ➡ 해결방법: 체이닝 or 개방주소법

Chaining : 링크드 리스트를 이용