현재 C로 프로그래밍 언어를 개발 중입니다. 사용자가 프로세스에서 성능을 저하시키지 않으면 서 숫자 인덱스가있는 "무제한"배열을 만들 수 있도록하고 싶습니다. 예를 들어, table [1000000000]은 이상적으로 사용 가능하지 않은 999,999,999 개 항목의 1,000,000,000 개 항목의 테이블에 대한 메모리 오버 헤드없이 즉시 생성하고 액세스 할 수 있습니다. 배열은 table [n]이 1 ≤ n ≤ 1000000으로 정의되었을 때도 잘 수행됩니다.해시 테이블을 사용하여 무제한 배열 만들기
이러한 배열 처리 시스템의 구현에 대한 제안 사항이 있습니까?
을 원하는 포인터를 사용하는 방법에 대한, 당신은 그것을 위해 요소의 수를 정의 할 필요가 없습니다 어떻게, 당신은 많은 요소를 위키 피 디아 문서에 언급 된 바와 같이, 이러한 수 추가 할 수 있습니다 연결된 목록으로 나타내야한다.
연속 된 인덱스에 대해 과도한 오버 헤드가 발생하지 않도록 링크 된 목록의 각 노드가 동적으로 할당 된 배열 일 수 있습니다.
당신이 직접 답변 해 준 것 같습니다. CMPH - C Minimal Perfect Hashing Library을보세요.
편집 :
아니면 배열의 실제 인덱스에 정수를 매핑 할 B+ Tree를 사용할 수 있습니다. B Trees을 사용하면 또 다른 이점이 있습니다. 범위 쿼리를 만들 수 있습니다.
이미 완벽한 해시 함수가 있습니다.이 경우 인덱스입니다. – Hasturkun
완벽한 해시 함수가 미리 키를 알고 있어야합니다 (예 : 월을 1 월 ... 12 월 1 ... 12로 매핑)? –
당신은 당신은 Sparse Array을 만들
이론적으로는 가능하다고 생각합니다. 당신이 필요로하는 것은 매우 좋은 해싱 알고리즘 (충돌을 피하기 위해)입니다. 그래서 누군가가 테이블을 말하는 경우 [100..0]; 공간을 한 번에 할당 할 필요가 없습니다. 필요에 따라 공간을 할당하십시오. 그래서 테이블 [100..0]에 있다면 처음 5 개의 값을 채우려고합니다. 그 5 개의 값만 저장하려고합니다. 그러면 테이블에 액세스하려고하면 'undef'와 같은 것을 얻을 것입니다. 또는 '전무'...
내가 테스트하지 않았습니다하지만 the_void 언급 라이브러리가 ... 좋은 것 같다 ...
:이 cmph를 사용 주디 배열 http://judy.sourceforge.net/
의는하지 않습니다 도움. 완벽한 해시 함수를 만들기 위해서는 모든 키를 미리 알아야합니다.
원하는 것은 희소 배열을 구현할 수있는 간단한 연관 매핑 구조입니다. 모든 해시 테이블 또는 트리 구조가 수행합니다. hash_map을 사용하거나 C++ stl 구현 또는 유사한 데이터 구조의 상자에서 즉시 매핑 할 수 있습니다.
당신이 멋지게 지내기를 원한다면 Judy Array를 사용할 수 있습니다 만, 올바르게 벤치마킹 할 수 있고 특정 유스 케이스에 대한 가정을 수행하는 좀 더 복잡한 데이터 구조를 고려하지 않으면 어떤 차이가 있는지 의심 스럽습니다. .
간단한 일을하십시오. 가장 쉬운 가용 해시 테이블이 가장 좋은 대답입니다. 해시 함수 등을 생각하지 마십시오. 플랫폼이 제공하는 것이 무엇이든간에 충분히 잘 작동합니다.
스파 스 어레이는'O (N)'-'N' 개의 실제 아이템 ('www .itl.nist ')의'get/set' 복잡성으로 더 비효율적 일 수 있습니다.gov/div897/sqg/dads/HTML/hugeSparseArray.html) –
왜 downvote? 지금까지 내가 희소 배열이라고 말할 수있는 한, @the_void에 링크 된 구현을 제안하는 것이 아니라, 시간이 지남에 따라 통일 될 수있는 배열의 링크 된 목록으로 제안했습니다 – Hasturkun