org.metastatic.rsync
Class TwoKeyMap

java.lang.Object
  |
  +--org.metastatic.rsync.TwoKeyMap
All Implemented Interfaces:
Map, Serializable

public class TwoKeyMap
extends Object
implements Serializable, Map

This is a "double-keyed" mapping. The first key is a 16-bit integer, and the second key is a variable-length byte array. With this, we can compute if a given mapping is "probably" in the map using the first key, and compute whether or not a mapping is definitely in the hashtable with the second key. The rationale behind this is that the first key is trivial to compute and that the second key is more difficult to compute but more unique.

Since the strong key can be a byte array of any length, then this "strong" key can be shorter (and thus less unique) than the "weak" key. For this class to work properly, the stronger key should be at least four bytes in length, preferably longer.

The weak-key/strong-key method is inspired by (and is was written for) the "hashtable" in the rsync algorithm, and has three levels of key search:

  1. Test if the lower 2 bytes of the weak key (the positive part of a 32-bit integer in Java) have been mapped to anything yet. This method always takes O(1) time, and it is assumed that the weak key is trivial to compute.
  2. Test if the entire weak key is mapped to anything. Since this class uses a linked list to handle collisions where the lower 2 bytes are the same, this method takes at most O(n) operations (also assuming that the weak key is trivial to compute).
  3. Test if both the weak and strong keys map to an Object. In addition to the linked-list search of the second step, this involves a search of a red-black tree, meaning that the upper-bound time complexity ranges from O(lg(n)) to O(n). This works under the assumption that the strong key is some sort of MessageDigest, and thus takes longer to compute.

With this method, we can determine if it is worth it to compute the strong key if we have already computed the weak key.

null is not a valid key in this map.

See Also:
Serialized Form

Nested Class Summary
 class TwoKeyMap.StrongKey
          The stronger of the two keys in this Map.
 class TwoKeyMap.SubTable
          A Map.Entry that contains another Map that is keyed with stronger, larger keys, and links to other SubTables whose TwoKeyMap.SubTable.key's lower four bytes are equivalent.
 
Field Summary
protected  TwoKeyMap.SubTable[] tables
          The sub-tables whose keys are the larger, stronger keys.
 
Constructor Summary
TwoKeyMap()
          Creates a new Map with 2^16 sub-tables.
TwoKeyMap(Map m)
          Create a new Map with all the mappings of the given map.
 
Method Summary
 void clear()
          Clear this Map.
 boolean containsKey(int key)
          Test if the map contains the lower two bytes of the weak key.
 boolean containsKey(Object key)
          Test if this map contains either the supplied weak key (if the argument is an Integer) or both the weak and strong keys (if the argument is a ChecksumPair).
 boolean containsValue(Object value)
          Test if the given value is in one of the sub-tables.
 Set entrySet()
          Return an unmodifiable set of the SubTable objects in this class.
 boolean equals(Object o)
          Test if this object equals another.
 Object get(Object key)
          Get the object mapped to by the given key pair.
 int hashCode()
          Return the hash code of this object.
 boolean isEmpty()
          Test if there are no mappings in this map.
 Set keySet()
          Return an unmodifiable set of all the pairs of keys in this mapping.
 Object put(Object key, Object value)
          Put the given object at the location specified by a key pair.
 void putAll(Map m)
          Put every entry in m in this map.
 Object remove(Object key)
          Removes a single mapping if the argument is a ChecksumPair, or an entire TwoKeyMap.SubTable if the argument is a Integer.
 int size()
          Return the number of mappings.
 String toString()
          Create a printable version of this Map.
 Collection values()
          Return a Collection of all the values mapped by this object.
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
 

Field Detail

tables

protected final TwoKeyMap.SubTable[] tables
The sub-tables whose keys are the larger, stronger keys. The index of this array is the shorter, weaker key.

Since:
1.1
Constructor Detail

TwoKeyMap

public TwoKeyMap()
Creates a new Map with 2^16 sub-tables.

Since:
1.1

TwoKeyMap

