해싱(hasing)이란?
- 키 값에 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근 매핑하는 과정. 해시테이블을 이용하여 탐색한다.
키(key) : 매핑 전 원래 데이터 값
해시값 : 매핑 후 데이터 값
해시 테이블
해시함수를 사용하여 키를 해시값으로 매핑하고 이 해시값을 색인 혹은 주소 삼아 데이터의 값을 키와 함께 저장하는 자료구조.
해싱을 한 후 직접 접근이 가능한 구조
장점
1. 해시가 충돌할 수 있는 가능성이 있다. 하지만 적은 리소스로 많은 데이터를 효율적으로 관리가 가능하다.
2. 하드디스크, 클라우드에 존재하는 데이터들은 무한에 가까운데, 이것들을 유한한 개수의 해시값으로 매핑하면서 작은 크기의 캐시 메모리로도 프로세스 관리가 가능
3. 색인에 해시값을 사용하므로 모든 데이터를 살피지 않아도 검색과 삽입/삭제를 빠르게 수행
4. 해시 함수는 언제나 동일한 해시값을 리턴, 해당 색인만 알면 해시 테이블의 크게이 상관없이 데이터에 빠르게 접근 가능.
5. 색인은 간단한 함수로 작동(효율적)
6. 데이터 삽입,삭제,탐색시 시간 복잡도0(1)을 지향
- 시간복잡도란?
알고리즘을 구성하는 명령어들이 몇번이나 실행이 되는지를 센 결과에 각 명령어의 실행시간을 곱한합계
프로그래머스 문제
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.
제한사항
마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
completion의 길이는 participant의 길이보다 1 작습니다.
참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
참가자 중에는 동명이인이 있을 수 있습니다.
입출력 예시
예제
#1
"leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.
#2
"vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.
#3
"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.
풀이1
해쉬를 이용한 풀이
ex) participant = ["mislav", "stanko", "mislav", "ana"]일시
{ mislav: 2, stanko: 1, ana: 1 }
key값 : 이름, value값: 참가인원 수 저장하여 value값이 1이상이면 완주하지 못한 인원으로 반환시켰다.
