c++ hashtable 예제

해싱은 유사한 개체 그룹에서 특정 개체를 고유하게 식별하는 데 사용되는 기술입니다. 해싱이 우리 삶에서 사용되는 방법의 몇 가지 예는 다음과 같습니다: 예를 들어 사용으로, 먼저 템플릿 초기화하여 컨테이너를 만들고 키-값 쌍을 넣습니다. 그런 다음 맵에서 요소를 얻거나 제거할 수 있습니다. 검색된 키가 없으면 false가 반환되고 값이 업데이트되지 않습니다. 이 두 예에서 학생들과 책들은 고유 한 숫자로 해시되었습니다. 현재 문서에서는 매우 간단한 해시 테이블 예제를 보여 주고 있습니다. 간단한 해시 함수를 사용하고, 선형 프로빙(열린 주소 지정 전략)을 사용하여 충돌이 해결되고 해시 테이블의 크기가 일정합니다. 이 예제에서는 해싱 기술의 기본 을 명확하게 보여 줍니다. 물론 정렬되지 않은 연관 컨테이너에 두 질문을 적용할 수 있습니다.

이제 컨테이너 std::unordered_set, std:unordered_multiset, std::unordered_map 및 std:unordered_multimap. std::map 및 std::unordered_map의 유사한 이름은 우연이 아닙니다. 둘 다 비슷한 인터페이스를 가지고 있습니다. 더 정확하게. std::map의 인터페이스는 std::unorederd_map의 인터페이스의 하위 집합입니다. 살펴보기: 해시 함수는 각 키를 고유한 버킷에 이상적으로 할당하지만 대부분의 해시 테이블 디자인은 해시 충돌이 발생할 수 있다고 가정합니다. 내 해시 함수는 키를 해시 테이블 크기로 나눌 때 나머지를 반환합니다. 전체 프로세스는 모든 키에 대해 해시 테이블 크기 내에서 정수 위치를 확보하여 해당 값을 삽입합니다. 그래서 프로세스는 간단하고, 사용자는 입력으로 세트(key, value)를 제공하고 해시 함수에 의해 생성된 값을 기반으로 인덱스가 생성되어 특정 키에 해당하는 값이 저장되는 곳에 한다. 따라서 O(1)인 키에 해당하는 값을 가져와야 할 때마다 해시 함수는 모든 문자열에 대해 동일한 인덱스를 계산하고 문자열은 다음 형식으로 해시 테이블에 저장됩니다.

모든 문자열의 인덱스가 동일하므로 해당 인덱스에 목록을 만들고 해당 목록에 있는 모든 문자열을 삽입할 수 있습니다. 계산하기 쉬움: 계산이 쉬워야 하며 그 자체로 알고리즘이 되어서는 안 됩니다. 이 표는 전체 체계를 한 번 더 보여줍니다. 체계는 주문된 컨테이너(logarithmic)와 정렬되지 않은 컨테이너(상수)에 대한 액세스 시간을 포함합니다. 또한 클래스에는 키로 매핑된 값에 액세스하는 get(key) 함수, 키 값 쌍을 테이블에 배치하고 키로 해시 노드를 제거하는 remove(key) 함수를 포함합니다. 충돌 해결을 위해 별도의 체인링 전략이 사용되었습니다. 문자열 해시 함수 인덱스 abcdef (971 + 982 + 993 + 1004 + 1015 + 1026)%2069 38 bcdefa (981 + 992 + 1003 + 1014 + 1025 + 976)%2069 23 cdefab (991 + 1002 + 1013 + 1013 + 1024 + 975 + 1023 + 974 + 985 + 996)%2069 11 해시 된 인덱스라고 가정해 봅시다. 항목 레코드는 하나의 해시 함수에 의해 계산되는 인덱스이며 해당 인덱스의 슬롯이 이미 사용되었습니다.

Det här inlägget postades i Okategoriserade. Bokmärk permalänken.