기본 유형에 매핑하기위한 HashMap의 빠른 대안은 무엇입니까?

Question

우선 먼저 Java HashMap performance optimization/alternative 전에 물어 본 다음 질문을 읽었으며 비슷한 질문이 있습니다.

내가하고 싶은 일은 stanford 파서가 의존성을 부여하고 종속성을 점수와 함께 저장하도록 New York 타임 텍스트에서 많은 의존성을 취하는 것입니다. 즉, 종속성을 두 번 볼 수 있습니다. 해시 맵에서 점수를 1 씩 증가시킵니다.

작업은 초당 약 10 문장으로 시작하지만 빠르게 저울질됩니다. 30,000 문장 (각 문장에서 10 단어를 가정하고 저장하는 각 단어에 대해 3-4 가지 종속성을 가짐)은 내 해시 맵에서 약 300 000 개의 항목입니다.

어떻게하면 해시 맵의 성능을 향상시킬 수 있습니까? 어떤 종류의 해시 키를 사용할 수 있습니까?

덕분에 많은 Martinos

편집 1 :

확인 녀석 어쩌면 내가 아니라 바이트 배열은 내 프로젝트에 있지만, 위의 다른 사람의 비슷한 질문에 사용되지 않는, 내 질문이 잘못 확인을 표현한. 나는 그들이 왜 그렇게 물었는지 그걸 위해 그것을 사용하고 있는지 모르겠다.

는 둘째 :

문장으로

이 : 내가 그것을 이해하는 일을 열심히 할 것입니다 생각하지만, 여기에 샘플이기 때문에 내가 코드를 게시하지 않습니다 (I : "나는 침대에 갈거야"내가 종속성이 오전, -1) (i, going, -2) (i, ~,) (am, going, -1) . . . (to, bed, -1) 모든 문장 (1 000 000 문장)의 이러한 종속성은 해시 맵에 저장됩니다. 만약 내가 의존성을 두 번 보면 나는 기존 의존성의 점수를 얻고 1을 더할 것입니다.

그리고 그것은 꽤 많이 있습니다. 모든 것이 잘되지만 해시 맵 (또는 검색)에서 문장을 추가하는 비율은 다음 줄로 축소됩니다. dependancyBank.put (newDependancy, dependancyBank.get (newDependancy) +1); 누구나 그 이유를 말해 줄 수 있습니까? 감사합니다. Martinos

Answer 1

Trove은 키 또는 값이 기본 유형 인 경우 최적화 된 해시 맵을 제공합니다.

그러나 키의 구조와 해시 코드의 현명한 선택에 따라 많은 부분이 달라집니다.

이 부분은 분명하지 않습니다. The task starts off really quickly, about 10 sentences a second but scales off quickly. At 30 000 sentences(which is assuming 10 words in each sentence and about 3-4 dependences for each word which im storing) is about 300 000 entries in my hashmap.. 그러나 더 큰 데이터에 대한 성능이 무엇인지는 말하지 않습니다. 귀하의지도가 커지며 이는 분명합니다. 해쉬 맵은 이론적으로 만 O(1)입니다. 실제로는 캐시 지역이 적기 때문에 크기에 따른 성능 변화가 발생할 수 있으며, 다시 해싱으로 인한 점프가 발생할 수 있습니다. 따라서 put() 및 get() 시간은 일정하지 않지만 여전히 그 값에 가깝습니다. 아마도 빠른 액세스를 보장하지 않는 방식으로 해시 맵을 사용하고있을 것입니다. 그것을 반복함으로써? 이 경우 크기가 선형 적으로 증가하고 알고리즘을 변경하지 않으면 변경할 수 없습니다.

Answer 2

Google 'fastutil'을 사용하면 객체 키를 점수에 매핑하는 우수한 솔루션을 찾을 수 있습니다.

Answer 3

구아바 멀티 맵 : http://www.coffee-bytes.com/2011/12/22/guava-multimaps 기본적으로 모든 키가 동일한 키에 매핑되는 목록을 유지하도록 설계되었습니다. 그것은 당신의 필요를 해결할 수도 있습니다.

Answer 4

어떻게하면 해시 맵의 성능을 향상시킬 수 있습니까?

get() 또는 put() 당 1 초 이상 걸릴 경우 IMHO 버그가 있습니다. 왜 오래 걸릴지 결정해야합니다. 모든 객체의 hasCode가 같은 최악의 경우에도 성능이 떨어집니다.

어떤 종류의 해시 키를 사용할 수 있습니까?

이는 키의 데이터 유형에 따라 다릅니다. 이게 뭐야?

그리고 마지막으로 byte [] a = new byte [2]; byte [] b = 새로운 바이트 [3]; 위에 게시 된 질문에?

바이트 배열입니다. 조회 할 값으로 사용할 수 있지만 다른 값 유형이 필요할 수 있습니다.

Answer 5

HashMap에는 초기 용량을 입력으로 사용하는 오버로드 된 생성자가 있습니다. 당신이 볼 스케일은 HashMap을 거의 사용할 수없는 재 해싱 (rehashing) 때문입니다. 다시 해싱을 자주하지 않으려면 더 큰 초기 용량의 HashMap부터 시작해야합니다. 다시 해싱하기 전에 해시를로드하는 비율을 나타내는로드 요소를 설정할 수도 있습니다.

public HashMap(int initialCapacity).

개체 생성 중에 초기 용량을 HashMap에 전달합니다. 프로그램을 실행하는 동안 맵에 추가하려는 요소 수의 거의 두 배에 이르는 용량을 설정하는 것이 좋습니다.