The

It's using an

upper packed storage mode array to store the triangular matrix. In the Java programming language a 2D array is actually an array of arrays (also called a

jagged array) and as a result, not as efficient. In addition, storing the possible collision pairs only

requires a triangular portion of a 2D array. Instead, its much more efficient to use a 1D array that uses a calculation to index the triangular matrix elements. From the source, the element Aij can be found by doing this:

Code: Select all

`// i and j are the row/column indices`

// we compute the 1D array index using a formula

indexIn1DArray = i + (j * (j - 1) / 2);

Aij = array1d[indexIn1DArray];

Using a HashTable would work of course, but there's no need. We already have O(1) lookup time for the 1D array since we compute the index.

SemiSober wrote:i can't understand these lines :

CODE: SELECT ALL

if (current.id > test.id) {

matrix[test.id + (current.id * (current.id - 1) / 2)] = true;

} else {

matrix[current.id + (test.id * (test.id - 1) / 2)] = true;

}

This is the calculation of the 1D index of the 2D element. In other words, its setting the Aij element to true.

and why we should check their id ?

We check which id (index) is bigger because the calculation works only when j >= i.

William