Есть ли структура данных для этого типа списка / карты?

22

Возможно, есть название для того, что я хочу, но я не знаю об этом. Мне нужно что-то похожее на a LinkedHashMapв Java, но где он возвращает «предыдущее» значение, если в указанном ключе нет значения.

То есть у меня есть список объектов, хранящихся с помощью целочисленного ключа (в моем случае это единицы времени):

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

Итак, если бы я запросил значение для ключа 0-9, он бы вернулся null. Особая часть состоит в том, что если бы я запросил что-то 10 <= i <= 14, он вернул бы A. Или, для i> = 20, он вернул бы C.

Есть ли структура данных для этого?

java data-structures Ник
источник
Я не знаю, есть ли реализованный, но вы могли бы расширить существующий для этого. Будет ли это соответствовать вашим целям производительности или нет без переписывания, я не знаю ...
Rig
1
+1 за отличный вопрос. Большинство людей с тремя младшими цифрами задают вопрос типа «пожалуйста, сделайте мою домашнюю работу». Здесь не тот случай.
Tulains Córdova

Ответы:

33

Вы ищете NavigableMap . Это подтип SortedMap, который также имеет некоторые функции, помимо характера сортируемой карты. Обратите внимание, что карта Navigable «предназначена для замены интерфейса SortedMap». ( Java SE 6 Collections Framework Расширения ). Все, что в настоящее время реализует, SortedMapреализует, NavigableMapи это, вероятно, останется верным.

В частности, метод, floorKey(K key)который «возвращает наибольший ключ, меньший или равный данному ключу, или ноль, если такого ключа нет.

Это только один из многих методов, которые позволяют вам получить определенные ключи или подкарты карты.

  • потолок / пол (запись выше / ниже параметра)
  • доступ к ключам или карте в порядке убывания
  • голова / хвост (записи меньше / больше, чем данный ключ)
  • выше / ниже (следующий ключ, который выше или ниже, чем параметр)
  • подкарта (дано два ключа, вернуть карту, которая находится между двумя ключами)

В Java есть две реализации NavigableMap - TreeMap и ConcurrentSkipListMap .

Если вы посмотрите на идею / реализацию пропускающего списка, вы поймете, почему он действительно хорошо работает с такой структурой и ее запросами.


источник
1+ отличный ответ. Никогда не думал, что такая специфическая Карта существует в Java API.
Тулаинс Кордова
@ user61852 Мой любимый тип данных - это список пропусков, и я возился с ним. Когда я увидел, что он реализован в 1.6, я изучил все, что он предоставил, и заметил, какие интерфейсы у него были, и, таким образом, мое знакомство с ним.
Именно такие вещи убеждают меня, что Java - один из лучших языков, которые вы можете найти.
Тулаинс Кордова
1
Обратите внимание, что хотя это, кажется, решает проблему OP, оно не действует так, как LinkedHashMapон упоминает. Ни , TreeMapни ConcurrentSkipListMapупорядочены по времени введения , как LinkedHashMap, скорее , они упорядочиваются по Comparatorили в ключе естественного порядка , если они реализуют Comparable.
MikeFHay
1
Очень хороший момент. Этаж работы - это то, что я искал, компаратор, который я могу легко добавить. И в моем случае гораздо лучше внедрить компаратор, а не изобретать велосипед. Спасибо.
Ник
1

То, что вы ищете, это таблица символов, которая поддерживает упорядоченные операции. А в вашем случае это напольная операция.

Хеш-реализация таблицы символов является самой быстрой, но она не предлагает эти упорядоченные операции.

Но древовидная реализация таблиц символов делает. Примером этого в Java является класс TreeMap

Моха всемогущий верблюд
источник