<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Aug 26, 2015, at 8:59 PM, Gábor Horváth <<a href="mailto:xazax.hun@gmail.com" class="">xazax.hun@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div style="font-family: Helvetica; font-size: 14px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">So ImmutableMap right now uses an AVL tree, which has O(log(n)) complexity for lookup, insertion and deletion. Finger search trees, however, can be implemented as immutable data structures, and they have amortized O(log(n)) lookup and amortized O(1) insertion and deletion (source:<span class="Apple-converted-space"> </span><a href="https://urldefense.proofpoint.com/v2/url?u=https-3A__en.wikipedia.org_wiki_Finger-5Fsearch-5Ftree&d=BQMFaQ&c=eEvniauFctOgLOKGJOplqw&r=UVc407_CCx3FapxjS2xZ9jo4Q91upSGpJHRF8fPPYVY&m=ZSn2Xpd2bzTg-eJGSZwPHL5YX99ATIUerX2pwnRrOyU&s=ua5pVdOaNO6HMJElFSPe5UheXE8vDgUI0q6MD5oKVJo&e=" class="">https://en.wikipedia.org/wiki/Finger_search_tree</a>). If inserting a value into the map is the most frequent operation this could be a huge win. </div><div style="font-family: Helvetica; font-size: 14px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">Ben, if I am not mistaken, this might be worth to investigate.</div></div></blockquote></div><div class=""><br class=""></div><div class="">That’s a great insight. That indeed could be a huge win. We would need to evaluate both the memory and CPU impact of the change, and big-O isn’t everything. Sometimes the constant factor is important, especially if the majority of maps have a small number of elements.</div></body></html>