0

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.

sdanzig
  • 4,510
  • 1
  • 23
  • 27
  • http://stackoverflow.com/questions/460088/is-there-a-java-hash-structure-with-keys-only-and-no-values – Florian Groetzner Nov 26 '13 at 16:38
  • Does a linking hash map provide constant time look-up? That doesn't sound correct to me. Doesn't it has a O(N) worst case on all operations? – Justin Nov 26 '13 at 16:38
  • i think it has O(N) worst case but correct me if im wrong http://stackoverflow.com/questions/8162501/worse-case-time-complexity-put-get-hashmap – Florian Groetzner Nov 26 '13 at 16:40
  • Also, does a linking hash map doesn't provide a natural ordering iteration between buckets. I wouldn't think so. – Justin Nov 26 '13 at 16:40
  • @Dlotan Yea, you are correct. It was a mis-type :-) – Justin Nov 26 '13 at 16:41
  • I'm not referring to a LinkedHashMap, which I think you were referring to... that only provides insertion order. I'll add clarification. – sdanzig Nov 26 '13 at 16:44
  • @sdanzig No, I wasn't referring to a linked hash map. I was referring to a hash map where each bucket is a linked list. Isn't that what you are referring to also, or am I wrong? – Justin Nov 26 '13 at 16:47
  • @Justin Nope, meant each bucket, optimally, has a single node in a linked list. – sdanzig Nov 26 '13 at 16:50

1 Answers1

2

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.

Community
  • 1
  • 1
OldCurmudgeon
  • 64,482
  • 16
  • 119
  • 213
  • Not quite constant time operations. – Justin Nov 26 '13 at 16:49
  • 2
    @Justin - `O(M)` lookup which is arguably constant if your keys *adhere to a pattern* of being constant length. – OldCurmudgeon Nov 26 '13 at 16:51
  • Agreed, just wanted to make sure that information was included. – Justin Nov 26 '13 at 17:00
  • A space efficient radix trie implementation I've written: http://github.com/phishman3579/java-algorithms-implementation/blob/master/src/com/jwetherell/algorithms/data_structures/PatriciaTrie.java – Justin Feb 02 '16 at 21:33