231020 항해 5일차 TIL - 해시테이블

항해99-17기 5일차 TIL

• leetcode 706. 해시맵 디자인 - https://leetcode.com/problems/design-hashmap - <파이썬 알고리즘 인터뷰> (이하 책) 2p.

1. leetcode 771. 보석과 돌 - https://leetcode.com/problems/jewels-and-stones - 책 2p.
2. leetcode 3. 중복 문자가 없는 가장 긴 부분 문자열 - https://leetcode.com/problems/longest-substring-without-repeating-characters - 책 2p.
3. leetcode 347. 상위 K 빈도 요소 - https://leetcode.com/problems/top-k-frequent-elements - 책 2p.
4. 백준 1920. 수 찾기 - https://www.acmicpc.net/problem/1920
5. 백준 17219. 비밀번호 찾기 - https://www.acmicpc.net/problem/17219

오늘의 강의 내용과 문제는 해시 테이블에 관한 내용이다.

---

# 해시 테이블 (Hash Table)

해시 테이블 (Hash Table)은,

키와 값의 맵핑 구조를 가지며,
!순서 없이! 키를 지정해 값을 호출하여 시간 복잡도가 O(1)이다.
JS의 Obj나 Map, 파이썬의 딕셔너리 등이 해당한다. ( 사전[어휘명] == 뜻 )
쉽게 생각하면 핸드폰 연락처에 저장해 둔 이름을 검색하여 번호를 불러 오는 방식과 같다.

키에 해싱을 적용해(키 데이터에 해시 함수를 적용), 2바이트 고정 크기 값으로 매핑된다.
해싱은 정보를 빠르게 저장하고 검색하기 용이하게 하며 이와 같이 해시 테이블이나,무작위화 함수, 암호 등과 관련이 깊어 때때로 혼용되기도 한다.