- key, value로 데이터를 저장하는 자료구조 중 하나
- 빠른 검색 속도를 제공한다. (내부적인 배열을 사용하여 데이터 저장)
- 각각의 key 값에 해시 함수를 적용해 배열의 고유한 index를 생성
- index를 활용해 값을 저장하거나 검색한다.
- 평균 시간복잡도는 O(1)이다.
해시 함수
고유한 인덱스 값을 설정하기 위한 용도
1) Division Method : 주소 = 입력값 % 테이블의 크기
2) Difit Folding : key의 문자열을 ASCII 코드로 바꾸고 합한 데이터를 테이블 내 주소로 사용
3) Multiplcation Method : 숫자로 된 키 값 a, 0과 1 사이 실수 b, 2의 제곱수 c를 사용 h(a) = (abmod1) * c
4) Univeral Hashing : 다수의 해시 함수를 만들어 집합에 넣어두고 무작위로 해시 함수를 선택
해시 값이 충돌하면?
1) 분리 연결법(Separate Chaining)
- 동일한 버킷에 데이터에 대해 추가 메로리를 사용하여 다음 데이터의 주소를 저장함
- 해시 테이블 확장이 필요 없음, 삭제 쉬움
- 데이터 수가 많아질수록 chaining 되는 데이터가 많아짐 => 캐시 효율성 감소
2) 개방 주소법(Open Addressing)
- 비어있는 해시 테이블의 공간 활용
- 데이터가 삭제되면 해시 테이블을 재정리해줘야함
1) Linear Probing : 현재 index로부터 고정폭 만큼씩 이동해서 빈 곳에 저장
2) Quadratic Probing : 해시 저장순서 폭을 제곱으로 저장
3) Double Hashing Probing : 해시된 값을 한 번 더 해싱
해시맵과 해시테이블의 차이
해시테이블은 병렬 프로그래밍을 할 때 동기화를 지원해준다.
즉, 함수 처리 시간이 조금 지연된다.
병렬 처리를 하면서 자원의 동기화를 고려해야 한다면? => 해시테이블
병렬 처리, 자원 동기화가 필요 없다면 => 해시맵
