Частенько начал натыкаться на необходимость получать по нужному ключу соответствующее значение и наоборот. Для этого приходится использовать что-то вроде этого:
HashMap<String, Integer> hm1;
HashMap<Integer, String> hm2;
Такой вариант меня чаще всего не устраивает по затратам памяти и "лишней" возне с двумя таблицами.
А есть ли какая-то структура данных (встроенная в JAVA), которая позволяет производить такие запросы сохраняя сложность запроса O(1) ?
А если нет встроенной, то какие есть?
Благодарю.
Казалось бы, тут нужно как минимум ограничение на два одинаковых значения в hm1, которые превратятся в два одинаковых ключа в hm2.
А, в общем случае, выйдет какая-то фигня.
http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/HashBiMap.html
Я всегда писал так, как написано в посте, и никогда не ловил себя на мысли, что мне нужно что-то удобнее. Вроде бы и так удобно. И насчет памяти это странно, т.к. везде 256 МБ давно стоит.
Еще если ключи от 0 до size-1, вторую мапу можно превратить в массив, например, такое часто случается при сжатии координат.
Кстати, возник вопрос по поводу сжатия координат.. точнее "сжатие" двух значений типа double в одно. Представим, что пишем бфс на яве по плоскости на которой отмечены точки с действительными координатами, плоскость большая (точек много). Хранение в очереди Pair(double x, double y) получает TLE, использование 2х очередей не рассматриваем (или всё же?).
Каким образом ускорить процесс? (надеюсь вопрос понятен)
Если бы координаты были целочисленными и скажем от 0 до 10000 (примерно), то можно было x и y (+ еще и расстояние от текущей точки) закодировать так:
и в итоге хватило бы одной очереди.
Вроде видел такой метод:
1. Когда кладём значения -- положим сначала Х, потом Y;
2. Когда вытаскиваем -- вытащим Х и Y(в нужном порядке, работает так же и для стека).
А вообще чем плохо хранить в очереди индекс точки в массиве(всё равно они где-то ведь хранятся)?
Интересный вариант. Берем на заметку. Спасибо.
Так дело в том, что точки-то не хранятся нигде. Генерируешь БФСом новые точки, нашел точку подходящую — выполнил какое-то действие, нет — идем дальше.
недавно сталкивался с сабмитом как раз с такой очередью — http://codeforces.com/contest/199/submission/1818705 не уверен, что это как-то особо отражается на времени выполнения, на Яве по крайней мере.
Скинь ссылку на эту задачу c точками, вдруг там вовсе не БФС (:
Стандартной структуры нет, но вроде несложно написать самому, унаследовавшись от HashMap и перегрузив put, remove и добавив пару своих методов. При этом внутри понадобится дополнительная хеш-мапа, без этого никуда
А зачем наследоваться от HashMap, если по сути своей данное решение равносильно созданию просто нового класса с соответствующим функционалом (двумя хэш-мапами) ?
Не совсем понял вопроса. Так мы внешне пользуемся мапой, как будто это обычная мапа с парой дополнительных методов. Если не наследоваться, то нам придется делигировать всю толпу методов, определенных интерфейсом Map (если мы хотим что-то универсальное сделать, конечно)
Теперь понятно. Изначально в вопросе я имел ввиду такой способ:
ну, просто придется не только перегружать put и remove, как в моем варианте, но и делегировать 100500 методов. Кстати, хорошей идеей будет будет создать интерфейс BiMap (наследник Map) и класс BiHashMap extends HashMap implements BiMap — когда потом понадобится BiTreeMap это поможет