private Entry < K > cuckoo ( Entry < K > entry ) { // Holds the entry currently being placed in the hash table. Entry < K > currentEntry = entry ; // Holds the index into the hash table where the current entry will be placed. int hash = entry . hash1 ; int index = indexFor ( hash ) ; Entry < K > nextEntry = hashTable [ index ] ; int previousFlag = 0 ; int [ ] previousIndex = new int [ 2 ] ; int [ ] previousSeq = new int [ 2 ] ; for ( int i = 0 ; i < hashTableSize ; i ++ ) { // Check the current index, to see if it is an empty slot. If it is an empty slot then the current // entry is placed there and the algorithm completes. if ( nextEntry == null ) { hashTable [ index ] = currentEntry ; return null ; } // If the current index does not point to an empty slot, the current entry is placed there anyway, but the // displaced entry (the egg displaced by the cuckoo) becomes the current entry for placing. hashTable [ index ] = currentEntry ; currentEntry = nextEntry ; // A new index is selected depending on whether the entry is currently at its primary or secondary hashing. int firstPosition = indexFor ( currentEntry . hash1 ) ; hash = ( index == firstPosition ) ? currentEntry . hash2 : currentEntry . hash1 ; index = indexFor ( hash ) ; // A check for infinite loops of size 2 is made here, to circumvent the simplest and most common infinite // looping condition. previousIndex [ previousFlag ] = index ; previousSeq [ previousFlag ] = nextEntry . seq ; previousFlag = ( previousFlag == 1 ) ? 0 : 1 ; nextEntry = hashTable [ index ] ; if ( ( nextEntry != null ) && ( index == previousIndex [ previousFlag ] ) && ( nextEntry . seq == previousSeq [ previousFlag ] ) ) { break ; } } return currentEntry ; }
Adds a new entry to a hash table using the cuckoo algorithm .