This is an automated email from the ASF dual-hosted git repository.
dongjoon-hyun pushed a commit to branch branch-4.x
in repository https://gitbox.apache.org/repos/asf/spark.git
The following commit(s) were added to refs/heads/branch-4.x by this push:
new 94f791a15462 [SPARK-60491][MLLIB] Include the shape and the entry
positions in `Matrix.hashCode`
94f791a15462 is described below
commit 94f791a154626668d9f537b12946cce3efb31cee
Author: Dongjoon Hyun <[email protected]>
AuthorDate: Fri Oct 23 05:17:13 2026 -0700
[SPARK-60491][MLLIB] Include the shape and the entry positions in
`Matrix.hashCode`
### What changes were proposed in this pull request?
This PR improves `Matrix.hashCode` in both `org.apache.spark.ml.linalg` and
`org.apache.spark.mllib.linalg` by including the shape and the entry positions.
| Class | Change in this PR | Result |
|---|---|---|
| `ml.linalg.DenseMatrix` | Updates `hashCode` | Includes the shape and the
entry positions |
| `ml.linalg.SparseMatrix` | Computes `hashCode` itself instead of
delegating to Breeze | Includes the shape and the entry positions |
| `mllib.linalg.DenseMatrix` | None (delegates to `asML.hashCode` since
SPARK-60296) | Fixed by the `ml` change |
| `mllib.linalg.SparseMatrix` | Delegates to `asML.hashCode` instead of
`asBreeze.hashCode` | Fixed by the `ml` change |
The new hash code mixes `numRows` and `numCols` first, and then mixes 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`, and converts a transposed sparse matrix by
`toSparseColMajor` first.
### Why are the changes needed?
`SparseMatrix.hashCode` has delegated to Breeze since Apache Spark
[v2.0.0](https://github.com/apache/spark/releases/tag/v2.0.0) (2016-07-26)
(SPARK-6429), and Breeze's `QuasiTensor.hashCode` mixes only the sequence of
nonzero values, ignoring 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` regardless of their shapes, and all `n x n`
permutation matrices have the same hash cod [...]
```scala
import org.apache.spark.HashPartitioner
import org.apache.spark.ml.linalg.{DenseMatrix, SparseMatrix}
val z1 = SparseMatrix.fromCOO(2, 3, Seq.empty)
val z2 = SparseMatrix.fromCOO(3, 2, Seq.empty)
z1.hashCode == z2.hashCode // Before: true, After: false
val a = SparseMatrix.fromCOO(3, 1, Seq((0, 0, 1.0), (2, 0, 2.0)))
val b = SparseMatrix.fromCOO(3, 1, Seq((0, 0, 1.0), (1, 0, 2.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)).toSparse
}
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
```
`DenseMatrix.hashCode` has the same problem because SPARK-60296 (#59559)
made it compute the same hash code as `SparseMatrix.hashCode` to be consistent
with `equals`.
### 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
Closes #59729 from dongjoon-hyun/SPARK-60491.
Authored-by: Dongjoon Hyun <[email protected]>
Signed-off-by: Dongjoon Hyun <[email protected]>
(cherry picked from commit 70ba7bef612fe5d677231b5429437c6c88c45fa0)
Signed-off-by: Dongjoon Hyun <[email protected]>
---
.../org/apache/spark/ml/linalg/Matrices.scala | 30 +++++++++++++++++-----
.../org/apache/spark/ml/linalg/MatricesSuite.scala | 27 +++++++++++++++++++
.../org/apache/spark/mllib/linalg/Matrices.scala | 2 +-
.../apache/spark/mllib/linalg/MatricesSuite.scala | 14 ++++++++++
4 files changed, 66 insertions(+), 7 deletions(-)
diff --git
a/mllib-local/src/main/scala/org/apache/spark/ml/linalg/Matrices.scala
b/mllib-local/src/main/scala/org/apache/spark/ml/linalg/Matrices.scala
index 55e109162542..471036991b7e 100644
--- a/mllib-local/src/main/scala/org/apache/spark/ml/linalg/Matrices.scala
+++ b/mllib-local/src/main/scala/org/apache/spark/ml/linalg/Matrices.scala
@@ -333,16 +333,17 @@ class DenseMatrix @Since("2.0.0") (
}
override def hashCode: Int = {
- // Matches SparseMatrix.hashCode (Breeze's QuasiTensor.hashCode) so that
equal dense and
- // sparse matrices have the same hash code. The values are visited in
column major order
- // and those with a zero hash code, such as 0.0 and -0.0, are skipped.
+ // Matches SparseMatrix.hashCode so that equal dense and sparse matrices
have the same hash
+ // code. The shape is mixed first, and then the column major index and the
value of each
+ // entry are mixed in column major order. The values with a zero hash
code, such as 0.0 and
+ // -0.0, are skipped.
val data = if (isTransposed) toArray else values
- var hash = 43
+ var hash = MurmurHash3.mix(MurmurHash3.mix(43, numRows), numCols)
var i = 0
while (i < data.length) {
val valueHash = data(i).##
if (valueHash != 0) {
- hash = MurmurHash3.mix(hash, valueHash)
+ hash = MurmurHash3.mix(MurmurHash3.mix(hash, i), valueHash)
}
i += 1
}
@@ -669,7 +670,24 @@ class SparseMatrix @Since("2.0.0") (
rowIndices: Array[Int],
values: Array[Double]) = this(numRows, numCols, colPtrs, rowIndices,
values, false)
- override def hashCode(): Int = asBreeze.hashCode()
+ override def hashCode(): Int = {
+ // Matches DenseMatrix.hashCode. The entries are visited in column major
order.
+ val m = if (isTransposed) toSparseColMajor else this
+ var hash = MurmurHash3.mix(MurmurHash3.mix(43, numRows), numCols)
+ var j = 0
+ while (j < numCols) {
+ var k = m.colPtrs(j)
+ while (k < m.colPtrs(j + 1)) {
+ val valueHash = m.values(k).##
+ if (valueHash != 0) {
+ hash = MurmurHash3.mix(MurmurHash3.mix(hash, m.rowIndices(k) + j *
numRows), valueHash)
+ }
+ k += 1
+ }
+ j += 1
+ }
+ hash
+ }
override def equals(o: Any): Boolean = o match {
case m: Matrix => asBreeze == m.asBreeze
diff --git
a/mllib-local/src/test/scala/org/apache/spark/ml/linalg/MatricesSuite.scala
b/mllib-local/src/test/scala/org/apache/spark/ml/linalg/MatricesSuite.scala
index 9de9cbf5b130..af31f94eea63 100644
--- a/mllib-local/src/test/scala/org/apache/spark/ml/linalg/MatricesSuite.scala
+++ b/mllib-local/src/test/scala/org/apache/spark/ml/linalg/MatricesSuite.scala
@@ -154,6 +154,33 @@ class MatricesSuite extends SparkMLFunSuite {
assert(dmx.hashCode === dmx.toSparse.hashCode)
}
+ test("SPARK-60491: Matrix.hashCode depends on the shape and the positions of
the entries") {
+ val values = Array(1.0, 2.0, 3.0, 4.0, 5.0, 6.0)
+ // The same values in different shapes.
+ val reshaped = Seq(new DenseMatrix(2, 3, values), new DenseMatrix(3, 2,
values),
+ new DenseMatrix(1, 6, values))
+ // Zero matrices in different shapes.
+ val zeros = Seq(DenseMatrix.zeros(2, 3), DenseMatrix.zeros(3, 2),
DenseMatrix.zeros(1, 6))
+ // The same values at different positions.
+ val moved = Seq(Array(1.0, 0.0, 2.0), Array(1.0, 2.0, 0.0), Array(0.0,
1.0, 2.0))
+ .map(v => new DenseMatrix(3, 1, v))
+ // All 4 x 4 permutation matrices.
+ val permutations = (0 until 4).permutations.map { rows =>
+ val v = new Array[Double](16)
+ rows.zipWithIndex.foreach { case (i, j) => v(i + 4 * j) = 1.0 }
+ new DenseMatrix(4, 4, v)
+ }.toSeq
+ Seq(reshaped, zeros, moved, permutations).foreach { matrices =>
+ assert(matrices.map(_.hashCode).distinct.length === matrices.length)
+ matrices.foreach { m =>
+ Seq(m.toDenseRowMajor, m.toSparseColMajor, m.toSparseRowMajor).foreach
{ other =>
+ assert(other === m)
+ assert(other.hashCode === m.hashCode)
+ }
+ }
+ }
+ }
+
test("matrix indexing and updating") {
val m = 3
val n = 2
diff --git a/mllib/src/main/scala/org/apache/spark/mllib/linalg/Matrices.scala
b/mllib/src/main/scala/org/apache/spark/mllib/linalg/Matrices.scala
index 7cd851de91a5..da00b3440f13 100644
--- a/mllib/src/main/scala/org/apache/spark/mllib/linalg/Matrices.scala
+++ b/mllib/src/main/scala/org/apache/spark/mllib/linalg/Matrices.scala
@@ -621,7 +621,7 @@ class SparseMatrix @Since("1.3.0") (
case _ => false
}
- override def hashCode(): Int = asBreeze.hashCode
+ override def hashCode(): Int = asML.hashCode
private[mllib] def asBreeze: BM[Double] = {
if (!isTransposed) {
diff --git
a/mllib/src/test/scala/org/apache/spark/mllib/linalg/MatricesSuite.scala
b/mllib/src/test/scala/org/apache/spark/mllib/linalg/MatricesSuite.scala
index d5f77c8f3ed6..5d88b1b8e37d 100644
--- a/mllib/src/test/scala/org/apache/spark/mllib/linalg/MatricesSuite.scala
+++ b/mllib/src/test/scala/org/apache/spark/mllib/linalg/MatricesSuite.scala
@@ -174,6 +174,20 @@ class MatricesSuite extends SparkFunSuite {
}
}
+ test("SPARK-60491: Matrix.hashCode depends on the shape and the positions of
the entries") {
+ val values = Array(1.0, 2.0, 3.0, 4.0, 5.0, 6.0)
+ val matrices = Seq(new DenseMatrix(2, 3, values), new DenseMatrix(3, 2,
values),
+ new DenseMatrix(3, 2, Array(1.0, 0.0, 2.0, 0.0, 3.0, 0.0)),
+ new DenseMatrix(3, 2, Array(1.0, 2.0, 0.0, 3.0, 0.0, 0.0)))
+ assert(matrices.map(_.hashCode).distinct.length === matrices.length)
+ matrices.foreach { m =>
+ assert(m.toSparse === m)
+ assert(m.toSparse.hashCode === m.hashCode)
+ assert(m.toSparse.transpose === m.transpose)
+ assert(m.toSparse.transpose.hashCode === m.transpose.hashCode)
+ }
+ }
+
test("matrix indexing and updating") {
val m = 3
val n = 2
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]