로그 읽기 복잡도가있는 시간 소인 기반 정렬 된 데이터 구조

Question

Java에서 좋은 정렬 된 데이터 구조를 찾고 있습니다. 몇 가지 연구를 한 후에 TreeSet/TreeMap 사용에 대한 힌트가 거의 없습니다. 그러나 이러한 구성 요소는 집합에서 요소에 임의 액세스 할 수 없다는 단점이 있습니다. 예를 들어, 정렬 된 집합의 n 번째 요소에 액세스하려고하지만 TreeSet을 사용하면 거기에 도착하기 전에 다른 n-1 요소를 반복해야합니다. 내 세트에 수천 가지 요소가 들어 있기 때문에 낭비 일 것입니다.

유스 케이스는 내가 항상 사용자가 최신 편집 된 제목을 표시 할

9:20 AM what is this object? edited by user1 
9:30 AM what is this book ? edited by user2 
9:40 PM what is this red book? edited by user1 

이하 같다. 나는 최신이 가장 큰 타임 스탬프를 가지고있을 것이라는 것을 안다. 이것을 위해 나는 ConcurrentSkipListSet/Maps가 좋다는 것을 알았다. 그러나이 기능을 구현하는 더 좋은 방법이 있는지 알고 싶습니다.

Answer 1

데이터 정렬을 유지한다고 가정 할 때 가장 좋은 방법은 TreeMap입니다. 정렬 된 컬렉션 인 은색 글 머리 기호가없고 O(1) 임의 액세스를 수행합니다. 순서가 지정된 컬렉션에서는 인덱스가있는 요소에 직접 액세스 할 수 있지만 콜렉션을 정렬해야하는 경우 인덱스 기반 액세스의 이점을 누릴 수 없습니다.

동시성이 필요한 경우 ConcurrentSkipListMap이 좋습니다. 데이터에 대한 대규모 동시 액세스에 적합합니다. 그러나 퍼포먼스면에서 Red-Black tree 기반의 친구 인 TreeMap과는 일치하지 않습니다. 따라서 동시성이 필요하지 않은 경우 ConcurrentSkipListMap을 잊어서 TreeMap을 붙이십시오.

TreeMap은 귀하의 요구를 만족시킵니다. 그럼에도 불구하고 실제로는 HashMap을 사용하고 필요할 때마다 데이터를 정렬하는 것이 더 나을 수도 있습니다. 둘 다 시도해보고 어떤 것이 더 나은지 알아보십시오.