0

I'm not sure how to search for or properly phrase this, so if there's duplicates, please forgive me.

What I'm thinking is:

Using a sorted integer-key map, I would like to access it with a key that isn't currently used:

someMap = {1 -> "one", 4 -> "four", 5 -> "five"}

someMap.get(2) == "one"

(Edit: for clarity, I'm only concerned about interacting with the keys themselves. The actual data the keys are pointing to is irrelevant to this question.)

Coming from java, I'd expect to implement some sort of Comparator to explicitly define how to choose the closest (or from other criteria) element -- but I'd be curious to hear about other ways of doing this (bit shifts?).

Todd Schwine
  • 101
  • 1
  • Welcome to SO! Are you asking for a specific language based on "coming from Java"? My first thought is if you have a sorted list, you can binary search it or use a BST to get closest matches. BST is still pretty fast but O(n log(n)) but for insertion and for retrieval rather than O(1), unfortunately. – ggorlen Jan 07 '19 at 23:47
  • Thanks! The java comment was more for clarity on suggesting a comparator in java code, as I'm sure C programmers might get their swords ready otherwise. I'll look into using a BST now. – Todd Schwine Jan 07 '19 at 23:50
  • Possible duplicate of [Hashing a range](https://stackoverflow.com/questions/3516351/hashing-a-range) – ggorlen Jan 08 '19 at 00:09
  • I think [Data structures that can map a range of keys to a value](https://stackoverflow.com/questions/13399821/data-structures-that-can-map-a-range-of-keys-to-a-value?rq=1) has the answers I'm looking for – Todd Schwine Jan 08 '19 at 00:26
  • Are you looking for something like [`TreeMap.floorKey`](https://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html#floorKey(K))? (or `floorEntry`)? – Lee Jan 08 '19 at 00:28
  • @Lee I may need to play around with it to be sure but at a glance it looks like it's exactly what I'm after – Todd Schwine Jan 08 '19 at 00:32
  • Funny that the most recent question (before yours) in the data-structures tag is https://stackoverflow.com/q/54082701/56778, which is essentially the same question. – Jim Mischel Jan 08 '19 at 05:14

0 Answers0