static int [ ] unwrappingGetItems ( final PairTable table , final int numPairs ) { if ( numPairs < 1 ) { return null ; } final int [ ] slotsArr = table . slotsArr ; final int tableSize = 1 << table . lgSizeInts ; final int [ ] result = new int [ numPairs ] ; int i = 0 ; int l = 0 ; int r = numPairs - 1 ; // Special rules for the region before the first empty slot. final int hiBit = 1 << ( table . validBits - 1 ) ; while ( ( i < tableSize ) && ( slotsArr [ i ] != - 1 ) ) { final int item = slotsArr [ i ++ ] ; if ( ( item & hiBit ) != 0 ) { result [ r -- ] = item ; } // This item was probably wrapped, so move to end. else { result [ l ++ ] = item ; } } // The rest of the table is processed normally. while ( i < tableSize ) { final int look = slotsArr [ i ++ ] ; if ( look != - 1 ) { result [ l ++ ] = look ; } } assert l == ( r + 1 ) ; return result ; }
While extracting the items from a linear probing hashtable this will usually undo the wrap - around provided that the table isn t too full . Experiments suggest that for sufficiently large tables the load factor would have to be over 90 percent before this would fail frequently and even then the subsequent sort would fix things up .