hash

해시 테이블(해시 맵): 키를 값(해시)에 매핑할 수 있는 구조인, 연관 배열 ADT를 구현하는 자료구조 대부분의 연산이 분할 상환 분석에 따라 시간 복잡도가 O(1) 해시 함수: 임의 크기 데이터를 고정 크기 값(해시)으로 매핑하는 데 사용할 수 있는 함수 해시 함수가 값을 매핑할 때 충돌을 최소화하는 것이 무엇보다 중요함 로드 팩터: 해시 테이블에 저장된 데이터 개수를 버킷의 개수로 나눈 것 해싱: 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것 개별 체이닝: 충돌 발생 시 연결리스트로 연결 오픈 어드레싱: 충돌 방생 시 탐사를 통해 빈 공간을 찾는 방식 전체 슬롯 개수 이상 저장 불가, 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장이 없음 데이터들이 고르지 않고 뭉치는 ..