Efficient string hash computation

Abstract

A method for efficiently computing a hash value for a string is disclosed. In one embodiment, such a method includes receiving an original string comprising multiple characters. The method computes an original hash value for the original string. The method produces an updated string by performing at least one of the following updates on the original string: adding leading/trailing characters to the original string; removing leading/trailing characters from the original string, and modifying characters of the original string while preserving the length of the original string. The method then computes an updated hash value for the updated string by performing at least one operation on the original hash value, wherein the at least one operation takes into account the updates that were made to the original string. A corresponding apparatus and computer program product are also disclosed.

1 - 10 . (canceled) 
     
     
         11 . A computer program product for efficiently computing a hash value for a string, the computer program product comprising a non-transitory computer-readable storage medium having computer-usable program code embodied therein, the computer-usable program code comprising:
 computer-usable program code to receive an original string comprising a plurality of characters;   computer-usable program code to compute an original hash value for the original string;   computer-usable program code to produce an updated string by performing at least one of the following updates on the original string: add leading/trailing characters to the original string; remove leading/trailing characters from the original string, and modify characters of the original string; and   computer-usable program code to compute an updated hash value for the updated string by performing at least one operation on the original hash value, wherein the at least one operation takes into account the updates that were made to the original string.   
     
     
         12 . The computer program product of  claim 11 , wherein producing an updated string comprises concatenating a new substring to the original string. 
     
     
         13 . The computer program product of  claim 12 , further comprising computer-usable program code to compute a new hash value for the new substring. 
     
     
         14 . The computer program product of  claim 13 , wherein computing the updated hash value comprises computing the updated hash value as a function of the original hash value and the new hash value. 
     
     
         15 . The computer program product of  claim 11 , wherein producing an updated string comprises removing a substring from the original string. 
     
     
         16 . The computer program product of  claim 15 , further comprising computer-usable program code to compute a hash value for the removed substring. 
     
     
         17 . The computer program product of  claim 16 , wherein computing the updated hash value comprises computing the updated hash value as a function of the original hash value and the hash value of the removed substring. 
     
     
         18 . The computer program product of  claim 11 , wherein producing an updated string comprises modifying a substring within the original string while preserving the length of the original string. 
     
     
         19 . The computer program product of  claim 18 , further comprising computer-usable program code to compute a hash value for the modified substring. 
     
     
         20 . The computer program product of  claim 19 , wherein computing the updated hash value comprises computing the updated hash value as a function of the original hash value and the hash value of the modified substring. 
     
     
         21 . An apparatus for efficiently computing a hash value for a string, the apparatus comprising:
 at least one processor;   at least one memory device coupled to the at least one processor and storing computer instructions for execution on the at least one processor, the computer instructions enabling the at least one processor to:
 receive an original string comprising a plurality of characters; 
 compute an original hash value for the original string; 
 produce an updated string by performing at least one of the following updates on the original string: add leading/trailing characters to the original string; remove leading/trailing characters from the original string, and modify characters of the original string; and 
 compute an updated hash value for the updated string by performing at least one operation on the original hash value, wherein the at least one operation takes into account the updates that were made to the original string.