해시 및 해시 테이블

반응형

img

해시(고기와 감자를 잘게 다져 섞어 요리하여 따뜻하게 차려 낸 것)

해시 함수는 문자열이나 파일 내용과 같은 데이터를 가져다가 고정된 크기의 문자열이나 숫자인 해시를 출력한다.

예를 들어, MD5 해시(MD5는 일반적인 해시 함수)는 단순히 "케이크"를 포함하는 파일에 대해 다음과 같다:

DF7CE038E2FA96EDF39206F898DF134D

 

다음은 같은 파일에 대한 해시가 "케이크"로 편집된 후의 모습입니다.

0E9091167610558FDA6F69BD6716771

해시 테이블

기타 이름:
해시, 해시 맵, 맵, 정렬되지 않은 맵, 사전

해시 테이블은 지정된 키에 대한 값을 빠르게 검색할 수 있도록 데이터를 구성합니다.

 

장점:

빠른 검색. 검색은 평균 O(1)O(1)시간이 걸립니다.

유연한 키. 대부분의 데이터 유형은 해시만 가능하다면 키에 사용할 수 있습니다.

약점:

최악의 경우 검색이 느립니다. 최악의 경우 검색에 O(n)O(n)시간이 걸립니다.

 

순서 없음. 열쇠는 특별한 순서로 보관되지 않습니다. 가장 작은 키, 가장 큰 키 또는 범위의 모든 키를 찾으려면 모든 키를 살펴봐야 합니다.

단방향 조회. O(1)O(1) 시간 내에 주어진 키의 값을 조회할 수 있지만, 주어진 값의 키를 조회하려면 전체 데이터 집합(O(n)O(n) 시간)을 반복해야 합니다.

캐시 친화적이지 않습니다. 많은 해시 테이블 구현체들은 링크된 리스트를 사용하며 메모리에서 서로 옆에 데이터를 두지 않는다.

해시 맵은 배열에 구축됩니다.

배열은 이미 해시맵과 상당히 유사합니다. 배열로 주어진 "키" . . . .에 대한 값을 빠르게 찾을 수 있지만 키를 "index"라고 부를 수는 없습니다. 키는 항상 순차 정수(0, 1, 2, 3 등)입니다.

 

해시맵을 배열 위에 있는 "핵"으로 생각하면 순차적 정수 "인덱스"로 고정되는 대신 유연한 키를 사용할 수 있습니다.

키를 배열 인덱스(정수)로 변환하는 함수만 있으면 됩니다. 그 함수를 해싱 함수라고 합니다.

해시 충돌

두 개의 키가 우리 어레이의 동일한 인덱스에 해시되면 어떨까요?
이를 해시 충돌이라고 합니다.

해시 테이블 작업에 O(n)O(n) 시간이 걸리는 경우

 

해시 충돌
동적 배열 크기 조정

놓다

집합은 값 없이 키만 저장한다는 점을 제외하면 해시맵과 같습니다.

그래프에서 방문한 노드, 문자열에서 본 문자 또는 인접 노드에서 사용하는 색상과 같은 항목 그룹을 추적할 때 집합이 나타나는 경우가 많습니다. 평소에는 세트 안에 뭐가 있는지 관심이 많아요.

<3>을 읽어주셔서 감사합니다.
해시 앤 해시맵에 대한 좋은 아이디어가 있길 바랍니다.