저장 및 해시하는 가장 좋은 방법 키 (C++)

Question

저의 목표는 (메모리 제한이없는 세계에서) 약 10^5 x 10^5 인 행렬의 가장 관련있는 항목을 저장하는 효율적인 구조를 만드는 것입니다 복식으로 채워진다. 행렬은 대칭이므로 실제로 (10^10)/2 값만 포함합니다.

시뮬레이션에서 여러 번 항목에 액세스해야하므로 빠른 검색이 중요합니다.

구조를 관리하기 쉽게하기 위해 사용하지 않을 수있는 멤버를 삭제합니다. 색인이 (int_x1, int_x2) 인 경우, 예를 들어 x1을 포함하는 모든 쌍을 삭제하려는 경우가 있습니다.

이 작업에 가장 적합한 구조 또는 구조 집합은 무엇입니까? 두 int에 대한 좋은 해시는 무엇입니까?

휴대 성을 위해 Boost를 피하고 싶습니다. 현재 TR1의 unordered_map을 프로그램의 다른 곳에서 사용하고 있습니다. 나는 키 쌍으로 unordered_map을 다시 사용하려고 생각하고 있었지만이 방법으로 항목을 효율적으로 삭제할 수 있을지 잘 모르겠다. 좋은 해시 함수가 어떻게 생겼는지 모르겠다.

저는 시작 프로그래머입니다. 따라서 분명히 말씀해주십시오.

Answer 1

데이터가 매우 희박한 경우 해시 테이블 배열을 사용할 수 있습니다.

hash_map<int,double> matrix[] = new hash_map<int,double>[10000]; 
for (int i = 0; i < 10000; i++) matrix[i] = new hash_map<int,double>(); 

그런 다음 값 (x, y)을 찾으려면 배열을 x로 인덱싱하고 해시 테이블에서 y를 찾습니다. 조심하는

몇 가지 : 당신이 해시 테이블의 많은 반복을 가지고

• 삭제가 꽤 비싼 얻을 수 있습니다.
• 삭제/삽입 할 때 총 저장 용량이 커질 수 있으므로 때때로 hash_maps를 trim()해야합니다.
• 대칭을 이용하는 것이 쉬워야합니다.