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)
| 109 | * and the position that the key is in or the first EMPTY position found |
| 110 | */ |
| 111 | private long getIndex(int key) |
| 112 | { |
| 113 | long extraInfo = EXTRA_INDEX_INFO; |
| 114 | //D1 |
| 115 | final int hash = h(key) & INT_MASK; |
| 116 | int i = hash % keys.length; |
| 117 | |
| 118 | //D2 |
| 119 | int satus_i = status[i]; |
| 120 | if((keys[i] == key && satus_i != DELETED) || satus_i == EMPTY) |
| 121 | return extraInfo | i; |
| 122 | if(extraInfo == EXTRA_INDEX_INFO && satus_i == DELETED) |
| 123 | extraInfo = ((long)i) << 32; |
| 124 | |
| 125 | //D3 |
| 126 | final int c = 1 + (hash % (keys.length -2)); |
| 127 | |
| 128 | while(true)//this loop will terminate |
| 129 | { |
| 130 | //D4 |
| 131 | i -= c; |
| 132 | if(i < 0) |
| 133 | i += keys.length; |
| 134 | //D5 |
| 135 | satus_i = status[i]; |
| 136 | if( (keys[i] == key && satus_i != DELETED) || satus_i == EMPTY) |
| 137 | return extraInfo | i; |
| 138 | if(extraInfo == EXTRA_INDEX_INFO && satus_i == DELETED) |
| 139 | extraInfo = ((long)i) << 32; |
| 140 | } |
| 141 | } |
| 142 | |
| 143 | private void enlargeIfNeeded() |
| 144 | { |