#hash-table
노트 2개
Algorithm › Data Structure
기초 자료구조: 배열에서 트라이까지연산의 약속(추상 자료형)과 구현(자료구조)을 나누는 관점, 배열과 realloc 크기 조정 비용, 배열·행렬 문제의 요령(부분 배열과 부분 수열, 인덱스 변환, 전치), 연결 리스트(C 구조체·Kotlin 예제)와 둘 중 고르는 기준, 더미 노드·제자리 뒤집기 같은 연결 리스트 기법, 층을 쌓아 건너뛰는 스킵 리스트, 이진 탐색 트리와 균형, 해시 테이블과 충돌, 트라이, 얕은 복사와 깊은 복사.
Algorithm › Data Structure
해시 테이블키를 해시 함수로 배열 인덱스로 바꿔 평균 O(1)에 찾는 해시 테이블의 원리, 해시 함수 설계(나눗셈·곱셈·다항·보편 해싱), 개방 주소법과 분리 연결법의 충돌 해결 비교와 이중 해싱의 약점, 적재율과 리사이즈, Java HashMap·Python dict 같은 실제 구현, 빈도 세기·애너그램 같은 문제 풀이 패턴, 해시 맵과 연결 리스트로 만드는 O(1) LRU·LFU 캐시.