Path: csiph.com!news.swapon.de!aioe.org!.POSTED!not-for-mail From: =?UTF-8?Q?Arne_Vajh=c3=b8j?= Newsgroups: comp.lang.java.programmer Subject: Re: Where can I find a good implementation of an IntMap similar to the one they used to have at org.cljp.*? Date: Tue, 16 May 2017 20:56:15 -0400 Organization: Aioe.org NNTP Server Lines: 233 Message-ID: References: <07a2714d-79c4-4a77-834d-261c1b8bf3e2@googlegroups.com> NNTP-Posting-Host: PBuS014lhzVyHjLbXmo/ZQ.user.gioia.aioe.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-Complaints-To: abuse@aioe.org User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:45.0) Gecko/20100101 Thunderbird/45.8.0 X-Notice: Filtered by postfilter v. 0.8.2 Xref: csiph.com comp.lang.java.programmer:36640 On 5/14/2017 1:55 PM, J Crawford wrote: > On Sunday, May 14, 2017 at 10:48:54 AM UTC-5, lewb...@gmail.com > wrote: >> What's wrong with `HashMap`? > > This is for real-time development so I need a data-structure that > does not produce any garbage for the GC and it is very > fast/efficient. My assumption would be that Map is only one out of many disturbances. Other things like: other GC, JIT compiler running, multi-tasking OS scheduling could also intervene. Java in general is not that good at real time. But you probably have that covered. > HashMap is not for real-time development. There are > many open source projects out there (Trove, GS Collections, etc.) but > the IntMap I've seen from Jon Skeet was the best. It does not seem to available on the internet. Just for the fun of it I tried writing a Map implementation with no allocation in put ever. It is not nice code. And I have not tested it. But just in case - it is attached below. Arne import java.util.AbstractMap; import java.util.ArrayList; import java.util.Collection; import java.util.HashSet; import java.util.Iterator; import java.util.List; import java.util.Map; import java.util.Set; // Map implementation not allocating objects in put // not good code - very limited functionality and very old style public class PrimitiveMap implements Map { private int maxsize; private Object[] keys; private Object[] values; private int[] next; private int scale; private int free; private int count; private void add(Object key, Object value, int ix) { keys[ix] = key; values[ix] = value; count++; } private void move(int target, int source) { if(source < scale) { keys[target] = null; values[target] = null; next[target] = 0; } else { keys[target] = keys[source]; values[target] = values[source]; move(source, next[source]); } } public void dump() { for(int i = 0; i < free; i++) { if(keys[i] != null) { System.err.printf("%d : %s %s %d\n", i, keys[i].toString(), values[i].toString(), next[i]); } } } public PrimitiveMap(int maxsize) { this.maxsize = maxsize; keys = new Object[maxsize]; values = new Object[maxsize]; next = new int[maxsize]; scale = maxsize / 2; free = scale; count = 0; } @Override public int size() { return count; } @Override public boolean isEmpty() { return (count == 0); } @Override public boolean containsKey(Object key) { return (get(key) != null); } @Override public boolean containsValue(Object value) { throw new RuntimeException("Not implemented yet"); } @SuppressWarnings("unchecked") @Override public TV get(Object key) { if(key == null) { throw new RuntimeException("Key null not allowed"); } int hsh = key.hashCode(); int ix = hsh % scale; if(keys[ix] == null) { return null; } else { do { if(keys[ix].equals(key)) { return (TV)values[ix]; } else { ix = next[ix]; } } while(ix >= scale); return null; } } @SuppressWarnings("unchecked") @Override public TV put(TK key, TV value) { if(key == null) { throw new RuntimeException("Key null not allowed"); } int hsh = key.hashCode(); int ix = hsh % scale; int oldix; if(keys[ix] == null) { add(key, value, ix); return null; } else { do { if(keys[ix].equals(key)) { Object res = values[ix]; values[ix] = value; return (TV)res; } else { oldix = ix; ix = next[ix]; } } while(ix >= scale); if(free >= maxsize) { throw new RuntimeException("Maximum size exceeded"); } add(key, value, free); next[oldix] = free; free++; return null; } } @SuppressWarnings("unchecked") @Override public TV remove(Object key) { if(key == null) { throw new RuntimeException("Key null not allowed"); } int hsh = key.hashCode(); int ix = hsh % scale; if(keys[ix] == null) { return null; } else { do { if(keys[ix].equals(key)) { Object res = values[ix]; move(ix, next[ix]); count--; while(free > scale && keys[free-1] == null) { free--; } return (TV)res; } else { ix = next[ix]; } } while(ix >= scale); return null; } } @Override public void putAll(Map m) { Iterator> it = m.entrySet().iterator(); while(it.hasNext()) { Map.Entry ent = it.next(); put(ent.getKey(), ent.getValue()); } } @Override public void clear() { for(int i = 0; i < maxsize; i++) { keys[i] = null; values[i] = null; next[i] = 0; } free = scale; count = 0; } @SuppressWarnings("unchecked") @Override public Set keySet() { Set res = new HashSet<>(); for(int i = 0; i < free; i++) { if(keys[i] != null) { res.add((TK)keys[i]); } } return res; } @SuppressWarnings("unchecked") @Override public Collection values() { List res = new ArrayList<>(); for(int i = 0; i < free; i++) { if(keys[i] != null) { res.add((TV)values[i]); } } return res; } @SuppressWarnings("unchecked") @Override public Set> entrySet() { Set> res = new HashSet<>(); for(int i = 0; i < free; i++) { if(keys[i] != null) { res.add(new AbstractMap.SimpleEntry((TK)keys[i], (TV)values[i])); } } return res; } }