dongjoon-hyun opened a new pull request, #59729:
URL: https://github.com/apache/spark/pull/59729
### What changes were proposed in this pull request?
This PR aims to include the shape and the entry positions in
`Matrix.hashCode` in both `org.apache.spark.ml.linalg` and
`org.apache.spark.mllib.linalg`.
- `ml.linalg.DenseMatrix.hashCode` and `ml.linalg.SparseMatrix.hashCode` now
mix `numRows` and `numCols` first, and then mix the column-major index and the
`##` of each value with `MurmurHash3.mix` in column-major order. As before, the
values with a zero hash code, such as `0.0` and `-0.0`, are skipped, so equal
dense and sparse matrices still have the same hash code.
- `ml.linalg.SparseMatrix.hashCode` visits its own `colPtrs`, `rowIndices`,
and `values` instead of using Breeze's `QuasiTensor.hashCode`. A transposed
sparse matrix is converted by `toSparseColMajor` first.
- `mllib.linalg.SparseMatrix.hashCode` delegates to `asML.hashCode` like
`mllib.linalg.DenseMatrix.hashCode`.
### Why are the changes needed?
`SparseMatrix.hashCode` uses Breeze's `QuasiTensor.hashCode`, and
`DenseMatrix.hashCode` computes the same hash code since SPARK-60296 (#59559).
This hash code mixes only the sequence of nonzero values and ignores the shape
and the positions of the values. As a result, many unequal matrices have the
same hash code. For example, all zero matrices have the hash code `43`, and all
`n x n` permutation matrices have the same hash code. The hash code of a 0/1
matrix depends only on the number of ones.
This causes heavy hash collisions and partition skew when matrices are used
as keys in hash-based collections and RDD operations.
```scala
import org.apache.spark.HashPartitioner
import org.apache.spark.ml.linalg.DenseMatrix
DenseMatrix.zeros(2, 3).hashCode == DenseMatrix.zeros(3, 2).hashCode //
Before: true, After: false
val a = new DenseMatrix(3, 1, Array(1.0, 0.0, 2.0))
val b = new DenseMatrix(3, 1, Array(1.0, 2.0, 0.0))
a.hashCode == b.hashCode // Before: true, After: false
val rnd = new scala.util.Random(42)
val matrices = Seq.fill(20000) {
new DenseMatrix(10, 10, Array.fill(100)(if (rnd.nextBoolean()) 1.0 else
0.0))
}
matrices.distinct.size // 20000
matrices.map(_.hashCode).distinct.size // Before: 40, After: 20000
val partitions = matrices.groupBy(new HashPartitioner(200).getPartition)
partitions.size // Before: 37, After: 200
partitions.values.map(_.size).max // Before: 2778, After: 123
```
### Does this PR introduce _any_ user-facing change?
Yes. The hash codes of `DenseMatrix` and `SparseMatrix` change in both `ml`
and `mllib`, and no longer match the hash codes of Breeze matrices. The
consistency with `equals` is unchanged, including the equality between a dense
matrix and a sparse matrix with the same entries.
### How was this patch tested?
Pass the CIs with the newly added test cases in `ml.linalg.MatricesSuite`
and `mllib.linalg.MatricesSuite`.
```
$ build/sbt 'mllib-local/testOnly *MatricesSuite'
$ build/sbt 'mllib/testOnly org.apache.spark.mllib.linalg.MatricesSuite'
```
### Was this patch authored or co-authored using generative AI tooling?
Generated-by: Claude Opus 5.5
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
