해시맵, 해시테이블
해시 카드 키-값 쌍으로 구성된 데이터저장된 값은 키로 불러올 수 있습니다.
내부적으로 배열을 통해 구현되며 각 키는 배열의 인덱스로 해시되어 저장됩니다.
이때, 해시 함수는 키의 일부를 가져와 해싱이라고 하는 인덱스로 변환합니다.
그것은 말한다.
해쉬함수로 얻은 인덱스에 해당하는 배열 위치에 데이터가 저장되어 있다면, 나중에 같은 키로 검색하면 해쉬함수로 인덱스를 얻은 직후에 해당 위치의 값을 찾을 수 있다.
이때 검색 시간 복잡도는 O(1)이므로 매우 빠른 검색 속도를 보장합니다.
해시 테이블의 구조
해시 테이블의 구조는 다음과 같습니다.
- 단추 : 해시 테이블 접근을 위한 입력 값.
- 해시 함수 : 키를 해시 값에 매핑하는 작업입니다.
해시 함수
배열의 각 인덱스는 해시 함수를 사용하여 키와 연결된 값을 저장합니다.
현재 해시함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이며, 이 과정을 해싱이라고 합니다.
- 해시 값 : 해시 테이블의 인덱스입니다.
- 해시 테이블 : 키 값을 연결하고 저장하는 데이터 구조입니다.
해시 충돌
해시 함수와 관련된 인덱스에 다른 값이 이미 저장되어 있으면 충돌이 발생합니다.
. 해시 충돌은 해시 함수의 효율성을 감소시키고 데이터 검색 성능을 저하시킵니다.
따라서 충돌을 최소화하는 것이 중요합니다.
해시 충돌 해결
해시 충돌을 최소화하는 한 가지 방법은 충돌이 발생할 때 데이터를 저장할 다른 장소를 찾는 것입니다.
두 가지 대표적인 방법은 열린 주소, 별도의 연결 및 별도의 연결알아봅시다.
열린 주소
충돌이 발생한 경우 테이블에서 충돌이 발생한 해시 버킷과 다른 해시 버킷을 찾아 새로운 데이터를 저장하는 방식이다.
다시 말해서, 개방형 주소 지정 방식은 해시 충돌 시 해시 함수를 다시 계산하여 새로운 위치를 찾는 방식입니다.
오전.
오른쪽 주소 열기 선형 조사, 2차 조사, 이중 해싱 등.
충돌이 발생할 때 선형 탐색이 다음 해시 버킷에 데이터를 저장하는 방법오전. 예를 들어 해시 버킷 3이 이미 사용 중인 경우 데이터는 해시 버킷 4에 저장됩니다.
해시 버킷 4도 사용되는 경우 데이터는 해시 버킷 5 등에 저장됩니다.
문제로 1차 클러스터링 문제 발생할 수 있다는 것
기본 클러스터링
충돌이 반복되는 지점을 중심으로 데이터를 수집하는 경우를 말한다.
2차 탐색은 충돌이 발생했을 때 주기적으로 다음 해시 버킷을 찾는 방법입니다.
오전. 예를 들어 해시 버킷 3이 이미 사용 중인 경우 데이터는 해시 버킷 3 + 1^2에 저장됩니다.
해시 버킷 3 + 1^2도 사용되면 데이터를 해시 버킷 3 + 2^2에 저장하는 식으로 간격을 두고 다음 해시 버킷을 찾습니다.
선형 탐색 방법의 1차 군집화는 부분적으로 보완할 수 있지만 2차 군집화 문제가 발생할 수 있습니다.
이중 해시는 충돌이 발생했을 때 두 개의 해시 함수를 사용하여 다음 해시 버킷을 찾는 방법입니다.
오전. 예를 들어 버킷 3이 이미 사용 중인 경우 해시 함수 h1 및 h2를 사용하여 다음 해시 버킷을 찾습니다.
연결 및 별도 연결
연결 주소 방식은 충돌이 발생한 버킷에 다른 데이터를 삽입할 때 연결 리스트를 이용해 새로운 데이터를 버킷에 연결하는 방식이다.
오전. 이 방법은 간단하고 구현하기 쉬우며 메모리를 효율적으로 사용할 수 있지만 연결 리스트의 길이가 길어질수록 검색 시간이 늘어나는 단점이 있다.
반면 연결 해제 방식은 충돌이 발생한 버킷에 여러 개의 슬롯을 배치하고 각 슬롯에 데이터를 저장한다.
Insert는 해시 함수를 사용하여 버킷을 찾은 다음 버킷에서 빈 슬롯을 찾아 데이터를 저장합니다.
이 방식은 슬롯 수가 증가할수록 충돌 확률이 낮아지기 때문에 검색 시간이 일정하게 유지된다는 장점이 있지만 구현이 어렵고 많은 메모리 공간을 필요로 한다.
따라서 연결 주소 방식은 데이터의 개수가 적거나 저장 공간을 절약하기 위해 주로 사용되며, 별도 연결 방식은 데이터 개수가 많거나 해시 충돌이 자주 발생하는 경우에 주로 사용된다.