Hashing

Es gibt bereits viele Implementierungen von Hash-Tabellen, jedoch leiden viele darunter, dass das häufige Löschen von Einträgen zu einer deutlichen Performance-Verschlechterung führt. Deshalb habe ich einen Algorithmus aus dem Jahr 1989 genommen, um eine eigene Implementierung in Scala zu erstellen. Beschrieben wird der Algorithmus im Journal of Algorithms, Volume 10, 1989 im Artikel Hash table collision resolution with direct chaining von Gary D. Knott und Pilar De La Torre.

Hashing

Geschlossenes Hashing

Die Hash-Tabelle ist ein Array, dessen Größe sich aus den (wahrscheinlich) zu speichernden Elementen (floor) und einem Puffer (cellar) berechnet. Eine spätere Änderung der Größe ist nicht vorgesehen.

In dem Array werden die Elemente an der durch den Hash berechneten Position abgelegt. Kollisionen werden dadurch behandelt, dass Elemente mit dem gleichen Hash-Wert in einer linearen Liste gespeichert werden. Diese Liste wird im eigentlichen Array gespeichert, so dass der gesamte Speicherverbrauch minimal ist.

Das größte Problem tritt auf, wenn ein neues Element an einer Stelle gespeichert werden soll, die bereits durch ein Listenelement belegt ist. Dies wäre im Fall einer doppelt verketteten Liste nicht weiter schwierig, aber in diesem Algorithmus wird sehr elegant eine einfach verkettete Liste verwendet.

