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