Найдите "ближайший ключ с плавающей точкой" в HashMap по значению Float
Есть LinkedHashMap<Float, Integer>
, Ключи этого HashMap - это точки во времени в секундах (например, 0.031f
или же 1.4021f
). Там могут быть сотни тысяч записей.
Учитывая float
ценность, скажем 0.6102f
Мне нужно найти ключ HashMap, который находится ближе всего к нему (например, 0.6002f
возможно, при условии, что это в наборе ключей).
Тривиальным ответом будет проверка ключа по ключу HashMap. В конце концов, записи оказываются правильно отсортированы. Но я думаю, что это O(n)
операция, которая не может быть хорошей идеей, учитывая, что я должен выполнять этот поиск несколько раз в секунду.
Есть ли эффективный способ найти "ближайший ключ с плавающей точкой" HashMap, заданный с плавающей точкой?
1 ответ
Нет эффективного способа сделать это, используя HashMap
; т.е. ничего лучше O(N)
где N
количество записей на карте.
Однако, если вы переключитесь на использование TreeMap<Float, Integer>
Вы можете найти запись с ближайшим ключом в O(logN)
, Вам нужно использовать floorEntry
а также ceilingEntry
и затем проверьте, какой из 2 ключей ввода находится ближе всего к вашему заданному ключу.
В конце концов, записи оказываются правильно отсортированы.
На самом деле ключи в HashMap
не отсортированы. hashCode()
реализации некоторых ключевых типов могут показаться, что HashMap
ключи отсортированы, но то, что вы видите, это артефакт.