Top Description Fields Constructors Methods
org.hsqldb.map

public Class HashIndex

extends Object
Class Inheritance
Imports
java.util.Arrays
A chained bucket hash index implementation. hashTable and linkTable are arrays of signed integral types. This implementation uses int as the type but short or byte can be used for smaller index sizes (cardinality). hashTable[index] contains the pointer to the first node with (index == hash modulo hashTable.length) or -1 if there is no corresponding node. linkTable[{0,newNodePointer}] (the range between 0 and newNodePointer) contains either the pointer to the next node or -1 if there is no such node. reclaimedNodeIndex contains a pointer to an element of linkTable which is the first element in the list of reclaimed nodes (nodes no longer in index) or -1 if there is no such node. elements at and above linkTable[newNodePointer] have never been used as a node and their contents is not significant.
Author
Fred Toussi (fredt@users dot sourceforge.net)
Since
1.7.2
Version
2.6.0

Field Summary

Modifier and TypeField and Description
pack-priv int
elementCount

pack-priv boolean
fixedSize

pack-priv int[]
hashTable

pack-priv int[]
linkTable

pack-priv boolean
modified

pack-priv int
newNodePointer

pack-priv int
reclaimedNodePointer

Constructor Summary

AccessConstructor and Description
public
HashIndex(int hashTableSize, int capacity, boolean fixedSize)

Method Summary

Modifier and TypeMethod and Description
public void
clear()

Reset the index as empty.

public HashIndex
clone()

Overrides java.lang.Object.clone.

Creates and returns a copy of this object.

public int
getElementCount()

public int
getHashIndex(int
hash value
hash)

public int
getLimitPointer()

public int

Returns:

either -1 or the first node for this hash value
getLookup(int
the hash value used for indexing
hash)

Return the array index for a hash.

public int
getNewNodePointer()

Return the pointer

public int

Returns:

either -1 or the next node from this node
getNextLookup(int
A valid node to look from
lookup)

This looks from a given node, so the parameter is always > -1.

public boolean

Returns:

true if node found in unlinked state
insertEmptyNode(int
the node to remove
lookup)

Insert a node.

public int

Returns:

the new node
linkNode(int
an index into hashTable
index, final int
either -1 or the node to which the new node will be linked
lastLookup)

Link a new node into the linked list for a hash index.

public boolean

Returns:

true if node found in unlinked state
removeEmptyNode(int
the node to remove
lookup)

Remove a node that has already been unlinked.

public void
reset(int
size
hashTableSize, int
capacity
capacity)

Reset the structure with a new size as empty.

public void
resetTables()

public void
unlinkNode(int
an index into hashTable
index, int
either -1 or the node to which the target node is linked
lastLookup, int
the node to remove
lookup)

Unlink a node from a linked list and link into the reclaimed list.

Inherited from java.lang.Object:
equalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

elementCountback to summary
pack-priv int elementCount
fixedSizeback to summary
pack-priv boolean fixedSize
hashTableback to summary
pack-priv int[] hashTable
linkTableback to summary
pack-priv int[] linkTable
modifiedback to summary
pack-priv boolean modified
newNodePointerback to summary
pack-priv int newNodePointer
reclaimedNodePointerback to summary
pack-priv int reclaimedNodePointer

Constructor Detail

HashIndexback to summary
public HashIndex(int hashTableSize, int capacity, boolean fixedSize)

Method Detail

clearback to summary
public void clear()

Reset the index as empty.

cloneback to summary
public HashIndex clone()

Overrides java.lang.Object.clone.

Doc from java.lang.Object.clone.

Creates and returns a copy of this object. The precise meaning of "copy" may depend on the class of the object. The general intent is that, for any object x, the expression: 

x.clone() != x
will be true, and that the expression: 
x.clone().getClass() == x.getClass()
will be true, but these are not absolute requirements. While it is typically the case that: 
x.clone().equals(x)
will be true, this is not an absolute requirement.

By convention, the returned object should be obtained by calling super.clone. If a class and all of its superclasses (except Object) obey this convention, it will be the case that x.clone().getClass() == x.getClass().

By convention, the object returned by this method should be independent of this object (which is being cloned). To achieve this independence, it may be necessary to modify one or more fields of the object returned by super.clone before returning it. Typically, this means copying any mutable objects that comprise the internal "deep structure" of the object being cloned and replacing the references to these objects with references to the copies. If a class contains only primitive fields or references to immutable objects, then it is usually the case that no fields in the object returned by super.clone need to be modified.

getElementCountback to summary
public int getElementCount()
getHashIndexback to summary
public int getHashIndex(int hash)
Parameters
hash:int

hash value

getLimitPointerback to summary
public int getLimitPointer()
getLookupback to summary
public int getLookup(int hash)

Return the array index for a hash.

Parameters
hash:int

the hash value used for indexing

Returns:int

either -1 or the first node for this hash value

getNewNodePointerback to summary
public int getNewNodePointer()

Return the pointer

getNextLookupback to summary
public int getNextLookup(int lookup)

This looks from a given node, so the parameter is always > -1.

Parameters
lookup:int

A valid node to look from

Returns:int

either -1 or the next node from this node

insertEmptyNodeback to summary
public boolean insertEmptyNode(int lookup)

Insert a node.

Parameters
lookup:int

the node to remove

Returns:boolean

true if node found in unlinked state

linkNodeback to summary
public int linkNode(int index, final int lastLookup)

Link a new node into the linked list for a hash index.

Parameters
index:int

an index into hashTable

lastLookup:int

either -1 or the node to which the new node will be linked

Returns:int

the new node

removeEmptyNodeback to summary
public boolean removeEmptyNode(int lookup)

Remove a node that has already been unlinked. This is not required for index operations. It is used only when the row needs to be removed from the data structures that store the actual indexed data and the nodes need to be contiguous.

Parameters
lookup:int

the node to remove

Returns:boolean

true if node found in unlinked state

resetback to summary
public void reset(int hashTableSize, int capacity)

Reset the structure with a new size as empty.

Parameters
hashTableSize:int

size

capacity:int

capacity

resetTablesback to summary
public void resetTables()
unlinkNodeback to summary
public void unlinkNode(int index, int lastLookup, int lookup)

Unlink a node from a linked list and link into the reclaimed list.

Parameters
index:int

an index into hashTable

lastLookup:int

either -1 or the node to which the target node is linked

lookup:int

the node to remove