хэш-код класса случая scala с циклическими ссылками - PullRequest
Новая
       30

хэш-код класса случая scala с циклическими ссылками

0 голосов
/ 23 октября 2019

Как сказано в документации Scala: "Классы дел сравниваются по структуре, а не по ссылке".

Я пытался создать связанный список с циклом в нем, а затем добавить узел из этого зацикленного списка визменчивый набор. При использовании обычного класса это удалось, но с классом case я столкнулся с переполнением стека.

Мне любопытно, почему Scala не first проверяет ссылки перед проверкой структуры. Я думаю, что если ссылка одинакова, то структура гарантированно будет одинаковой, поэтому это может быть как ярлык, так и круговые ссылки.

Код: 

object CaseClassHashcodeExample {
  def main(args: Array[String]): Unit = {
    val head = new ListNode(0)
    head.appendToTail(1)
    head.appendToTail(2)
    head.appendToTail(3)
    head.next.next.next = head.next
    val set = collection.mutable.Set[ListNode]()
    set.add(head)
    assert(set(head))
  }
}

case class ListNode(var data: Int, var next: ListNode = null) {
  def appendToTail(d: Int): Unit = {
    val end = new ListNode(d)
    var cur = this
    while (cur.next != null)
      cur = cur.next
    cur.next = end
  }
}

1 Ответ

4 голосов
/ 23 октября 2019

Мне любопытно, почему Scala сначала не проверяет ссылки, прежде чем проверять структуру

Ну, что точно вы хотите проверить? Текущий сгенерированный код выглядит примерно так: 

def hashCode() = 31 * data.hashCode() + next.hashCode()

Одна вещь, которую вы можете попробовать, это 

def hashCode() = 31 * data.hashCode() + (if (next eq this) 0 else next.hashCode())

, но на самом деле это не поможет: в вашем случае это не next, чтотакой же, как this, это next.next.

next.hashCode не знает, что он вызывается с this.hashCode и поэтому не может сравнивать свои next с this.

Вы можете создать вспомогательный метод, принимая во внимание набор «видимых» объектов: 

def hashCode() = hashCode(Nil)
def hashCode(seen: List[ListNode]) = if (seen.exists(_ eq this)) 0 else 31 * data.hashCode() + next.hashCode(this :: seen)

Но это в значительной степени замедляет общий случай, и на самом деле это трудно сделать правильно.

РЕДАКТИРОВАТЬ: для equals, равенство ссылок сначала проверяется в случае классов. 

class NeverEq {
  override def equals(other: Any) = false
}

case class Test(x: NeverEq)

val x = Test(new NeverEq())
println(x == x)

печатает true и будет false, если сравнивать только структуру.

Но на самом деле это не помогает с циклическими ссылками. Допустим, у вас есть тип ListNode без data, чтобы упростить, который реализует равенство следующим образом: 

def equals(other: Any) = (this eq other) || (other match {
  case other: ListNode => this.next == other.next
})

и хотите проверить, если node1 == node2, где node1.next равно node2, и наоборот:

node1 <--> node2
  1. node1 == node2 уменьшается до (node1 eq node2) || (node1.next == node2.next).
  2. node1 eq node2 ложно, так что уменьшается до node1.next == node2.next, то есть node2 == node1.
  3. node2 eq node1 ложно, так что уменьшается до node2.next == node1.next, то есть node1 == node2 ...
...