Gets the index of the given key. Based on that #status variable, the index is either the location to insert OR the location of the key. This method returns 2 integer table in the long. The lower 32 bits are the index that either contains the key, or is the first empty index. The upper 32 b
(int key)
| 285 | * and the position that the key is in or the first EMPTY position found |
| 286 | */ |
| 287 | private long getIndex(int key) |
| 288 | { |
| 289 | long extraInfo = EXTRA_INDEX_INFO; |
| 290 | //D1 |
| 291 | final int hash = h(key) & INT_MASK; |
| 292 | int i = hash % keys.length; |
| 293 | |
| 294 | //D2 |
| 295 | int satus_i = status[i]; |
| 296 | if((keys[i] == key && satus_i != DELETED) || satus_i == EMPTY) |
| 297 | return extraInfo | i; |
| 298 | if(extraInfo == EXTRA_INDEX_INFO && satus_i == DELETED) |
| 299 | extraInfo = ((long)i) << 32; |
| 300 | |
| 301 | //D3 |
| 302 | final int c = 1 + (hash % (keys.length -2)); |
| 303 | |
| 304 | while(true)//this loop will terminate |
| 305 | { |
| 306 | //D4 |
| 307 | i -= c; |
| 308 | if(i < 0) |
| 309 | i += keys.length; |
| 310 | //D5 |
| 311 | satus_i = status[i]; |
| 312 | if( (keys[i] == key && satus_i != DELETED) || satus_i == EMPTY) |
| 313 | return extraInfo | i; |
| 314 | if(extraInfo == EXTRA_INDEX_INFO && satus_i == DELETED) |
| 315 | extraInfo = ((long)i) << 32; |
| 316 | } |
| 317 | } |
| 318 | |
| 319 | /** |
| 320 | * Returns a non-negative hash value |