배열 삭제와 탐색은 O(N)이지만, 해시 같은 경우는 모든 편집이 O(1)이 된다.

• 해시 같은 경우는 카드 번호와 이름을 매칭할 때 특정 번호(뒷 번호 4자리, 뒷 번호 2자리 등)로 이름을 매칭 시킬 수 있다.

• 해시 자료 구조 → 키에 대응되는 값을 저장하는 자료 구조
• 해시 자료 구조는 테이블로 관리 → 해시 테이블
• 충돌 처리가 해시 성능에 가장 큰 영향을 줌
• 최악의 상황은 O(N)이 되어 버림

충돌

• 일 대 일 대응이 아니라 다 대 일 대응일 경우 충돌이 발생하게 됨

충돌이 발생 됬을 경우 해결 방안

Chaining 해결 방안

• 연결 리스트나 동적 배열을 사용하여 인덱스의 연결 리스트에 값을 추가하는 방식
• STL 자료구조는 Chaining 해결 방안 사용

Open Addressing 해결 방안

• 이미 번지에 데이터가 있다면 다음 번지에 저장
• 카드번호 뒷 4자리 인덱스부터 카드 번호가 일치할 때까지 탐색
• 삭제를 할 때 해당 칸에 별도의 배열을 둠 (제거된 상태 명시해줘야 함)

Linear Probing

• 출동 발생 시 오른쪽으로 1칸씩 이동하는 방식
• Cache hit rate 가 높은 장점 존재