Path: csiph.com!usenet.pasdenom.info!aioe.org!.POSTED!not-for-mail From: Roedy Green Newsgroups: comp.lang.java.programmer Subject: Re: optimsed HashMap Date: Fri, 23 Nov 2012 22:42:40 -0800 Organization: Canadian Mind Products Lines: 56 Message-ID: <8ip0b8p7blu31eub502so8cus1h9so3m9s@4ax.com> References: <8i70b8d0pm6ibk03ti4t2pv60jd0bctlcs@4ax.com> Reply-To: Roedy Green NNTP-Posting-Host: K2Qzzs3EAqXk5RLzfhxcSw.user.speranza.aioe.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Complaints-To: abuse@aioe.org X-Notice: Filtered by postfilter v. 0.8.2 X-Newsreader: Forte Agent 6.00/32.1186 Xref: csiph.com comp.lang.java.programmer:19883 On Fri, 23 Nov 2012 17:33:43 -0800, markspace <-@.> wrote, quoted or indirectly quoted someone who said : >I'm not sure what you are trying to say there. You want the case where >you do not find something in a hash map to be optimized? "Optimized" how? >What do you mean "add to the list of words" and "freeze"? The following is not the real problem, but it might more simply illustrate what I am asking. Think of an ordinary HashMap What it does is translate a few English words with French derivation, putting the French accents on them. e.g. naive -> naïve Napoleon -> Napol´on Let us say you have 100 such words you want to transform. (In my actual problem I have about 1500 words). You go through the files for a website looking at each word of text (avoiding HTML markup) in the HashMap. If you find it you replace it. Most of the time word you look up is not in the list. This is a time-consuming process. I would like to speed it up. My lookup has two properties that might be exploited in some variant HashMap. 1. nearly always the lookup fails. The code should be optimised for this case. If it has some fast way of knowing the elt is not there, it should do that first. 2. the list of words to lookup does not change after initial preparation. I can afford to do some special calculation to prime the lookup. For example, I once heard of some tweaking to avoid long collision chains for a C implementation of HashMap. My question had two purposes. To see if there was something available off the shelf, and to stimulate thought on some new algorithm that could have wider application that just my problem. Another way of looking at the problem is it would be nice to have a HashSet implementation that was considerably faster than a HashMap. IIRC, currently HashSet is implemented as a HashMap. Such an algorithm could be used to fix your most common spelling mistakes, to add links to magic words, to add markup to magic words to find and report the presence of certain words, or in my case find acronyms and replace them with a macro for that acronym that displays the meaning of the acronym the first time it is used on a page. -- Roedy Green Canadian Mind Products http://mindprod.com Students who hire or con others to do their homework are as foolish as couch potatoes who hire others to go to the gym for them.