class FastHashMap[K: ClassManifest, V: ClassManifest](
  val floor: Int,
  val cellar: Int ) {

  import FastHashMap.NIL

  require( floor > 0 )
  require( cellar >= 0 )

  def this( floor: Int ) = this( floor, ( floor * 16 ) / 100 )
  def this() = this( FastHashMap.DEFAULT_FLOOR )

  def size = count;
  def isEmpty = ( size == 0 )

  def put( key: K, value: V ): Option[V] = {
    def handleUsedEntry( entry: Int ): Option[V] = {
      def changeValue( entry: Int, newValue: V ): V = {
        val oldValue = values( entry )
        values( entry ) = value
        oldValue
      }
      def writeEntry( entry: Int ) {
        def prepareFreeEntry( free: Int, entry: Int ) {
          link( free ) = link( entry )
          fsl( free ) = fsl( entry )
          chainStart( free ) = false
          used( free ) = true
        }
        def insertIntoChain( entry: Int, free: Int ) {
          setEntry( free, key, value )
          link( entry ) = free
        }
        def movePreviousEntry( entry: Int, free: Int ) {
          val pred = getPred( entry )
          link( pred ) = free

          setEntry( free, keys( entry ), values( entry ) )
          setEntry( entry, key, value )
          link( entry ) = NIL
          fsl( entry ) = false
          chainStart( entry ) = true
        }

        val free = getFreeEntry
        prepareFreeEntry( free, entry )
        if ( chainStart( entry ) ) insertIntoChain( entry, free )
        else movePreviousEntry( entry, free )
      }

      if ( keys( entry ) == key ) { Some( changeValue( entry, value ) ) }
      else { writeEntry( entry ); None }
    }

    def handleUnusedEntry( entry: Int ) {
      if ( entry == fslStart ) {
        getFreeEntry
        link( entry ) = NIL
        fsl( entry ) = false
      }

      setEntryUsed( entry, key, value )
    }

    if ( size == tableSize )
      None

    count += 1
    val entry = hash( key )

    if ( used( entry ) ) handleUsedEntry( entry )
    else { handleUnusedEntry( entry ); None }
  }

  def get( key: K ): Option[V] = {
    def findEntry( entry: Int ): Option[V] = {
      if ( entry == NIL || chainStart( entry ) ) None
      else if ( keys( entry ) == key ) Some( values( entry ) )
      else findEntry( link( entry ) )
    }
    val entry = hash( key )
    if ( !used( entry ) || !chainStart( entry ) ) None
    else if ( keys( entry ) == key ) Some( values( entry ) )
    else findEntry( link( entry ) )
  }

  def chainStart( key: K ): Option[Int] = {
    val entry = hash( key )
    if ( !used( entry ) || !chainStart( entry ) ) None
    else Some( entry )
  }

  def remove( key: K ): Option[V] = {
    def isLastChainEntry( entry: Int ): Boolean = {
      if ( entry == NIL )
        throw new IllegalStateException
      val next = link( entry )
      next == NIL || chainStart( next )
    }
    def insertInFsl( entry: Int ) {
      if ( !fsl( entry ) ) {
        fsl( entry ) = true
        link( entry ) = fslStart
        fslStart = entry
      }
      used( entry ) = false
      chainStart( entry ) = true
    }
    def removeChainStart( entry: Int ): Option[V] = {
      def copyLastEntry( entry: Int ): Int = {
        def findLastEntry( pred: Int, entry: Int ): ( Int, Int ) = {
          if ( isLastChainEntry( entry ) ) ( pred, entry )
          else {
            require( fsl( pred ) == fsl( entry ) )
            findLastEntry( entry, link( entry ) )
          }
        }

        val ( pred, last ) = findLastEntry( entry, link( entry ) )
        setEntry( entry, keys( last ), values( last ) )
        if ( !fsl( pred ) ) link( pred ) = NIL
        last
      }

      val oldValue = values( entry )
      val free =
        if ( isLastChainEntry( entry ) ) entry
        else copyLastEntry( entry )
      insertInFsl( free )
      Some( oldValue )
    }
    def findAndRemove( entry: Int ): Option[V] = {
      def findPred( entry: Int ): Option[Int] = {
        val next = link( entry )
        if ( next == NIL || chainStart( next ) ) None
        else if ( keys( next ) == key ) Some( entry )
        else findPred( next )
      }

      val pred = findPred( entry )
      if ( pred == None ) None
      else {
        val prev = pred.get
        val free = link( prev )

        val oldValue = values( free )
        link( prev ) = link( free )
        link( free ) = fslStart
        used( free ) = false
        chainStart( free ) = true
        fsl( free ) = true
        fslStart = free
        Some( oldValue )
      }
    }

    val entry = hash( key )

    val result =
      if ( !used( entry ) || !chainStart( entry ) ) None
      else if ( keys( entry ) == key ) removeChainStart( entry )
      else findAndRemove( entry )

    if ( result != None ) count -= 1
    result
  }

  private[this] def hash( key: K ) = {
    val index = key.hashCode() % floor
    if ( index >= 0 ) index
    else index + floor
  }

  private[this] def getFreeEntry = {
    def nextEntry( entry: Int ): Int = {
      if ( entry == NIL ) NIL
      else if ( used( entry ) ) {
        fsl( entry ) = false
        val next = link( entry )
        if ( chainStart( next ) )
          link( entry ) = NIL
        nextEntry( next )
      } else entry
    }
    val start = fslStart
    if ( fslStart != NIL )
      fslStart = nextEntry( link( fslStart ) )
    start
  }
  private[this] def setEntry( entry: Int, key: K, value: V ) {
    keys( entry ) = key
    values( entry ) = value
  }
  private[this] def setEntryUsed( entry: Int, key: K, value: V ) {
    keys( entry ) = key
    values( entry ) = value
    used( entry ) = true
  }
  private[this] def getPred( entry: Int ): Int = {
    def findNext( temp: Int ): Int =
      if ( link( temp ) == entry ) temp
      else findNext( link( temp ) )

    val start = hash( keys( entry ) )
    if ( start == entry ) NIL
    else findNext( start )
  }

  private[this] def init() {
    for ( i ← 0 until tableSize ) {
      link( i ) = i - 1
      used( i ) = false
      chainStart( i ) = true
      fsl( i ) = true
    }
    fslStart = tableSize - 1
  }

  private[this] val tableSize = floor + cellar
  private[this] var count = 0;
  private[this] val values = new Array[V]( tableSize )
  private[this] val keys = new Array[K]( tableSize )
  private[this] val link = new Array[Int]( tableSize )
  private[this] val used = new Array[Boolean]( tableSize )
  private[this] val chainStart = new Array[Boolean]( tableSize )
  private[this] val fsl = new Array[Boolean]( tableSize )
  private[this] var fslStart: Int = _

  init()
}

object FastHashMap {
  val DEFAULT_FLOOR = 1024
  val NIL = -1
}