Retrieving a value from a hashmap goes through the following steps: 1) Compute the hashcode of the supplied key. 2) Navigate through the map's internal tree structure to the bucket that should contain this hashcode (the complexity of this step depends on the number of different hashcodes stored in the map, not on the complexity of the key you're searching for). 3) If that bucket is empty, return the provided "missing" value (default: nil). 4) If the bucket is not empty, for each item in the bucket (all of them have the same hashcode): 5) Compare for pointer equality; if equal, return the associated value 6) Compare for true equality; if equal, return the associated value 7) Return the provided "missing" value.
So, yes, if you use complex, deeply nested keys _and_ you retrieve the associated value through using newly-created, value-equal instances of those keys, it will be a bit slow because you'll have to recompute the hashcode of the supplied key each time you build it again, and then you'll still need to traverse the supplied key and the existing copy in the hashmap for true equality. In practice, it will most likely be much faster than the worst case because you will not rebuild the full key from scratch each time, and Clojure value equality is aware of structural sharing (i.e. if there is a subtree of the nested keys you're comparing that is actually equal, Clojure will not need to traverse that part). Due to the way Clojure works with immutable values, the most likely scenario is that you will have built that key once, and use the same key (same object in memory) in the hasmap as in the code that retrieves it; it's also likely that you will have just that one key for that hashcode value in the map. In that situation, in order to retrieve the key you just need one hashcode retrieval (it's been cached on first computation, when you added the key to the map), then one traversal to the correct bucket (that's typically a O(log32 N) depth), then one pointer equality check; all of that will be very fast and independent of the complexity of the key. Note that the above assumes your keys are Clojure values; if they are arbitrary Java objects the equality comparison defaults to Java's .equals so it may be a bit different; also, most Java objects do not cache their hashcodes. On 12 November 2017 at 08:35, Jay Porcasi <jaygporc...@gmail.com> wrote: > thank you very much for the clarification > so no magic there :-) > using big nested structures as keys is gonna slow down things a bit > > but how caching can help? > > On Friday, November 10, 2017 at 12:29:41 PM UTC+7, tbc++ wrote: >> >> Most Clojure collections cache their hashcode, so that improves things >> quite bit. Also, very large collections are rarely used as *keys* in other >> maps. Most of the time key collections are one or two values. This means >> that what we're really talking about is combining the hash values of a few >> values, and that's pretty fast. >> >> So sure, the initial hash of one million symbols inside a vector may take >> a fair amount of time, but I've never seen that in the wild. >> >> Timothy >> >> >> -- > You received this message because you are subscribed to the Google > Groups "Clojure" group. > To post to this group, send email to clojure@googlegroups.com > Note that posts from new members are moderated - please be patient with > your first post. > To unsubscribe from this group, send email to > clojure+unsubscr...@googlegroups.com > For more options, visit this group at > http://groups.google.com/group/clojure?hl=en > --- > You received this message because you are subscribed to the Google Groups > "Clojure" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to clojure+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
