package kapitel_09 /** * Beispiel aus * * - Algorithmen und Datenstrukturen für Dummies * - von Andreas Gogol-Döring und Thomas Letschert * - Verlag Wiley-VCH; Oktober 2019 * - Kapitel 9, Mengen und ihre Speicherung * * @author A. Gogol-Döring, Th. Letschert */ object AuD_09_06_HashTable_App extends App { /* * Hashtabellen gehören in jeder anständige Programmiersprache zu Grundausstattung, entweder als Sprachelement * oder als Bestandteil der API. Scala stellt veränderliche und unveränderliche Implementierungen von Mengen * und Abbildungen auf Basis von Hashtabellen zur Verfügung. Die einfache Version der Hash-Tabelle * kann natürlich auch leicht selbst implementiert werden: */ final class HashTable[K] private (N: Int, a: Array[List[K]]) { def this(N: Int) = this(N, a = Array.tabulate[List[K]](N)(i => List())) def insert(k: K): Unit = { val hc = k.hashCode() val i = hc % N if (!a(i).contains(k)) a(i) = k :: a(i) } def contains(k: K): Boolean = { val hc = k.hashCode() val i = hc % N a(i).contains(k) } } /* * Generell sollten natürlich die Klassen der API eigenen Implementierungen gegenüber bevorzugt werden. */ final case class Rabbit(name: String, var weight: Int) { override def equals(other: Any): Boolean = other match { case that: Rabbit => name == that.name case _ => false } override def hashCode(): Int = { 31 * name.hashCode() } } val HT = new HashTable[Rabbit](10) val egon = Rabbit("Egon", 3) HT.insert(egon) println(s"Ht contains light egon : ${HT.contains(egon)}") // true egon.weight = egon.weight + 5 println(s"Ht contains heavy egon : ${HT.contains(egon)}") // true }