com.limegroup.gnutella.routing
Class HashFunction

java.lang.Object
  extended bycom.limegroup.gnutella.routing.HashFunction

public class HashFunction
extends java.lang.Object

The official platform-independent hashing function for query-routing. The key property is that it allows interpolation of hash tables of different sizes. More formally k*hash(x,n)<=hash(x, kn)<=k*hash(x,n)+1.

This experimental version does not necessarily work cross-platform, however, nor is it secure in any sense. See Chapter 12.3.2. of for details of multiplication-based algorithms.


Constructor Summary
HashFunction()
           
 
Method Summary
static java.lang.String[] getPrefixes(java.lang.String[] words)
           
static int hash(java.lang.String x, byte bits)
           
static int hash(java.lang.String x, int start, int end, byte bits)
          Returns the same value as hash(x.substring(start, end), bits), but tries to avoid allocations.
static int keywordEnd(java.lang.String query, int i)
          Returns the index just past the end of the keyword starting at the i'th position of query, or query.length() if no such index.
static java.lang.String[] keywords(java.lang.String query)
          Returns a list of canonicalized keywords in the given query, suitable for passing to hash(String,int).
static int keywordStart(java.lang.String query, int i)
          Returns the index of the keyword starting at or after the i'th position of query, or -1 if no such luck.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

HashFunction

public HashFunction()
Method Detail

hash

public static int hash(java.lang.String x,
                       byte bits)

hash

public static int hash(java.lang.String x,
                       int start,
                       int end,
                       byte bits)
Returns the same value as hash(x.substring(start, end), bits), but tries to avoid allocations. Note that x is lower-cased when hashing.

Parameters:
x - the string to hash
bits - the number of bits to use in the resulting answer
start - the start offset of the substring to hash
end - just PAST the end of the substring to hash
Returns:
the hash value

keywords

public static java.lang.String[] keywords(java.lang.String query)
Returns a list of canonicalized keywords in the given query, suitable for passing to hash(String,int). The returned keywords are lower-cased, though that is not strictly needed as hash ignores case.


keywordStart

public static int keywordStart(java.lang.String query,
                               int i)
Returns the index of the keyword starting at or after the i'th position of query, or -1 if no such luck.


keywordEnd

public static int keywordEnd(java.lang.String query,
                             int i)
Returns the index just past the end of the keyword starting at the i'th position of query, or query.length() if no such index.


getPrefixes

public static java.lang.String[] getPrefixes(java.lang.String[] words)
Returns:
an array of strings with the original strings and prefixes