private Integer applyWithEntry ( K key , Entry < K > entry , boolean tryRehashing ) { // Used to hold a new entry if one has to be created, or can re-use an entry passed in as a parameter. Entry < K > uninsertedEntry = entry ; // Holds a flag to indicate that a new sequence number has been taken. boolean createdNewEntry = false ; // Check if there is already an entry for the key, and return it if so. Entry < K > existingEntry = entryForKey ( key ) ; Integer result = null ; if ( existingEntry != null ) { result = existingEntry . seq ; } else { // Create a new entry, if one has not already been created and cached. if ( uninsertedEntry == null ) { uninsertedEntry = new Entry < K > ( ) ; uninsertedEntry . key = key ; uninsertedEntry . seq = nextSequenceNumber ; nextSequenceNumber ++ ; count ++ ; createdNewEntry = true ; result = uninsertedEntry . seq ; } // Attempt to insert the new entry. The sequence number is only incremented when this succeeds for a new // entry. Existing entries that are being re-hashed into a new table will not increment the sequence // number. while ( true ) { // Hash the entry for the current hash functions. int keyHashCode = uninsertedEntry . key . hashCode ( ) ; uninsertedEntry . hash1 = hash1 ( keyHashCode ) ; uninsertedEntry . hash2 = hash2 ( uninsertedEntry . hash1 , keyHashCode ) ; // Try and insert the entry, checking that no entry is left uninserted as a result. uninsertedEntry = cuckoo ( uninsertedEntry ) ; if ( uninsertedEntry == null ) { result = createdNewEntry ? result : - 1 ; break ; } // If the cuckoo algorithm fails then change the hash function/table size and try again. if ( tryRehashing ) { rehash ( ) ; } else { result = null ; break ; } } } return result ; }
Looks up the specified key in hash table using cuckoo hashing . If the key cannot be found in the table then the next available sequence number is allocated to it and a new entry is added to the hash table for the key again using cuckoo hashing .