hash table c programs implement hash table
이 튜토리얼은 C ++ 해시 테이블과 해시 맵을 설명합니다. 또한 해시 테이블 응용 프로그램 및 C ++ 구현에 대해 학습합니다.
해싱은 '해시 함수'를 사용하여 많은 양의 데이터를 더 작은 테이블에 매핑 할 수있는 기술입니다.
해싱 기술을 사용하면 선형 및 이진 검색과 같은 다른 검색 기술과 비교할 때 데이터를 더 빠르고 효율적으로 검색 할 수 있습니다.
ETL 테스터 인터뷰 질문 및 답변
이 튜토리얼의 예제를 통해 해싱 기술을 이해하겠습니다.
학습 내용 :
C ++에서 해싱
수천 권의 책을 보관하는 대학 도서관의 예를 들어 보겠습니다. 책은 주제별, 학과별로 정리되어 있습니다.하지만 여전히 각 섹션에는 많은 책이 있으므로 검색이 매우 어렵습니다.
따라서이 어려움을 극복하기 위해 우리는 책의 위치를 즉시 알 수 있도록 각 책에 고유 한 번호 또는 키를 할당합니다. 이것은 실제로 해싱을 통해 달성됩니다.
라이브러리 예제를 계속 진행하면서 부서, 주제, 섹션 등에 따라 매우 긴 문자열을 생성 할 수있는 각 책을 식별하는 대신 고유 함수를 사용하여 라이브러리의 각 책에 대해 고유 한 정수 값 또는 키를 계산합니다. 이러한 키를 별도의 테이블에 저장하십시오.
위에서 언급 한 고유 한 기능을“해시 기능”이라고하고 별도의 테이블을“해시 테이블”이라고합니다. 해시 함수는 주어진 값을 해시 테이블의 특정 고유 키에 매핑하는 데 사용됩니다. 결과적으로 요소에 더 빠르게 액세스 할 수 있습니다. 해싱 기능이 더 효율적 일수록 각 요소를 고유 키에 매핑하는 것이 더 효율적입니다.
해시 함수를 고려해 보겠습니다. h (x) 그 가치 ' 엑스 '에서' x % 10 ”가 배열에 있습니다. 주어진 데이터에 대해 아래 다이어그램과 같이 키 또는 해시 코드 또는 해시를 포함하는 해시 테이블을 구성 할 수 있습니다.
위의 다이어그램에서 배열의 항목이 해시 함수를 사용하여 해시 테이블의 위치에 매핑되는 것을 볼 수 있습니다.
따라서 해싱은 아래에 언급 된 두 단계를 사용하여 구현된다고 말할 수 있습니다.
#1) 값은 해시 함수를 사용하여 고유 한 정수 키 또는 해시로 변환됩니다. 해시 테이블에 속하는 원래 요소를 저장하기위한 인덱스로 사용됩니다.
위의 다이어그램에서 해시 테이블의 값 1은 다이어그램의 LHS에 제공된 데이터 배열의 요소 1을 저장하는 고유 키입니다.
#두) 데이터 배열의 요소는 해시 된 키를 사용하여 빠르게 검색 할 수있는 해시 테이블에 저장됩니다. 위의 다이어그램에서 해시 함수를 사용하여 각각의 위치를 계산 한 후 해시 테이블에 모든 요소를 저장했음을 확인했습니다. 다음 표현식을 사용하여 해시 값과 인덱스를 검색 할 수 있습니다.
hash = hash_func(key) index = hash % array_size해시 기능
매핑의 효율성은 우리가 사용하는 해시 함수의 효율성에 달려 있다고 이미 언급했습니다.
해시 함수는 기본적으로 다음 요구 사항을 충족해야합니다.
- 간편한 계산 : 해시 함수는 고유 키를 쉽게 계산할 수 있어야합니다.
- 더 적은 충돌 : 요소가 동일한 키 값과 동일하면 충돌이 발생합니다. 사용되는 해시 함수에는 가능한 한 최소한의 충돌이 있어야합니다. 충돌이 발생하기 때문에 적절한 충돌 해결 기술을 사용하여 충돌을 처리해야합니다.
- 균등 분포: 해시 함수는 해시 테이블 전체에 데이터를 균일하게 분산하여 클러스터링을 방지해야합니다.
해시 테이블 C ++
해시 테이블 또는 해시 맵은 원래 데이터 배열의 요소에 대한 포인터를 저장하는 데이터 구조입니다.
라이브러리 예제에서 라이브러리의 해시 테이블에는 라이브러리의 각 책에 대한 포인터가 포함됩니다.
해시 테이블에 항목이 있으면 배열의 특정 요소를 더 쉽게 검색 할 수 있습니다.
이미 살펴본 것처럼 해시 테이블은 해시 함수를 사용하여 원하는 값을 찾을 수있는 버킷 또는 슬롯의 배열로 인덱스를 계산합니다.
다음 데이터 배열이있는 또 다른 예를 고려하십시오.
아래와 같이 크기가 10 인 해시 테이블이 있다고 가정합니다.
이제 아래에 주어진 해시 함수를 사용하겠습니다.
Hash_code = Key_value % size_of_hash_table이것은 Hash_code = Key_value % 10
위의 함수를 사용하여 아래와 같이 해시 테이블 위치에 키 값을 매핑합니다.
| 데이터 항목 | 해시 기능 | 해시 코드 |
|---|---|---|
| 22 | 22 % 10 = 2 | 두 |
| 25 | 25 % 10 = 5 | 5 |
| 27 | 27 % 10 = 7 | 7 |
| 46 | 46 % 10 = 6 | 6 |
| 70 | 70 % 10 = 0 | 0 |
| 89 | 89 % 10 = 9 | 9 |
| 31 | 31 % 10 = 1 | 1 |
위의 테이블을 사용하여 다음과 같이 해시 테이블을 표현할 수 있습니다.
따라서 해시 테이블에서 요소에 액세스해야 할 때 검색을 수행하는 데 O (1) 시간이 걸립니다.
충돌
일반적으로 해시 함수를 사용하여 해시 코드를 계산하므로 키 값을 해시 테이블의 해시 코드에 매핑 할 수 있습니다. 위의 데이터 배열 예에서 값 12를 삽입하겠습니다.이 경우 키 값 12의 hash_code는 2가됩니다 (12 % 10 = 2).
그러나 해시 테이블에는 아래와 같이 hash_code 2에 대한 키-값 22에 대한 매핑이 이미 있습니다.
위에 표시된 것처럼 두 값, 즉 12와 22에 대해 동일한 해시 코드가 있습니다. 즉, 2입니다. 하나 이상의 키 값이 동일한 위치에 해당하면 충돌이 발생합니다. 따라서 해시 코드 위치는 이미 하나의 키 값이 차지하고 있으며 동일한 위치에 배치해야하는 다른 키 값이 있습니다.
해싱의 경우 매우 큰 해시 테이블이 있어도 충돌이 발생할 수 있습니다. 이는 일반적으로 큰 키에 대해 작은 고유 값을 발견하기 때문에 하나 이상의 값이 주어진 시간에 동일한 해시 코드를 가질 수 있기 때문입니다.
해싱에서 충돌이 불가피하다는 점을 감안할 때 우리는 항상 충돌을 방지하거나 해결할 방법을 찾아야합니다. 해싱 중에 발생하는 충돌을 해결하기 위해 사용할 수있는 다양한 충돌 해결 기술이 있습니다.
충돌 해결 기법
다음은 해시 테이블에서 충돌을 해결하기 위해 사용할 수있는 기술입니다.
별도의 체인 (개방형 해싱)
이것은 가장 일반적인 충돌 해결 기술입니다. 개방형 해싱이라고도하며 연결 목록을 사용하여 구현됩니다.
YouTube 비디오를 mp3로 가장 잘 변환
별도의 연결 기술에서 해시 테이블의 각 항목은 연결 목록입니다. 키가 해시 코드와 일치하면 해당 특정 해시 코드에 해당하는 목록에 입력됩니다. 따라서 두 키에 동일한 해시 코드가 있으면 두 항목이 연결 목록에 입력됩니다.
위의 예에서 별도의 체인이 아래에 표시됩니다.
위의 다이어그램은 연결을 나타냅니다. 여기서는 mod (%) 함수를 사용합니다. 두 개의 키 값이 동일한 해시 코드와 같을 때 연결 목록을 사용하여 이러한 요소를 해당 해시 코드에 연결합니다.
키가 해시 테이블 전체에 균일하게 분산 된 경우 특정 키를 찾는 평균 비용은 해당 연결 목록의 평균 키 수에 따라 달라집니다. 따라서 슬롯보다 항목 수가 증가하는 경우에도 별도의 체이닝이 유효합니다.
개별 체인의 최악의 경우는 모든 키가 동일한 해시 코드와 동일하므로 하나의 연결 목록에만 삽입되는 경우입니다. 따라서 해시 테이블의 모든 항목과 테이블의 키 수에 비례하는 비용을 찾아야합니다.
선형 프로빙 (개방 주소 지정 / 폐쇄 해싱)
개방 주소 지정 또는 선형 프로빙 기법에서 모든 항목 레코드는 해시 테이블 자체에 저장됩니다. 키-값이 해시 코드에 매핑되고 해시 코드가 가리키는 위치가 비어 있으면 해당 위치에 키 값이 삽입됩니다.
위치가 이미 점유 된 경우 프로빙 시퀀스를 사용하여 해시 테이블에서 점유되지 않은 다음 위치에 키 값이 삽입됩니다.
선형 프로빙의 경우 해시 함수가 아래와 같이 변경 될 수 있습니다.
해시 = 해시 % hashTableSize
해시 = (해시 + 1) % hashTableSize
해시 = (해시 + 2) % hashTableSize
해시 = (해시 + 3) % hashTableSize
선형 프로빙의 경우 슬롯 또는 연속 프로브 사이의 간격이 일정하다는 것을 알 수 있습니다.
위의 다이어그램에서 우리는 0일해시 함수“hash = hash % hash_tableSize”를 사용하여 10을 입력합니다.
이제 요소 70도 해시 테이블의 위치 0과 동일합니다. 그러나 그 위치는 이미 점유되어 있습니다. 따라서 선형 프로빙을 사용하여 다음 위치 인 1을 찾을 수 있습니다.이 위치가 비어 있으므로 화살표를 사용하여 표시된대로이 위치에 키 70을 배치합니다.
결과 해시 테이블은 다음과 같습니다.
선형 프로빙은 연속적인 셀이 점유 될 가능성이 있고 새로운 요소를 삽입 할 확률이 감소하는 'Primary Clustering'문제로 어려움을 겪을 수 있습니다.
또한 두 요소가 첫 번째 해시 함수에서 동일한 값을 얻으면 두 요소 모두 동일한 프로브 시퀀스를 따릅니다.
2 차 프로빙
2 차 프로빙은 선형 프로빙과 동일하지만 프로빙에 사용되는 간격 만 다릅니다. 이름에서 알 수 있듯이이 기술은 선형 거리 대신 충돌이 발생할 때 슬롯을 점유하기 위해 비선형 또는 2 차 거리를 사용합니다.
2 차 프로빙에서 슬롯 사이의 간격은 이미 해시 된 인덱스에 임의의 다항식 값을 추가하여 계산됩니다. 이 기술은 1 차 클러스터링을 상당히 줄이지 만 2 차 클러스터링을 개선하지는 않습니다.
이중 해싱
이중 해싱 기술은 선형 프로빙과 유사합니다. 이중 해싱과 선형 프로빙의 유일한 차이점은 이중 해싱 기술에서 프로빙에 사용되는 간격이 두 개의 해시 함수를 사용하여 계산된다는 것입니다. 해시 함수를 하나씩 키에 적용하므로 기본 클러스터링과 보조 클러스터링이 제거됩니다.
체이닝 (개방형 해싱)과 선형 프로빙 (개방형 주소 지정)의 차이점
| 연결 (개방형 해싱) | 선형 프로빙 (개방형 주소 지정) |
|---|---|
| 키 값은 별도의 연결 목록을 사용하여 테이블 외부에 저장할 수 있습니다. | 키 값은 테이블 내부에만 저장되어야합니다. |
| 해시 테이블의 요소 수가 해시 테이블의 크기를 초과 할 수 있습니다. | 해시 테이블에있는 요소의 수는 해시 테이블의 인덱스 수를 초과하지 않습니다. |
| 삭제는 연결 기술에서 효율적입니다. | 삭제는 번거로울 수 있습니다. 필요하지 않으면 피할 수 있습니다. |
| 위치별로 별도의 연결 목록이 유지되므로 차지하는 공간이 큽니다. | 모든 항목이 동일한 테이블에 수용되기 때문에 차지하는 공간이 더 적습니다. |
C ++ 해시 테이블 구현
해시 테이블을 프로그래밍하기 위해 배열 또는 연결 목록을 사용하여 해싱을 구현할 수 있습니다. C ++에는 해시 테이블과 유사한 구조이지만 각 항목은 키-값 쌍인 '해시 맵'이라는 기능도 있습니다. C ++에서는 호출 된 해시 맵 또는 단순히 맵입니다. C ++의 해시 맵은 일반적으로 순서가 지정되지 않습니다.
지도의 기능을 구현하는 C ++의 표준 템플릿 라이브러리 (STL)에 정의 된 헤더가 있습니다. 우리는 STL 맵 STL 튜토리얼에서 자세히 설명합니다.
다음 구현은 연결 목록을 해시 테이블의 데이터 구조로 사용하여 해싱하기위한 것입니다. 또한이 구현에서 충돌 해결 기술로 'Chaining'을 사용합니다.
#include #include using namespace std; class Hashing { int hash_bucket; // No. of buckets // Pointer to an array containing buckets list *hashtable; public: Hashing(int V); // Constructor // inserts a key into hash table void insert_key(int val); // deletes a key from hash table void delete_key(int key); // hash function to map values to key int hashFunction(int x) { return (x % hash_bucket); } void displayHash(); }; Hashing::Hashing(int b) { this->hash_bucket = b; hashtable = new list (hash_bucket); } //insert to hash table void Hashing::insert_key(int key) { int index = hashFunction(key); hashtable(index).push_back(key); } void Hashing::delete_key(int key) { // get the hash index for key int index = hashFunction(key); // find the key in (inex)th list list :: iterator i; for (i = hashtable(index).begin(); i != hashtable(index).end(); i++) { if (*i == key) break; } // if key is found in hash table, remove it if (i != hashtable(index).end()) hashtable(index).erase(i); } // display the hash table void Hashing::displayHash() { for (int i = 0; i ' << x; cout << endl; } } // main program int main() { // array that contains keys to be mapped int hash_array() = {11,12,21, 14, 15}; int n = sizeof(hash_array)/sizeof(hash_array(0)); Hashing h(7); // Number of buckets = 7 //insert the keys into the hash table for (int i = 0; i < n; i++) h.insert_key(hash_array(i)); // display the Hash table cout<<'Hash table created:'< 산출:
생성 된 해시 테이블 :
0-> 21-> 14
1-> 15
두
삼
4-> 11
5-> 12
6
키 12 삭제 후 해시 테이블 :
0-> 21-> 14
1-> 15
두
삼
4-> 11
5
6
출력은 크기 7로 생성 된 해시 테이블을 보여줍니다. 충돌을 해결하기 위해 체인을 사용합니다. 키 중 하나를 삭제 한 후 해시 테이블을 표시합니다.
해싱의 응용
# 1) 비밀번호 확인 : 암호 확인은 일반적으로 암호화 해시 함수를 사용하여 수행됩니다. 암호를 입력하면 시스템은 암호의 해시를 계산 한 다음 확인을 위해 서버로 전송됩니다. 서버에는 원래 암호의 해시 값이 저장됩니다.
# 2) 데이터 구조 : C ++의 unordered_set 및 unordered_map, python 또는 C #의 사전, HashSet 및 Java의 해시 맵과 같은 다른 데이터 구조는 모두 키가 고유 한 값인 키-값 쌍을 사용합니다. 값은 다른 키에 대해 동일 할 수 있습니다. 해싱은 이러한 데이터 구조를 구현하는 데 사용됩니다.
# 3) 메시지 다이제스트 : 이것은 암호화 해시를 사용하는 또 다른 응용 프로그램입니다. 메시지 다이제스트에서 우리는 보내고받는 데이터 또는 파일에 대한 해시를 계산하고 저장된 값과 비교하여 데이터 파일이 변조되지 않았는지 확인합니다. 여기서 가장 일반적인 알고리즘은 'SHA 256'입니다.
# 4) 컴파일러 작동 : 컴파일러가 프로그램을 컴파일 할 때 프로그래밍 언어에 대한 키워드는 다른 ID와 다르게 저장됩니다. 컴파일러는 이러한 키워드를 저장하기 위해 해시 테이블을 사용합니다.
# 5) 데이터베이스 인덱싱 : 해시 테이블은 데이터베이스 인덱싱 및 디스크 기반 데이터 구조에 사용됩니다.
# 6) 연관 배열 : 연관 배열은 인덱스가 정수형 문자열 또는 기타 객체 유형이 아닌 데이터 유형 인 배열입니다. 해시 테이블은 연관 배열을 구현하는 데 사용할 수 있습니다.
결론
해싱은 삽입, 삭제 및 검색 작업에 일정한 시간 O (1)가 걸리므로 가장 널리 사용되는 데이터 구조입니다. 해싱은 대부분 대용량 데이터 항목에 대해 고유 한 작은 키 값을 계산하는 해시 함수를 사용하여 구현됩니다. 배열과 연결 목록을 사용하여 해싱을 구현할 수 있습니다.
하나 이상의 데이터 항목이 동일한 키 값과 동일 할 때마다 충돌이 발생합니다. 우리는 선형 프로빙, 체이닝 등 다양한 충돌 해결 기술을 보았습니다. 또한 C ++에서 해싱 구현을 보았습니다.
결론적으로 해싱은 프로그래밍 세계에서 가장 효율적인 데이터 구조라고 말할 수 있습니다.
=> 여기에서 전체 C ++ 교육 시리즈를 찾아보십시오.
추천 도서
- 의사 결정 테이블 기법을 사용하여 복잡한 비즈니스 로직 테스트 시나리오를 작성하는 방법
- 필드 검증 테이블 (FVT) : 필드 검증을위한 테스트 설계 기법
- QTP 튜토리얼 # 15-QTP에서 텍스트 영역, 테이블 및 페이지 체크 포인트 사용
- STL의지도
- 라우터에 관한 모든 것 : 라우터 유형, 라우팅 테이블 및 IP 라우팅
- Top 40 최고의 MySQL 인터뷰 질문 및 답변 (2021 질문)
- 상위 90 개 SQL 인터뷰 질문 및 답변 (최신)
- Unix 유틸리티 프로그램 명령 : What, Man, Find Su, Sudo (Part D)