이 유형의 목록 / 맵에 대한 데이터 구조가 있습니까? 원하는 것에 대한 이름이 있을지

아마도 내가 원하는 것에 대한 이름이 있을지 모르지만 나는 그것을 모른다. LinkedHashMapJava 와 비슷한 것이 필요 하지만 지정된 키에 값이 없으면 ‘이전’값을 반환합니다.

즉, 정수 키 (내 경우에는 시간 단위)로 저장된 객체 목록이 있습니다.

; key->value
10->A
15->B
20->C

따라서 0-9 키의 값을 쿼리하면을 반환 null합니다. 특별한 부분은 내가 10 <= i <= 14를 쿼리하면 A를 반환하거나 i> = 20의 경우 C를 반환하는 것입니다.

이에 대한 데이터 구조가 있습니까?

답변

당신은 NavigableMap을 찾고 있습니다. 이것은 SortedMap의 하위 유형이며 정렬되는 맵의 특성 외에 몇 가지 기능을 사용할 수 있습니다. 탐색 가능 맵은 “SortedMap 인터페이스를 대체하기위한 것입니다.” ( Java SE 6 Collections Framework 향상 ). 현재 구현 SortedMap하고있는 모든 것이 구현 NavigableMap될 가능성이 높습니다.

특히, floorKey(K key)“가장 큰 키를 주어진 키보다 작거나 같은 방법 으로 반환하거나 그러한 키가없는 경우 null을 반환하는 방법입니다.

이것은 특정 키 또는 맵의 서브맵을 얻을 수있는 많은 방법 중 하나입니다.

  • 천장 / 바닥 (매개 변수보다 높거나 낮은 항목)
  • 내림차순으로 키 또는 맵 액세스
  • 머리 / 꼬리 (주어진 키보다 작거나 큰 항목)
  • 높음 / 낮음 (매개 변수보다 높거나 낮은 다음 키)
  • 서브맵 (두 키가 주어지면 두 키 사이에있는 맵을 리턴)

Java에는 NavigableMap의 두 가지 구현 ( TreeMap 및 ConcurrentSkipListMap)이 있습니다.

건너 뛰기 목록 의 아이디어 / 구현을 보면 왜 그러한 구조와 쿼리에서 제대로 작동하는지 알 수 있습니다.

답변

찾고있는 것은 순서가 지정된 작업을 지원하는 기호 테이블입니다. 그리고 귀하의 경우 그것은 바닥 작업입니다.

기호 테이블의 해시 구현이 가장 빠르지 만 순서가 지정된 작업은 제공하지 않습니다.

그러나 심볼 테이블의 트리 구현은 그렇지 않습니다. Java의 예로는 TreeMap 클래스가 있습니다.

답변