0

What I'm Doing

I'm utilizing maps in alot of my code and I find that for efficient sorting and searching, maps are very useful. I like using them because they are the most efficient thing I can think of, being instant lookup.

The problem is

I have alot of things that are simply stored as Strings that I want to be able to look up later. I don't need to store any additional information with these Strings I mostly just want to be able to make a collection where Strings are stored and I can look them up instantly. For example a list of names (I'm using a lot of reflection so having the names of class parameters is an example of what I'm doing.) My question is this, Is there a different collection that allows me to look up the Strings in it without having to store a "value?". I keep making maps where the Key is the value I.E. Map<String,String> where String key = String value and this seems like a waste of memory. I just want the key anyways there is no need to store a copy of what I want. Surely there must be some functionality I'm not thinking of. I tried a google search for "is using a hashmap with keys that are their values a bad idea?" and I tried searching similar things on stack overflow. Nothing related to this specific problem maybe because I'm being silly and using the wrong thing to store my strings. Either way, the goal is to have a collection that uses less space to hold Strings I can look up. a Hashmap that doesn't have a value because the key is the value. If the key being equal to the value doesn't actually affect the amount of memory used then thats fine but I would think that it does.

ideas of mine

would making a Map<String,null> work? maybe somehow I could just get the key and since the value would be null that would not use up any extra memory space? I don't know how I would find out what affects memory space and what doesn't.

Community
  • 1
  • 1
Redacted
  • 613
  • 6
  • 23
  • 4
    You could probably use a `HashSet` which uses a `HashMap` internally – Lino Jul 23 '18 at 13:41
  • don't those still have a "value" though? EDIT nvm, googled hashset and I think you're right – Redacted Jul 23 '18 at 13:41
  • The current (java 8) `HashSet` implementation uses a static `Object` as a value, so all the entries have different keys, but the same value, so finally no big memory footprint – Lino Jul 23 '18 at 13:42
  • "being instant lookup" They aren't. How could they be? – Alexey Romanov Jul 23 '18 at 13:43
  • As @AlexeyRomanov points out, there is no theoretical basis to an instant lookup. The lookup is indeed fast (could be `O(log n)` I think), but it isn't exactly instant. – Neo Jul 23 '18 at 13:44
  • No I mean the look up not the iteration. the lookup of one value is O(log 1) because i can just call Map.get(key) rather than seach through an arraylist. Sorry if the wording was unclear – Redacted Jul 23 '18 at 13:45
  • @Redacted probably meant O(1) instead of O(log 1), because that's O(0) – Lino Jul 23 '18 at 13:46
  • Also currently it is kind of unclear why you're using those `Map`s. When having the same key as value, what is the sense behind this, because for the lookup you'd already need the key, so the lookup is completly useless – Lino Jul 23 '18 at 13:49
  • The use of this is to compare strings faster. I have a collection that can look up Strings in O(1) time so if I have a seperate list of strings that I want to see if theyre in the map then I just call map.get(). Otherwise Id have to use a binary search or worse a linear search of two arrays doing something like: if(String expected.equals(String actual)){//do stuff}; – Redacted Jul 23 '18 at 13:51
  • @Redacted Using a function someone else wrote doesn't make it of a lower complexity. I could write a piece of code to search in a 2d array and wrap it in a function but it won't make the operation `O(1)` instead of `O(m * n)` – Neo Jul 23 '18 at 13:51
  • I'm confused. I understand that adding elements to a Map when constructing it is O(n) and looking them up is O(1). What I'm doing is collection comparison in O(n) time by using a map after its constructed. I'm trying to avoid using binary search O(n log n) or a nested if statement with two arrays O(n^2). Thats all I'm trying to do. – Redacted Jul 23 '18 at 13:57
  • Where did you understand lookup time is O(1)? – Neo Jul 23 '18 at 13:58
  • Isn't map.get(element) one command? It should hash right to the value in the map right? I found it right here as an example [link]https://stackoverflow.com/questions/4553624/hashmap-get-put-complexity – Redacted Jul 23 '18 at 13:58
  • `callComplicatedCodeWhichRunsInPolynomalTime()` is also "one command". The internal implementation of `map.get` can't run on `O(1)`. It's just not possible. The O notation refers to the actual time it takes to do stuff, not to the amount of code the programmer needs to write – Neo Jul 23 '18 at 14:00
  • “this seems like a waste of memory.” You are prematurely optimizing. If the value is the same object as the key, the only memory used is a new *reference* to it—which is probably 256 bytes at most, or ¹⁄₄₀₉₆ megabytes. That said, I don’t understand why you aren’t simply using a Set. – VGR Jul 23 '18 at 14:13
  • alright welp. I was being silly and should've used a set all along. Haven't touched sets in forever, should've used them more often. I'll accept "use a hashset" as an answer cause it solves my problem. – Redacted Jul 23 '18 at 14:20
  • There is no memory usage difference if you save the **same** instance as key and value, or just any other instance as value - it is only a reference that is being saved. – user85421 Jul 23 '18 at 14:30
  • 1
    The average complexity of a lookup in a HashMap with a well-distributed hash function is `O(1)`. https://en.wikipedia.org/wiki/Hash_table - or any computer science textbook. – Erwin Bolwidt Jul 23 '18 at 14:40
  • @Neo the O notation does not refer to the actual time that it takes to do stuff. It refers to the growth of the time it takes as `n` goes towards infinity. And the average complexity of a lookup in a hash map is O(1). – Erwin Bolwidt Jul 23 '18 at 14:43
  • Thanks @Erwin Bolwidt. for a second I thought I was going insane or experiencing a Mandela Effect – Redacted Jul 23 '18 at 14:49

0 Answers0