데이터 구조의 해싱: 함수, 기술 [예제 포함]

소개

해싱은 배열에서 데이터를 효율적으로 찾고 저장하는 문제를 해결하기 위해 설계된 중요한 데이터 구조 입니다. 예를 들어, 20000개의 번호 목록이 있고 해당 목록에서 검색할 번호를 지정한 경우 일치하는 항목을 찾을 때까지 목록의 각 번호를 스캔합니다.

전체 목록에서 검색하고 특정 번호를 찾는 데 상당한 시간이 필요합니다. 이 수동 스캔 프로세스는 시간이 많이 소요될 뿐만 아니라 비효율적입니다. 데이터 구조에서 해싱을 사용하면 검색 범위를 좁히고 몇 초 안에 숫자를 찾을 수 있습니다.

이 블로그는 해시 방법, 해시 테이블 및 예제를 통해 선형 탐색에 대한 더 깊은 이해를 제공합니다.

데이터 구조에서 해싱이란 무엇입니까?

데이터 구조 에서 해싱 은 해싱 기능을 사용하여 큰 데이터 청크를 작은 테이블에 매핑하는 기술입니다. 메시지 다이제스트 기능이라고도 합니다. 유사한 항목 모음에서 특정 항목을 고유하게 식별하는 기술입니다.

해시 테이블을 사용하여 데이터를 배열 형식으로 저장합니다. 배열의 각 값에는 고유한 인덱스 번호가 할당되었습니다. 해시 테이블은 배열 형식으로 저장된 각 값에 대해 이러한 고유 인덱스 번호를 생성하는 기술을 사용합니다. 이 기술을 해시 기술이라고 합니다.

데이터를 찾는 것보다 원하는 항목의 인덱스만 찾으면 됩니다. 인덱싱을 사용하면 전체 목록을 빠르게 스캔하고 원하는 항목을 검색할 수 있습니다. 인덱싱은 또한 특정 위치에 데이터를 삽입해야 할 때 작업을 삽입하는 데 도움이 됩니다. 테이블이 크든 작든 관계없이 몇 초 안에 데이터를 업데이트하고 검색할 수 있습니다.

데이터 구조 의 해싱은 2단계 프로세스입니다.

1. 해시 함수는 항목을 작은 정수 또는 해시 값으로 변환합니다. 이 정수는 원본 데이터를 저장하기 위한 인덱스로 사용됩니다.
2. 해시 테이블에 데이터를 저장합니다. 해시 키를 사용하여 데이터를 빠르게 찾을 수 있습니다.

데이터 구조의 해싱 예

다음은 데이터 구조 에서 해싱 의 실제 예입니다 .

• 학교에서 교사는 각 학생에게 고유한 롤 번호를 할당합니다. 나중에 교사는 해당 롤 번호를 사용하여 해당 학생에 대한 정보를 검색합니다.
• 도서관에는 무한한 수의 책이 있습니다. 사서는 각 책에 고유 번호를 할당합니다. 이 고유 번호는 책장에서 책의 위치를 ​​식별하는 데 도움이 됩니다.

체크아웃: 데이터 구조 정렬

해시 함수

데이터 구조의 해시 함수는 임의의 크기의 데이터를 고정된 크기의 데이터에 매핑합니다. 작은 정수 값(해시 값이라고도 함), 해시 코드 및 해시 합계와 같은 값을 반환합니다.

해시 = hashfunc(키)

인덱스 = 해시 % array_size

has 함수는 다음 요구 사항을 충족해야 합니다.

• 좋은 해시 함수는 계산하기 쉽습니다.
• 좋은 해시 함수는 클러스터링에 갇히지 않으며 해시 테이블 전체에 키를 고르게 분배합니다.
• 좋은 해시 함수는 두 요소 또는 항목이 동일한 해시 값에 할당될 때 충돌을 방지합니다.

해시 테이블

데이터 구조의 해싱 은 해시 테이블을 사용하여 키-값 쌍을 저장합니다. 그런 다음 해시 테이블은 해시 함수를 사용하여 인덱스를 생성합니다. 해싱은 이 고유 인덱스를 사용하여 삽입, 업데이트 및 검색 작업을 수행합니다.

데이터 구조의 해싱은 어떻게 작동합니까?

해싱에서 해싱 함수는 문자열이나 숫자를 작은 정수 값으로 매핑합니다. 해시 테이블은 해시 함수를 사용하여 목록에서 항목을 검색합니다. 해싱 기술의 목적은 데이터를 어레이 전체에 고르게 분배하는 것입니다. 해싱은 모든 요소에 고유 키를 할당합니다. 해시 테이블은 이 키를 사용하여 목록의 데이터에 액세스합니다.

