1 package structures;
2 
3 import java.util.ArrayList;
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 August 3, 2017
17  *
18  */
19 public final class LongHashMap{
20 
main(String[] args)21 	public static void main(String[] args){
22 		Random randy2=Shared.threadLocalRandom();
23 		LongHashMap map=new LongHashMap(20, 0.7f);
24 		HashMap<Long, Integer> map2=new HashMap<Long, Integer>(20, 0.7f);
25 		ArrayList<Long> list=new ArrayList<Long>();
26 		ArrayList<Long> list2=new ArrayList<Long>();
27 //		ArrayList<Integer> vals=new ArrayList<Integer>();
28 		for(long i=0; i<1000; i++){
29 			assert(!map.contains(i));
30 			assert(!map2.containsKey(i));
31 			list.add(new Long(i));
32 		}
33 		for(int i=0; i<1000; i++){
34 			long r=randy2.nextLong();
35 			list2.add(r);
36 		}
37 
38 		for(long x : list){
39 			map.put(x, (int)(2*x));
40 			map2.put(x, (int)(2*x));
41 			assert(map.get(x)==((int)(2*x)));
42 			assert(map2.get(x)==((int)(2*x)));
43 		}
44 
45 		for(long x : list){
46 			assert(map.get(x)==((int)(2*x)));
47 			assert(map2.get(x)==((int)(2*x)));
48 			map.remove(x);
49 			map2.remove(x);
50 			assert(!map.contains(x));
51 			assert(!map2.containsKey(x));
52 		}
53 		assert(map.isEmpty());
54 		assert(map2.isEmpty());
55 
56 		for(long x : list2){
57 			map.put(x, (int)(2*x));
58 			map2.put(x, (int)(2*x));
59 			assert(map.get(x)==((int)(2*x)));
60 			assert(map2.get(x)==((int)(2*x)));
61 		}
62 
63 		for(long x : list2){
64 			assert(map.get(x)==((int)(2*x)));
65 			assert(map2.get(x)==((int)(2*x)));
66 			map.remove(x);
67 			map2.remove(x);
68 			assert(!map.contains(x));
69 			assert(!map2.containsKey(x));
70 		}
71 		assert(map.isEmpty());
72 		assert(map2.isEmpty());
73 
74 		int count=4000000;
75 		int runs=32;
76 		LongList ll=new LongList(count);
77 		for(int i=0; i<count; i++){ll.add(randy2.nextLong());}
78 
79 		Shared.printMemory();
80 		Timer t=new Timer();
81 		for(int k=0; k<2; k++){
82 			System.err.println("LongHashMap:");
83 			t.start();
84 			for(int i=0; i<runs; i++){
85 //				for(long x : ll.array){
86 //					map.add(x);
87 //				}
88 				final long[] y=ll.array;
89 				for(int z=0; z<count; z++){
90 					final long key=y[z];
91 					map.add(key);
92 					map.contains(key);
93 					map.remove(key);
94 					map.add(key);
95 				}
96 //				for(long x : ll.array){
97 //					map.remove(x);
98 //				}
99 //				map.clear();
100 //				assert(map.isEmpty());
101 //				System.err.println("Finished run "+i);
102 			}
103 			t.stop();
104 			System.err.println(t);
105 			Shared.printMemory();
106 
107 //			System.err.println("HashMap:");
108 //			t.start();
109 //			for(int i=0; i<runs; i++){
110 //				for(long x : ll.array){
111 //					map2.add(x);
112 //				}
113 //				for(long x : ll.array){
114 //					map2.remove(x);
115 //				}
116 //				assert(map2.isEmpty());
117 ////				System.err.println("Finished run "+i);
118 //			}
119 //			t.stop();
120 //			System.err.println(t);
121 //			Shared.printMemory();
122 		}
123 		t.stop();
124 	}
125 
126 	/*--------------------------------------------------------------*/
127 	/*----------------        Initialization        ----------------*/
128 	/*--------------------------------------------------------------*/
129 
LongHashMap()130 	public LongHashMap(){
131 		this(256);
132 	}
133 
LongHashMap(int initialSize)134 	public LongHashMap(int initialSize){
135 		this(initialSize, 0.7f);
136 	}
137 
LongHashMap(int initialSize, float loadFactor_)138 	public LongHashMap(int initialSize, float loadFactor_){
139 		invalid=randy.nextLong()|MINMASK;
140 		assert(invalid<0);
141 		assert(initialSize>0);
142 		assert(loadFactor_>0 && loadFactor_<1);
143 		loadFactor=Tools.mid(0.25f, loadFactor_, 0.90f);
144 		resize(initialSize);
145 	}
146 
147 	/*--------------------------------------------------------------*/
148 	/*----------------        Public Methods        ----------------*/
149 	/*--------------------------------------------------------------*/
150 
clear()151 	public void clear(){
152 		if(size<1){return;}
153 		Arrays.fill(keys, invalid);
154 		Arrays.fill(values, 0);
155 		size=0;
156 //		assert(verify()); //123
157 	}
158 
contains(long key)159 	public boolean contains(long key){
160 //		assert(verify()); //123
161 		return key==invalid ? false : findCell(key)>=0;
162 	}
163 
containsKey(long key)164 	public boolean containsKey(long key){
165 		return contains(key);
166 	}
167 
get(long key)168 	public int get(long key){
169 //		assert(verify()); //123
170 		int value=-1;
171 		if(key!=invalid){
172 			int cell=findCell(key);
173 			if(cell>=0){value=values[cell];}
174 		}
175 		return value;
176 	}
177 
178 	/**
179 	 * Increment this key's value by 1.
180 	 * @param key
181 	 * @return New value
182 	 */
add(long key)183 	public int add(long key){
184 		return increment(key, 1);
185 	}
186 
187 	/**
188 	 * Increment this key's value by incr.
189 	 * @param key
190 	 * @param incr
191 	 * @return New value
192 	 */
increment(long key, int incr)193 	public int increment(long key, int incr){
194 //		assert(verify()); //123
195 		if(key==invalid){resetInvalid();}
196 		int cell=findCellOrEmpty(key);
197 		if(keys[cell]==invalid){
198 			keys[cell]=key;
199 			values[cell]=incr;
200 			size++;
201 //			assert(verify()); //123
202 			if(size>sizeLimit){resize();}
203 //			assert(verify()); //123
204 			return incr;
205 		}else{
206 			values[cell]+=incr;
207 //			assert(verify()); //123
208 			return values[cell];
209 		}
210 	}
211 
212 	/**
213 	 * Map this key to value.
214 	 * @param key
215 	 * @param value
216 	 * @return true if the key was added, false if it was already contained.
217 	 */
put(long key, int value)218 	public boolean put(long key, int value){
219 //		assert(verify()); //123
220 		if(key==invalid){resetInvalid();}
221 		int cell=findCellOrEmpty(key);
222 		if(keys[cell]==invalid){
223 			keys[cell]=key;
224 			values[cell]=value;
225 			size++;
226 			if(size>sizeLimit){resize();}
227 //			assert(verify()); //123
228 			return true;
229 		}
230 		assert(keys[cell]==key);
231 //		assert(verify()); //123
232 		return false;
233 	}
234 
235 	/**
236 	 * Remove this key from the map.
237 	 * @param key
238 	 * @return Old value.
239 	 */
remove(long key)240 	public int remove(long key){
241 //		assert(verify()); //123
242 		if(key==invalid){return -1;}
243 		final int cell=findCell(key);
244 		if(cell<0){return -1;}
245 		assert(keys[cell]==key);
246 		keys[cell]=invalid;
247 		final int value=values[cell];
248 		values[cell]=0;
249 		size--;
250 
251 		rehashFrom(cell);
252 //		assert(verify()); //123
253 		return value;
254 	}
255 
size()256 	public int size(){return size;}
257 
isEmpty()258 	public boolean isEmpty(){return size==0;}
259 
260 	/*--------------------------------------------------------------*/
261 	/*----------------        String Methods        ----------------*/
262 	/*--------------------------------------------------------------*/
263 
264 	@Override
toString()265 	public String toString(){
266 		return toStringListView();
267 	}
268 
toStringSetView()269 	public String toStringSetView(){
270 		StringBuilder sb=new StringBuilder();
271 		sb.append('[');
272 		String comma="";
273 		for(int i=0; i<keys.length; i++){
274 			if(keys[i]!=invalid){
275 				sb.append(comma+"("+i+", "+keys[i]+", "+values[i]+")");
276 				comma=", ";
277 			}
278 		}
279 		sb.append(']');
280 		return sb.toString();
281 	}
282 
toStringListView()283 	public String toStringListView(){
284 		StringBuilder sb=new StringBuilder();
285 		sb.append('[');
286 		String comma="";
287 		for(int i=0; i<keys.length; i++){
288 			if(keys[i]!=invalid){
289 				sb.append(comma+keys[i]);
290 				comma=", ";
291 			}
292 		}
293 		sb.append(']');
294 		return sb.toString();
295 	}
296 
toArray()297 	public long[] toArray(){
298 		long[] x=KillSwitch.allocLong1D(size);
299 		int i=0;
300 		for(long key : keys){
301 			if(key!=invalid){
302 				x[i]=key;
303 				i++;
304 			}
305 		}
306 		return x;
307 	}
308 
getMin(int thresh)309 	public long[] getMin(int thresh){
310 		int found=0;
311 		long min=Long.MAX_VALUE;
312 		for(int i=0; i<values.length; i++){
313 			assert((values[i]==0)==(keys[i]==invalid)) : i+", "+values[i]+", "+keys[i]+", "+invalid+"\n"+toStringSetView();
314 			assert((keys[i]<0)==((keys[i]==invalid))) : toStringSetView();
315 			if(values[i]>=thresh){
316 				assert(keys[i]>=0) : "\nNegative key ("+keys[i]+", "+values[i]+", "+i+") for thresh "+thresh+":\n"+toStringSetView();
317 				found++;
318 				min=Tools.min(min, keys[i]);
319 			}
320 		}
321 		return new long[] {found>0 ? min : invalid, found};
322 	}
323 
toArray(int thresh)324 	public long[] toArray(int thresh){
325 		thresh=Tools.max(thresh, 1);
326 		int len=0;
327 //		assert(verify());
328 		for(int i=0; i<values.length; i++){
329 			assert((values[i]==0)==(keys[i]==invalid)) : i+", "+values[i]+", "+keys[i]+", "+invalid+"\n"+toStringSetView();
330 			assert((keys[i]<0)==((keys[i]==invalid))) : toStringSetView();
331 			if(values[i]>=thresh){
332 				assert(keys[i]>=0) : "\nNegative key ("+keys[i]+", "+values[i]+", "+i+") for thresh "+thresh+":\n"+toStringSetView();
333 				len++;
334 			}
335 		}
336 		long[] x=KillSwitch.allocLong1D(len);
337 		for(int i=0, j=0; j<len; i++){
338 			if(values[i]>=thresh){
339 				x[j]=keys[i];
340 				assert(keys[i]>=0) : "\nNegative key ("+keys[i]+", "+values[i]+", "+i+") for thresh "+thresh+":\n"+toStringSetView();
341 				j++;
342 			}
343 		}
344 		return x;
345 	}
346 
347 	/*--------------------------------------------------------------*/
348 	/*----------------        Private Methods       ----------------*/
349 	/*--------------------------------------------------------------*/
350 
verify()351 	public boolean verify(){
352 		if(keys==null){return true;}
353 		int numValues=0;
354 		int numFound=0;
355 		for(int i=0; i<keys.length; i++){
356 			final long key=keys[i];
357 			final int value=values[i];
358 
359 			if(key==invalid){
360 				if(value!=0){
361 					assert(false) : i+", "+key+", "+value;
362 					return false;
363 				}
364 			}else{
365 				numValues++;
366 				if(value<1){
367 					assert(false) : i+", "+key+", "+value;
368 					return false;
369 				}
370 				final int cell=findCell(key);
371 				if(i==cell){
372 					numFound++;
373 				}else{
374 					assert(false) : i+", "+key+", "+value+", "+cell+"\n"+((cell>=0) ? keys[cell]+", "+values[cell]+"\n" : "");
375 					return false;
376 				}
377 			}
378 		}
379 		boolean pass=(numValues==numFound && numValues==size);
380 		assert(pass) : numValues+", "+numFound+", "+size;
381 		return pass;
382 	}
383 
rehashFrom(int initial)384 	private void rehashFrom(int initial){
385 		if(size<1){return;}
386 		final int limit=keys.length;
387 		for(int cell=initial+1; cell<limit; cell++){
388 			final long x=keys[cell];
389 			if(x==invalid){return;}
390 			rehashCell(cell);
391 		}
392 		for(int cell=0; cell<initial; cell++){
393 			final long x=keys[cell];
394 			if(x==invalid){return;}
395 			rehashCell(cell);
396 		}
397 	}
398 
rehashCell(final int cell)399 	private boolean rehashCell(final int cell){
400 		final long key=keys[cell];
401 		final int value=values[cell];
402 		assert(key!=invalid);
403 		if(key==invalid){resetInvalid();}
404 		final int dest=findCellOrEmpty(key);
405 		if(cell==dest){return false;}
406 		assert(keys[dest]==invalid);
407 		keys[cell]=invalid;
408 		values[cell]=0;
409 		keys[dest]=key;
410 		values[dest]=value;
411 		return true;
412 	}
413 
resetInvalid()414 	private void resetInvalid(){
415 		final long old=invalid;
416 		long x=invalid;
417 		while(x==old || contains(x)){x=randy.nextLong()|MINMASK;}
418 		assert(x<0);
419 		invalid=x;
420 		for(int i=0; i<keys.length; i++){
421 			if(keys[i]==old){
422 				assert(values[i]==0);
423 				keys[i]=invalid;
424 			}
425 		}
426 	}
427 
428 	private int findCell(final long key){
429 		if(key==invalid){return -1;}
430 
431 		final int limit=keys.length, initial=(int)((key&MASK)%modulus);
432 		for(int cell=initial; cell<limit; cell++){
433 			final long x=keys[cell];
434 			if(x==key){return cell;}
435 			if(x==invalid){return -1;}
436 		}
437 		for(int cell=0; cell<initial; cell++){
438 			final long x=keys[cell];
439 			if(x==key){return cell;}
440 			if(x==invalid){return -1;}
441 		}
442 		return -1;
443 	}
444 
445 	private int findCellOrEmpty(final long key){
446 		assert(key!=invalid) : "Collision - this should have been intercepted.";
447 
448 		final int limit=keys.length, initial=(int)((key&MASK)%modulus);
449 		for(int cell=initial; cell<limit; cell++){
450 			final long x=keys[cell];
451 			if(x==key || x==invalid){return cell;}
452 		}
453 		for(int cell=0; cell<initial; cell++){
454 			final long x=keys[cell];
455 			if(x==key || x==invalid){return cell;}
456 		}
457 		throw new RuntimeException("No empty cells - size="+size+", limit="+limit);
458 	}
459 
460 	private final void resize(){
461 		assert(size>=sizeLimit);
462 		resize(keys.length*2L+1);
463 	}
464 
465 	private final void resize(final long size2){
466 //		assert(verify()); //123
467 		assert(size2>size) : size+", "+size2;
468 		long newPrime=Primes.primeAtLeast(size2);
469 		if(newPrime+extra>Integer.MAX_VALUE){
470 			newPrime=Primes.primeAtMost(Integer.MAX_VALUE-extra);
471 		}
472 		assert(newPrime>modulus) : "Overflow: "+size+", "+size2+", "+modulus+", "+newPrime;
473 		modulus=(int)newPrime;
474 
475 		final int size3=(int)(newPrime+extra);
476 		sizeLimit=(int)(modulus*loadFactor);
477 		final long[] oldKeys=keys;
478 		final int[] oldValues=values;
479 		keys=KillSwitch.allocLong1D(size3);
480 		values=KillSwitch.allocInt1D(size3);
481 		Arrays.fill(keys, invalid);
482 
483 //		System.err.println("Resizing "+(old==null ? "null" : ""+old.length)+" to "+size3);
484 
485 		if(size<1){return;}
486 
487 		size=0;
488 		for(int i=0; i<oldKeys.length; i++){
489 			long key=oldKeys[i];
490 			if(key!=invalid){
491 				put(key, oldValues[i]);
492 			}
493 		}
494 //		assert(verify()); //123
495 	}
496 
497 	/*--------------------------------------------------------------*/
498 	/*----------------            Getters           ----------------*/
499 	/*--------------------------------------------------------------*/
500 
501 	public long[] keys() {return keys;}
502 
503 	public int[] values() {return values;}
504 
505 	public long invalid() {return invalid;}
506 
507 	/*--------------------------------------------------------------*/
508 	/*----------------            Fields            ----------------*/
509 	/*--------------------------------------------------------------*/
510 
511 	private long[] keys;
512 	private int[] values;
513 	private int size=0;
514 	/** Value for empty cells */
515 	private long invalid;
516 	private int modulus;
517 	private int sizeLimit;
518 	private final float loadFactor;
519 
520 	private static final Random randy=new Random(1);
521 	private static final long MASK=Long.MAX_VALUE;
522 	private static final long MINMASK=Long.MIN_VALUE;
523 
524 	private static final int extra=10;
525 
526 }
527