public TwoKeyMap(Map m)
Create a new Map with all the mappings of the given map.

Parameters:
m - The initial mappings this Map should contain.
Throws:
ClassCastException - If one of the keys in m is not a ChecksumPair.
NullPointerException - If one of the keys in m is null.
Since:
1.1
Method Detail

containsKey

public boolean containsKey(int key)
Test if the map contains the lower two bytes of the weak key. This is the fastest, and least accurate containsKey method.

Parameters:
key - The key to check.
Returns:
true If the index key & 0xffff in tables is non-null.
Since:
1.1

put

public Object put(Object key,
                  Object value)
Put the given object at the location specified by a key pair.

Specified by:
put in interface Map
Parameters:
key - The ChecksumPair to use as the key.
value - The value to map to.
Returns:
The old value mapped, if any.
Since:
1.1

containsKey

public boolean containsKey(Object key)
Test if this map contains either the supplied weak key (if the argument is an Integer) or both the weak and strong keys (if the argument is a ChecksumPair).

Specified by:
containsKey in interface Map
Parameters:
key - The key to check.
Returns:
true If the map contains the given weak key (if key is an Integer) or the given pair of keys (if key is a ChecksumPair).
Since:
1.1

get

public Object get(Object key)
Get the object mapped to by the given key pair. The argument SHOULD be a ChecksumPair.

Specified by:
get in interface Map
Parameters:
key - The key of the object to get.
Returns:
The object keyed by key, or null if there is no such object.
Since:
1.1

clear

public void clear()
Clear this Map.

Specified by:
clear in interface Map
Since:
1.1

containsValue

public boolean containsValue(Object value)
Test if the given value is in one of the sub-tables.

Specified by:
containsValue in interface Map
Parameters:
value - The value to search for.
Returns:
true if value is in this Map.
Since:
1.1

entrySet

public Set entrySet()
Return an unmodifiable set of the SubTable objects in this class.

Specified by:
entrySet in interface Map
Returns:
A set of all sub-tables from this class.
Since:
1.1

equals

public boolean equals(Object o)
Test if this object equals another.

Specified by:
equals in interface Map
Overrides:
equals in class Object
Returns:
true if o is an instance of this class and if it contains the same sub-tables.
Throws:
ClassCastException - if o is not an instance of this class.
NullPointerException - if o is null.
Since:
1.1

hashCode

public int hashCode()
Return the hash code of this object.

Specified by:
hashCode in interface Map
Overrides:
hashCode in class Object
Returns:
The hash code of this object.
Since:
1.1

isEmpty

public boolean isEmpty()
Test if there are no mappings in this map.

Specified by:
isEmpty in interface Map
Returns:
true if this map is empty.
Since:
1.1

keySet

public Set keySet()
Return an unmodifiable set of all the pairs of keys in this mapping.

Specified by:
keySet in interface Map
Returns:
A set of all the ChecksumPairs in this mapping.
Since:
1.1

putAll

public void putAll(Map m)
Put every entry in m in this map. This method will only work if the keys of m are of type ChecksumPair.

Specified by:
putAll in interface Map
Parameters:
m - The mappings to put.
Throws:
ClassCastException - If every key in m is not a ChecksumPair.
NullPointerException - If a key in m is null.
Since:
1.1
See Also:
put(Object,Object)

remove

public Object remove(Object key)
Removes a single mapping if the argument is a ChecksumPair, or an entire TwoKeyMap.SubTable if the argument is a Integer.

Specified by:
remove in interface Map
Parameters:
key - The key of the object to be removed.
Returns:
The removed object, if such a mapping existed. null otherwise.
Since:
1.1

size

public int size()
Return the number of mappings.

Specified by:
size in interface Map
Returns:
The number of mappings.
Since:
1.1

values

public Collection values()
Return a Collection of all the values mapped by this object.

Specified by:
values in interface Map
Returns:
A Collection of all values mapped by this object.
Since:
1.1

toString

public String toString()
Create a printable version of this Map.

Overrides:
toString in class Object
Returns:
A String representing this object.
Since:
1.1