해시 테이블은 키-값 쌍으로 데이터를 저장합니다. 키는 해싱 함수에 대한 입력 역할을 합니다. 그런 다음 해싱 함수는 저장된 각 값에 대해 고유한 인덱스 번호를 생성합니다. 인덱스 번호는 해당 키에 해당하는 값을 유지합니다. 해시 함수는 작은 정수 값을 출력으로 반환합니다. 해시 함수의 출력을 해시 값이라고 합니다.

예제를 통해 데이터 구조의 해싱을 이해합시다 . 30개의 셀이 있는 해시 테이블 내부에 일부 항목(키-값 쌍으로 배열)을 저장해야 한다고 상상해 보십시오.

값은 다음과 같습니다. (3,21) (1,72) (40,36) (5,30) (11,44) (15,33) (18,12) (16,80) (38,99)

해시 테이블은 다음과 같습니다.

더 읽어보기: Python의 데이터 구조 유형

충돌 해결 기법

해시 테이블에서 두 개의 키에 동일한 인덱스 번호가 할당되면 데이터 구조의 해싱 이 충돌합니다. 해시 테이블의 각 인덱스는 하나의 값만 저장해야 하므로 충돌로 인해 문제가 발생합니다. 데이터 구조의 해싱 은 여러 충돌 해결 기술을 사용하여 해시 테이블의 성능을 관리합니다.

선형 프로빙

데이터 구조의 해싱은 값을 저장하기 위해 이미 점유된 배열 인덱스를 생성합니다. 이러한 경우 해싱은 검색 작업을 수행하고 다음 빈 셀에 대해 선형으로 탐색합니다.

선형 프로빙 예제

크기가 30인 해시 테이블에 일부 항목을 저장하라는 요청을 받았다고 상상해 보십시오. 항목은 이미 키-값 쌍 형식으로 정렬되어 있습니다. 주어진 값은 다음과 같습니다: (3,21) (1,72) (63,36) (5,30) (11,44) (15,33) (18,12) (16,80) (46,99) .

hash(n)은 해시 함수를 사용하여 계산된 인덱스이고 T는 테이블 크기입니다. 슬롯 인덱스 = ( hash(n) % T)가 가득 차면 1((hash(n) + 1) % T)을 추가하여 다음 슬롯 인덱스를 찾습니다. (hash(n) + 1) % T도 가득 차면 (hash(n) + 2) % T를 시도합니다. (hash(n) + 2) % T도 가득 차면 (hash(n) + 2) % T를 시도합니다. n) + 3) % T.

해시 테이블은 다음과 같습니다.

더블 해싱

이중 해싱 기술은 두 가지 해시 함수를 사용합니다. 두 번째 해시 함수는 첫 번째 함수가 충돌을 일으킬 때 사용됩니다. 값을 저장할 오프셋 인덱스를 제공합니다.

이중 해싱 기법의 공식은 다음과 같습니다.

(firstHash(key) + i * secondHash(key)) % sizeOfTable

여기서 i는 오프셋 값입니다. 이 오프셋 값은 빈 슬롯을 찾을 때까지 계속 증가합니다.

예를 들어 h1과 h2라는 두 가지 해시 함수가 있습니다. 빈 슬롯을 찾으려면 다음 단계를 수행해야 합니다.

1. hash1(key)가 비어 있는지 확인합니다. 그렇다면 이 슬롯에 값을 저장하십시오.
2. hash1(key)가 비어 있지 않으면 hash2(key)를 사용하여 다른 슬롯을 찾습니다.
3. hash1(key) + hash2(key)가 비어 있는지 확인합니다. 그렇다면 이 슬롯에 값을 저장하십시오.
4. 카운터를 계속 증가시키고 빈 슬롯을 찾을 때까지 hash1(key)+2hash2(key), hash1(key)+3hash2(key) 등으로 반복합니다.

이중 해싱 예

크기가 20인 해시 테이블 안에 일부 항목을 저장해야 한다고 상상해 보십시오. 주어진 값은 (16, 8, 63, 9, 27, 37, 48, 5, 69, 34, 1)입니다.

h1(n)=n%20

h2(n)=n%13

nh(n, i) = (h1(n) + ih2(n)) mod 20

결론

이중 해싱은 계산 비용이 높지만 선형 탐색 방법보다 빠르게 다음 여유 슬롯을 검색합니다. 기사에 제공된 예는 설명을 위한 것입니다. 요구 사항에 따라 위에 제공된 설명을 수정할 수 있습니다. 이 블로그에서 우리는 데이터 구조의 해싱 개념에 대해 배웠습니다 .

예제를 시도하여 데이터 구조 지식을 강화할 수 있습니다. 데이터 구조 에 대해 더 알고 싶다면 Full Stack Development 과정 의 upGrad Executive PG Program을 확인하십시오 . 이 과정은 일하는 전문가를 위해 설계되었으며 최고의 회사에서 엄격한 교육 및 취업 알선을 제공합니다.