1 package structures;
2 
3 import java.io.Serializable;
4 import java.util.Arrays;
5 import java.util.HashMap;
6 import java.util.Random;
7 
8 import shared.KillSwitch;
9 import shared.Primes;
10 import shared.Shared;
11 import shared.Timer;
12 import shared.Tools;
13 
14 /**
15  * @author Brian Bushnell
16  * @date June 7, 2017
17  *
18  */
19 public final class IntHashMap extends AbstractIntHashMap implements Serializable {
20 
21 	/**
22 	 *
23 	 */
24 	private static final long serialVersionUID = 5525726007591609843L;
25 
main(String[] args)26 	public static void main(String[] args){
27 //		IntHashMap set=new IntHashMap(20, 0.7f);
28 //		test(set);
29 		int size=args.length>0 ? Integer.parseInt(args[0]) : 100000000;
30 		bench(size);
31 	}
32 
bench(int size)33 	private static void bench(int size){
34 		System.gc();
35 		Timer t=new Timer();
36 
37 		{
38 			System.err.println("\nIntHashMap:");
39 			Shared.printMemory();
40 			t.start();
41 			IntHashMap map=new IntHashMap();
42 			for(int i=0; i<size; i++){
43 				map.put(i, 2*i);
44 			}
45 			t.stop("Time: \t");
46 			System.gc();
47 			Shared.printMemory();
48 			map=null;
49 			System.gc();
50 		}
51 
52 		{
53 			System.err.println("\nHashMap<Integer, Integer>:");
54 			Shared.printMemory();
55 			t.start();
56 			HashMap<Integer, Integer> map=new HashMap<Integer, Integer>();
57 			for(int i=0; i<size; i++){
58 				map.put(i, 2*i);
59 			}
60 			t.stop("Time: \t");
61 			System.gc();
62 			Shared.printMemory();
63 			map=null;
64 			System.gc();
65 		}
66 	}
67 
68 	/*--------------------------------------------------------------*/
69 	/*----------------        Initialization        ----------------*/
70 	/*--------------------------------------------------------------*/
71 
IntHashMap()72 	public IntHashMap(){
73 		this(256);
74 	}
75 
IntHashMap(int initialSize)76 	public IntHashMap(int initialSize){
77 		this(initialSize, 0.7f);
78 	}
79 
IntHashMap(int initialSize, float loadFactor_)80 	public IntHashMap(int initialSize, float loadFactor_){
81 		invalid=randy.nextInt()|MINMASK;
82 		assert(invalid<0);
83 		assert(initialSize>0);
84 		assert(loadFactor_>0 && loadFactor_<1);
85 		loadFactor=Tools.mid(0.25f, loadFactor_, 0.90f);
86 		resize(initialSize);
87 	}
88 
89 	/*--------------------------------------------------------------*/
90 	/*----------------        Public Methods        ----------------*/
91 	/*--------------------------------------------------------------*/
92 
93 	@Override
clear()94 	public void clear(){
95 		if(size<1){return;}
96 		Arrays.fill(keys, invalid);
97 		Arrays.fill(values, 0);
98 		size=0;
99 	}
100 
101 	@Override
get(int key)102 	public int get(int key){
103 		int cell=findCell(key);
104 		return cell<0 ? -1 : values[cell];
105 	}
106 
107 	@Override
put(int key, int value)108 	public int put(int key, int value){return set(key, value);}
109 
110 	@Override
set(int key, int value)111 	public int set(int key, int value){
112 		if(key==invalid){resetInvalid();}
113 		final int cell=findCellOrEmpty(key);
114 		final int oldV=values[cell];
115 		values[cell]=value;
116 		if(keys[cell]==invalid){
117 			keys[cell]=key;
118 			size++;
119 			if(size>sizeLimit){resize();}
120 		}
121 //		assert(get(key)==value);//TODO: slow
122 		return oldV;
123 	}
124 
125 	@Override
increment(int key)126 	public int increment(int key){
127 		return increment(key, 1);
128 	}
129 
130 	@Override
increment(int key, int incr)131 	public int increment(int key, int incr){
132 		if(key==invalid){resetInvalid();}
133 		final int cell=findCellOrEmpty(key);
134 		final int oldV=values[cell];
135 		final int value=oldV+incr;
136 		values[cell]=value;
137 		values[cell]=Tools.min(Integer.MAX_VALUE, value);
138 		if(keys[cell]==invalid){
139 			keys[cell]=key;
140 			size++;
141 			if(size>sizeLimit){resize();}
142 		}
143 //		assert(get(key)==value);//TODO: slow
144 		return value;
145 	}
146 
147 	@Override
remove(int key)148 	public boolean remove(int key){
149 		if(key==invalid){return false;}
150 		final int cell=findCell(key);
151 		if(cell<0){return false;}
152 		assert(keys[cell]==key);
153 		keys[cell]=invalid;
154 		values[cell]=0;
155 		size--;
156 
157 		rehashFrom(cell);
158 		return true;
159 	}
160 
161 	/*--------------------------------------------------------------*/
162 	/*----------------        Private Methods       ----------------*/
163 	/*--------------------------------------------------------------*/
164 
rehashFrom(int initial)165 	private void rehashFrom(int initial){
166 		if(size<1){return;}
167 		final int limit=keys.length;
168 		for(int cell=initial+1; cell<limit; cell++){
169 			final int key=keys[cell];
170 			if(key==invalid){return;}
171 			rehashCell(cell);
172 		}
173 		for(int cell=0; cell<initial; cell++){
174 			final int key=keys[cell];
175 			if(key==invalid){return;}
176 			rehashCell(cell);
177 		}
178 	}
179 
rehashCell(final int cell)180 	private boolean rehashCell(final int cell){
181 		final int key=keys[cell];
182 		final int value=values[cell];
183 		assert(key!=invalid);
184 		if(key==invalid){resetInvalid();}
185 		final int dest=findCellOrEmpty(key);
186 		if(cell==dest){return false;}
187 		assert(keys[dest]==invalid);
188 		keys[cell]=invalid;
189 		values[cell]=0;
190 		keys[dest]=key;
191 		values[dest]=value;
192 
193 		return true;
194 	}
195 
resetInvalid()196 	private void resetInvalid(){
197 		final int old=invalid;
198 		int x=invalid;
199 		while(x==old || contains(x)){x=randy.nextInt()|MINMASK;}
200 		assert(x<0);
201 		invalid=x;
202 		for(int i=0; i<keys.length; i++){
203 			if(keys[i]==old){
204 				keys[i]=invalid;
205 //				assert(volues[i]==0); //TODO: slow
206 			}
207 		}
208 	}
209 
210 	@Override
211 	int findCell(final int key){
212 		if(key==invalid){return -1;}
213 
214 		final int limit=keys.length, initial=(int)((key&MASK)%modulus);
215 		for(int cell=initial; cell<limit; cell++){
216 			final int x=keys[cell];
217 			if(x==key){return cell;}
218 			if(x==invalid){return -1;}
219 		}
220 		for(int cell=0; cell<initial; cell++){
221 			final int x=keys[cell];
222 			if(x==key){return cell;}
223 			if(x==invalid){return -1;}
224 		}
225 		return -1;
226 	}
227 
228 	private int findCellOrEmpty(final int key){
229 		assert(key!=invalid) : "Collision - this should have been intercepted.";
230 
231 		final int limit=keys.length, initial=(int)((key&MASK)%modulus);
232 		for(int cell=initial; cell<limit; cell++){
233 			final int x=keys[cell];
234 			if(x==key || x==invalid){return cell;}
235 		}
236 		for(int cell=0; cell<initial; cell++){
237 			final int x=keys[cell];
238 			if(x==key || x==invalid){return cell;}
239 		}
240 		throw new RuntimeException("No empty cells - size="+size+", limit="+limit);
241 	}
242 
243 	private final void resize(){
244 		assert(size>=sizeLimit);
245 		resize(keys.length*2L+1);
246 	}
247 
248 	private final void resize(final long size2){
249 		assert(size2>size) : size+", "+size2;
250 		long newPrime=Primes.primeAtLeast(size2);
251 		if(newPrime+extra>Integer.MAX_VALUE){
252 			newPrime=Primes.primeAtMost(Integer.MAX_VALUE-extra);
253 		}
254 		assert(newPrime>modulus) : "Overflow: "+size+", "+size2+", "+modulus+", "+newPrime;
255 		modulus=(int)newPrime;
256 
257 		final int size3=(int)(newPrime+extra);
258 		sizeLimit=(int)(modulus*loadFactor);
259 		final int[] oldK=keys;
260 		final int[] oldV=values;
261 		keys=KillSwitch.allocInt1D(size3);
262 		values=KillSwitch.allocInt1D(size3);
263 		Arrays.fill(keys, invalid);
264 
265 //		System.err.println("Resizing "+(old==null ? "null" : ""+old.length)+" to "+size3);
266 
267 		if(size<1){return;}
268 
269 		size=0;
270 		for(int i=0; i<oldK.length; i++){
271 			final int k=oldK[i], v=oldV[i];
272 			if(k!=invalid){
273 				set(k, v);
274 			}
275 		}
276 	}
277 
278 	/*--------------------------------------------------------------*/
279 	/*----------------            Getters           ----------------*/
280 	/*--------------------------------------------------------------*/
281 
282 	@Override
283 	public int[] toArray(){
284 		int[] x=KillSwitch.allocInt1D(size);
285 		int i=0;
286 		for(int key : keys){
287 			if(key!=invalid){
288 				x[i]=key;
289 				i++;
290 			}
291 		}
292 		return x;
293 	}
294 
295 	@Override
296 	public int[] keys(){return keys;}
297 
298 	@Override
299 	public int[] values(){return values;}
300 
301 	@Override
302 	public int invalid(){return invalid;}
303 
304 	@Override
305 	public int size(){return size;}
306 
307 	@Override
308 	public boolean isEmpty(){return size==0;}
309 
310 	/*--------------------------------------------------------------*/
311 	/*----------------            Fields            ----------------*/
312 	/*--------------------------------------------------------------*/
313 
314 	private int[] keys;
315 	private int[] values;
316 	private int size=0;
317 	/** Value for empty cells */
318 	private int invalid;
319 	private int modulus;
320 	private int sizeLimit;
321 	private final float loadFactor;
322 
323 	private static final Random randy=new Random(1);
324 
325 }
326