tag:blogger.com,1999:blog-34692233.post456533669901227962..comments2023-05-09T12:02:11.783+01:00Comments on Mind the Gap: CaseInsensitiveMapGlynhttp://www.blogger.com/profile/08741529390385812080noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-34692233.post-37102510516575320962013-01-29T11:05:19.184+00:002013-01-29T11:05:19.184+00:00@Didier: hmmm, I'm not sureI follow. I don'...@Didier: hmmm, I'm not sureI follow. I don't see any mention of consistency in the Map javadoc. If a case-insensitive Map never contains two keys which differ only in case, I don't see how such a map can be inconsistent.Glynhttps://www.blogger.com/profile/08741529390385812080noreply@blogger.comtag:blogger.com,1999:blog-34692233.post-80783491508437315382013-01-29T10:13:36.149+00:002013-01-29T10:13:36.149+00:00Thirdly, the javadoc for TreeMap says that the ord...Thirdly, the javadoc for TreeMap says that the ordering must be consistent with equals, meaning that the comparator should return 0 if and only if equals returns true, if the Map interface is to be correctly implemented. This would not be the case for case-insensitive comparison.<br /><br />Well, no Map can be both case-insensitive and consistent with String.equals… It is thus not possible to implement a case-insensitive Map.Anonymoushttps://www.blogger.com/profile/11683172926353880863noreply@blogger.comtag:blogger.com,1999:blog-34692233.post-59521468601771615012011-08-06T14:30:49.618+01:002011-08-06T14:30:49.618+01:00Thanks Ryan. Fixed the bad links.Thanks Ryan. Fixed the bad links.Glynhttps://www.blogger.com/profile/08741529390385812080noreply@blogger.comtag:blogger.com,1999:blog-34692233.post-71909724555555871012011-08-06T00:33:08.537+01:002011-08-06T00:33:08.537+01:00FYI Glyn, the link in the blog to the source of yo...FYI Glyn, the link in the blog to the source of your implementation no longer works.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-34692233.post-40001951230486507852009-04-30T15:02:00.000+01:002009-04-30T15:02:00.000+01:00Don't be too shocked about the lack of UOE for add...Don't be too shocked about the lack of UOE for addAll operations. Although it's not correct, it's benign!<br /><br />The problem is that TreeMap uses an AbstractSet to implement its key and entry sets but does not override addAll.<br /><br />AbstractSet.addAll (inherited from AbstractCollection) only throws UOE if it calls add and add throws UOE. So if you call addAll with a null or empty collection, you don't get a UOE. But, to be fair, it hasn't updated the set, so it's fairly harmless.<br /><br />In my opinion, this behaviour does not implement Map.keySet or Map.entrySet which both state that the returned set "does not support the add or addAll operations".<br /><br />The solution in my implementation is to override addAll and throw UOE regardless of the input parameter.<br /><br />I don't mind being called a pedant on this issue. I was much more concerned by the unexpected CME which could present a usability issue for callers of my code.Glynhttps://www.blogger.com/profile/08741529390385812080noreply@blogger.comtag:blogger.com,1999:blog-34692233.post-48881394731781950922009-04-30T00:31:00.000+01:002009-04-30T00:31:00.000+01:00I'm really shocked the Set views for key/ entries ...I'm really shocked the Set views for key/ entries don't throw UOE for any of the add operations. It just doesn't make sense to add a key, after all where's the value.<br /><br />While TreeSets are slightly slower than HashMaps this figure is not a magnitude number, but from my experience a few percentage points. After all TreeMsps etc use red/black trees which are slightly slower than a map with buckets etc. Sorting comes for free it's no big deal...<br /><br />If the String case insensitive Comparator is trivial to replace so that it handles or denies null keys and it's equals is consistent...<br /><br />The most mystifying problem you describe is the ConcurrentModEx I thought the views were live so one would imagine these sorts of things wouldn't happen...<br /><br />Oh well I guess the important thing is your solution works :)...rocket-gwthttps://www.blogger.com/profile/10871975054807215305noreply@blogger.comtag:blogger.com,1999:blog-34692233.post-10695634512995477742009-04-29T10:54:00.000+01:002009-04-29T10:54:00.000+01:00Thanks for bringing this up! Given the TreeMap imp...Thanks for bringing this up! Given the TreeMap implementation is about 6 lines of code, I was <B>really</B> tempted to switch. If I hadn't already written and tested the current code, I might have gone down that route.<br /><br />However, re-running my unit tests against the 6 line implementation showed up several weaknesses.<br /><br />The entry set test method threw a ConcurrentModificationException, although it was not doing anything multi-threaded or particularly complex. I think this is a usability issue for my users.<br /><br />put with a null key or a null value did not throw a NPE, so this would need overriding. There were some other NPEs that would need fixing up too.<br /><br />addAll on the entry set no longer threw UnsupportedOperationException, but Map.entrySet says that the entry set does not support addAll. Similarly for the key set.<br /><br />Finally, there are some disadvantages to sorting.<br /><br />Firstly, sorting is not required, so TreeMap appearing in the inheritance tree of the 6 line implementation is a bit of a pain.<br /><br />Secondly, sorted tree algorithms cost O(log n) for put/get compared to O(1) for hash tables (assuming the collision lists don't grow too long).<br /><br />Thirdly, the javadoc for TreeMap says that the ordering must be consistent with equals, meaning that the comparator should return 0 if and only if equals returns true, if the Map interface is to be correctly implemented. This would not be the case for case-insensitive comparison.Glynhttps://www.blogger.com/profile/08741529390385812080noreply@blogger.comtag:blogger.com,1999:blog-34692233.post-53301958011509798432009-04-29T00:31:00.000+01:002009-04-29T00:31:00.000+01:00What about a TreeMap with a The case insensitive C...What about a TreeMap with a The case insensitive Comparator that lives on String.rocket-gwthttps://www.blogger.com/profile/10871975054807215305noreply@blogger.com