데이터 구조 제안!

Question

나는이 데이터 구조에 대한 다음과 같은 요구 사항 :

키의 도움으로 요소에
1. 직접 액세스
2. 않도록 메모리 할당 (정수 될 것입니다 키, 범위도 정수 범위와 동일) 청크
3. 동적

가 어떤 데이터 구조는 제안 데이터 구조의 크기를 확장 할 수 있어야한다 (데이터를 포함하는 데이터 구조에 대한 인접하게 메모리를 할당)?

방향의 포인터도 도움이 될 것입니다.

Answer 1

나

Answer 2

1) 스파 스 배열에 hash table (일명 사전) 같은 소리
2,3) 힙

당신은 기본적으로 하나의 큰 버퍼를 공유 힙 및 스파 스 배열을 구현해야합니다 . 일반적으로 스파 스 어레이에 저장된 값은 포인터입니다. 귀하의 경우 포인터는 힙의 기점에 상대적입니다. 그렇지 않으면 오프셋으로 알려져 있습니다. 힙은 큰 버퍼의 희소 배열 앞에 있어야하므로 힙 크기를 조정해도 오프셋이 변경되지 않습니다.

일반적으로 이와 비슷한 단계는 병합 단계로 수행됩니다. 즉, 정상적인 해시 테이블 또는 희소 배열은 하나의 인접한 블록으로 모두 필요한 지점까지 시스템 관리 포인터와 함께 사용됩니다. 이 시점에서 모든 것이 다른 형식으로 압축되고 나중에 다시 확장됩니다.