해시 테이블, 해시맵
먼저 알고있어야 할 내용
- 해싱
- 임의의 값(예: key)를 고정된 크기의 값(예:인덱스)로 변환하는 작업
- 해시 함수
- 해싱 작업에 사용되는 함수
동일한 인풋에 대해 항상 동일한 값을 반환해야한다
해시 테이블
- 해시 함수를 이용하여 나온 값(인덱스)에 넣고 싶은 값(key)을 저장 자료구조
해시맵
- 해시 테이블처럼 key만 넣는게 아니라 대응(mapping)하는 value까지 같이 저장하는 자료구조
- 내부적으로 배열을 이용하여 데이터를 저장
- 검색, 삽입, 삭제의 평균 빅오 표기법은 O(1)
- 최악은 O(n)
- 결국 key는 위치 검색용