Java에서 HashTable의 사용자 정의 구현?

Question

나는 Quora problem을 해결했으며 값을 캐싱하기 위해 해시 테이블 (long-keys, int-values)이 필요했습니다. 키와 값에 대한 데이터 유형을 알았 기 때문에 자바 HashMap을 개선 할 수 있었으면 좋겠다. 원시와 문제 공간이기도하다. 순진하게도 "array-of-linkedlist"구조 (심지어 내 linkedList는 구현 한 Node 클래스)를 사용하여 간단한 해시 테이블을 구현하기로 결정했습니다. 그러나 내 자신의 순진 구현은 일반적인 Java HashMap보다 약 4 배 느린 것으로 나타났습니다. 또한 그들이하는 일을보기 위해 Trove's LongToIntMap 라이브러리를 사용하려고했습니다. 누구든지 Java HashMap보다 훨씬 뛰어난 Java에서 사용자 정의 Long to Int 해시 테이블을 작성하는 좋은 제안이 있습니까?

Answer 1

Javolution의 FastMap을 살펴보십시오. 소스 코드는 here입니다.

Answer 2

또한 Trove의 LongToIntMap 라이브러리를 사용하여 무엇을하는지 확인하려고했습니다.

코드를보고 어떻게 해 보았습니까?

---

코드를 보지 않고 구현에서 잘못한 부분이 무엇인지 확실히 말할 수는 없습니다. 그러나 한 가지 가능한 개선 사항은 LinkedList<Integer>을 int[]을 사용하여 목록을 나타내는 사용자 지정 "정수 목록"유형으로 바꿀 수 있습니다. 해시 테이블 API에 따라 값을 개체로 표시하는 비용을 피할 수 있어야합니다 (특히 Integer 초). (키 및/또는 값 유형에 대한 제네릭 형식을 가진 API를 구현하지 않아도 성능과 공간 활용도가 향상됩니다.)

가난한 사람에게는 성능이 해시 테이블 크기 조정을 구현하는 것을 무시하고 있습니다. 크기를 조정하지 않으면 테이블의 get 및 put 연산의 복잡도가 O(1)이 아닌 O(N)이됩니다. 해시 체인 길이가 해시 테이블 항목의 수에 비례하여 커지기 때문에.

마지막으로 성능 또는 공간 활용을 위해 최적화하고 있는지 여부를 명확히 밝혀야합니다. 최적의 솔루션은 달라질 것입니다 ....