C에서의 해시 맵의 실장
C++ STL에 있는 것처럼 C에 해시맵을 처음부터 작성하는 방법은 무엇입니까?
어떤 파라미터가 고려되고 해시맵은 어떻게 테스트됩니까?에서와 같이 해시맵이 완료되었다고 말하기 전에 실행하는 벤치마크 테스트 케이스는 무엇입니까?
기본만 알면 어렵지 않을 거예요.
일반적으로 키와 값을 포함하는 "버킷"이라는 어레이를 만들고 옵션 포인터를 사용하여 링크 목록을 만듭니다.
키를 사용하여 해시 테이블에 액세스하면 정수를 반환하는 커스텀 해시 함수로 키를 처리합니다.그런 다음 결과 계수를 구하면 배열 인덱스 또는 "버킷"의 위치가 됩니다.그런 다음 저장된 키로 삭제되지 않은 키를 확인하고 일치하는 경우 올바른 위치를 찾은 것입니다.
그렇지 않으면 "충돌"이 발생하여 링크된 목록을 탐색하고 일치할 때까지 키를 비교해야 합니다(일부 구현에서는 충돌에 링크된 목록 대신 이진 트리를 사용합니다).
다음 고속 해시 테이블 구현을 확인하십시오.
https://attractivechaos.wordpress.com/2009/09/29/khash-h/
최선의 접근법은 예상되는 키 배포와 충돌 수에 따라 달라집니다.비교적 충돌이 적은 경우 어떤 방법을 사용하든 상관없습니다.많은 충돌이 예상될 경우 어떤 충돌을 사용할지는 확장 가능한 버킷 데이터 구조를 조작하는 비용과 재평가 또는 프로브 비용에 따라 달라집니다.
C의 해시맵 구현의 소스 코드 예를 다음에 나타냅니다.
해시맵의 주요 목적은 데이터 세트를 저장하고 고유 키를 사용하여 데이터 세트에 거의 일정한 시간 검색을 제공하는 것입니다.해시맵 구현에는 다음 두 가지 일반적인 스타일이 있습니다.
- 개별 체인: 버킷 배열이 있는 체인(링크 리스트)
- 오픈 어드레싱: 엔트리를 인접 슬롯에 배치하여 인덱스 충돌을 해결할 수 있도록 여유 공간을 할당한 단일 어레이입니다.
해시맵에 해시함수가 불량할 수 있는 경우, 사용되지 않을 가능성이 있는 슬롯에 스토리지를 사전 할당하는 것이 바람직하지 않은 경우, 또는 엔트리의 사이즈가 가변적일 수 있는 경우에는 별도의 체인을 사용하는 것이 좋습니다.이러한 유형의 해시맵은 부하계수가 1.0을 초과한 경우에도 비교적 효율적으로 기능할 수 있습니다.각 엔트리에 링크 리스트 포인터를 저장하기 위해 필요한 추가 메모리가 있는 것이 분명합니다.
오픈 어드레싱을 사용하는 해시맵은 부하계수가 특정 임계값(일반적으로 약 0.7) 미만으로 유지되고 상당히 양호한 해시함수가 사용되었을 때 잠재적인 성능상의 이점을 가집니다.이는 링크된 목록과 관련된 캐시 누락 및 많은 작은 메모리 할당을 방지하고 사전 할당된 연속 어레이에서 모든 작업을 수행하기 때문입니다.모든 요소를 반복하는 것도 비용이 적게 듭니다.단, 오픈어드레싱을 사용하는 해시맵은 이상적인 부하계수를 유지하기 위해 더 큰 사이즈로 재할당하고 재플래시해야 합니다.그렇지 않으면 퍼포먼스가 크게 저하됩니다.부하계수가 1.0을 넘는 것은 불가능합니다.
해시맵을 작성할 때 평가하는 주요 퍼포먼스 메트릭에는 다음과 같은 것이 있습니다.
- 최대 부하 계수
- 삽입 시 평균 충돌 횟수
- 충돌 분포: 불균일한 분포(클러스터링)는 해시 함수가 불량함을 나타낼 수 있습니다.
- 다양한 조작의 상대시간: put, get, 기존 엔트리 및 존재하지 않는 엔트리의 삭제.
다음은 제가 실시한 유연한 해시맵 구현입니다.충돌 해결을 위해 오픈 어드레싱과 선형 프로브를 사용했습니다.
https://github.com/DavidLeeds/hashmap
오버플로우를 처리하는 메커니즘은 오버플로우 엔트리의 단순한 링크 리스트 외에 많은 메모리를 낭비하는 메커니즘이 있습니다.
사용하는 메커니즘은 해시함수를 선택할 수 있는지 여부와 둘 이상의 가능한 선택을 할 수 있는지(예를 들어 충돌을 처리하기 위해 더블 해시를 구현하는 경우), 항목을 자주 추가할지 또는 맵이 채워지면 정적인지 여부, 항목을 삭제할지에 따라 달라집니다.
이를 구현하기 위한 가장 좋은 방법은 먼저 이러한 모든 매개 변수를 검토한 후 직접 코드화하는 것이 아니라 성숙한 기존 구현을 선택하는 것입니다.Google은 몇 가지 적절한 구현을 가지고 있습니다(예: http://code.google.com/p/google-sparsehash/).
언급URL : https://stackoverflow.com/questions/838404/implementing-a-hashmap-in-c
'programing' 카테고리의 다른 글
| Vue 구성 요소의 조건부 루트 태그 (0) | 2022.06.09 |
|---|---|
| String으로 변환/주조하는 방법 (0) | 2022.06.09 |
| 계산된 속성 Vue.js에서 데이터에 액세스하는 방법 (0) | 2022.06.09 |
| 스프링 부트 설정 및 2개의 데이터 소스 사용 (0) | 2022.06.09 |
| Vue.js - 동적으로 생성한 정의되지 않은 img 소스 변경 (0) | 2022.06.09 |