Найдите "ближайший ключ с плавающей точкой" в HashMap по значению Float

Question

Есть LinkedHashMap<Float, Integer>, Ключи этого HashMap - это точки во времени в секундах (например, 0.031f или же 1.4021f). Там могут быть сотни тысяч записей.

Учитывая float ценность, скажем 0.6102fМне нужно найти ключ HashMap, который находится ближе всего к нему (например, 0.6002f возможно, при условии, что это в наборе ключей).

Тривиальным ответом будет проверка ключа по ключу HashMap. В конце концов, записи оказываются правильно отсортированы. Но я думаю, что это O(n) операция, которая не может быть хорошей идеей, учитывая, что я должен выполнять этот поиск несколько раз в секунду.

Есть ли эффективный способ найти "ближайший ключ с плавающей точкой" HashMap, заданный с плавающей точкой?

Answer 1

Нет эффективного способа сделать это, используя HashMap; т.е. ничего лучше O(N) где N количество записей на карте.

Однако, если вы переключитесь на использование TreeMap<Float, Integer> Вы можете найти запись с ближайшим ключом в O(logN), Вам нужно использовать floorEntry а также ceilingEntry и затем проверьте, какой из 2 ключей ввода находится ближе всего к вашему заданному ключу.

---

В конце концов, записи оказываются правильно отсортированы.

На самом деле ключи в HashMap не отсортированы. hashCode() реализации некоторых ключевых типов могут показаться, что HashMap ключи отсортированы, но то, что вы видите, это артефакт.