CODEWITHSUNDEEP
javadata-structureslinked-listhashmaptreemap
sdanzig
sdanzig

Reputation: 4500

Does the Java API or an open source library provide for a TreeMap-like data structure with constant-time lookup?

I get that a TreeMap has log(n) insertion and lookup runtime complexity. However, a HashMap pointing to nodes in a linked list will provide for the same runtime complexity, but also constant-time lookup, which is a pretty big advantage. However, you would have to implement the search/insert/delete functionality yourself. I'm wondering if something in Java or another open-source library provides this for you?

I do realize that TreeMap's red-black tree might be better suited than a HashMap in certain situations, but certainly constant time lookup with natural-ordering is preferable in others.

NOTE: I know LinkedHashMap provides a built-in linked list for insertion order, but I'm talking about maintaining natural ordering like a TreeMap would do.

Upvotes: 0

Views: 165

Answers (1)

OldCurmudgeon
OldCurmudgeon

Reputation: 65851

Only if your keys adhere to a pattern that you can take advantage of in the data structure.

A good example would be a TrieMap. See Wikipedia for a description and here for a discussion containing references to implementations.

I posted a Trie implementation here some time ago. Not sure how efficient it is but it works. I have certainly improved it since that post.

Upvotes: 2

Related Questions