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