Heiner Kücker

Range-Map

Home

Java-Seite

   ASM Improved

   heterogene
   Map, HMap

   Constraint
   Code Generator

   JSP WorkFlow
   PageFlow FlowControl
   Page Flow Engine
   Web Flow Engine
   Control_and_Command

   JSP_Spreadsheet

   Code-Generator
   für Option-Either-Stil
   in Java

   verbesserter
   Comparator

   Fluent-Interface
   Code-Generator
   auf Basis
   einer Grammatik

   Visitor mit Multidispatch

   for-Schleife mit
   yield-return

   Kognitions-Maschine
   semantisches Netz

   Domain Parser

   Codegenerator_für
   hierarchische
   Datenstrukturen

   Expression_Engine
   Formula_Parser

   Thread Preprocessor

   State Transition Engine

   AspectJ

   Java_Explorer

   DBF_Library

   Kalender_Applet

   SetGetGen

   BeanSetGet

   CheckPackage

   LineNumbers

   GradDms

   Excel-Export

   StringTokenizer

   JspDoc

   JspCheck

   JSP-Schulung
   Java Server Pages
   Struts

   Ascii-Tabellen-
   Layouter

   Ascii-Baum-
   Layouter

   Ascii-Art-Fluss-
   Diagramm-
   Parser

   AsciiArt
   AssignmentMatrix
   Layouter

   StringSerial

   Silbentrennung

   JDBC_Schlüssel-
   Generierung

   bidirektional/
   unidirektional
   gelinkte Liste

   Java_Sitemap
   Generator

   XmlBuilder

   RangeMap

   StringFormatter

   VersionSafe
   XCopy

   JTextField

   CommandLine-
   ParamReader

   Bitmap-Grafik

   MultiMarkable-
   Buffered-
   InputStream

   JavaCache

   JdomUtil

   CollectionUtil

   XML Really
   Pull Parser

   Log-Filter

   Remote-Protokoll

   Sudoku-Generator

   Delegation statt
   Mehrfachvererbung

   Disjunct
   Interval Set

   WebCam_Demo

   Weiterentwicklung_Java

Alaska-XBase++-Seite

Projekte

Philosophien
Techniken


Konzepte

Sudoku

Kontakt /
Impressum


Links

SiteMap





Letzte Aktualisierung:
20.08.2005

Range-Map

Die RangeMap ist eine performanceoptimierte Datenstruktur zum Zuordnen eines Wertes zu einem Band/Bereich von Werten (Nummernband).
Dazu wird eine JDK-TreeMap (java.util.TreeMap) durch spezielle Comparatoren und spezielle put und get-Methoden dekoriert, so dass beim Einfügen put eine Range (Wert von bis) und beim Abfragen get ein Point (konkreter Wert) benutzt wird.

Die JDK-TreeMap sorgt für das Ausbalancieren des Baumes beim Einfügen und für das performante Suchen beim Abfragen der Range-Map.

Gegeben sei folgendes Problem:

Es gibt konkrete Nummern (Gerätenummer) die jeweils zu einem Nummernband (Nummernbereich von bis) gehören.

Es werden clusterweise wechselnd Geräte hergestellt, die jeweils ein zusammengehörendes Band von laufenden Nummern bekommen.

An die Applikation werden demzufolge wechselnd Anfragen zu bestimmten konkreten Nummern gestellt, für die ermittelt werden muss, zu welchem Bereich sie gehören.

Die Nummernbänder überlappen sich nicht.

Es sollte nicht vorkommen, dass kein Treffer gefunden wird.

Es ergibt sich folgende Datenstruktur in der Datenbank:

ITEM_FROM NUMBER
ITEM_TO NUMBER
ITEM_TYP NUMBER

Ich will also anhand der Geräte-Nummer die Artikel-Nummer (Geräte-Typ) herausbekommen.

Das alles soll ziemlich performant sein.

Von der Datenbank hole ich den passenden Datensatz per

    SELECT ... WHERE ITEM_FROM <= ? AND ITEM_TO >= ?

Ein WHERE IN ... hilft mir hier nicht.

Ich weiss nicht, ob mir hier ein Index auf der DB hilft. Beim Clipper gab es einen

    SET SOFTSEEK ON - Schalter
der steuerte, dass beim Index-Lookup der nächst passende Treffer ermittelt wurde.

Zwischen der Businesslogik und der DB-Schicht liegt natürlich ein Cache.

Normalerweise arbeitet ein Cache mit einer Key-Value-Kombination, also HashMap.

Das klappt in diesem Fall nicht, da das Prinzip des Hashes auf einer möglichst weiten Spreizung konkreter Werte im Wertebereich beruht.

Also brauche ich eine RangeMap.

Also ich habe eine Struktur mit einem Key von bis und einem Value in.
Wie schon gesagt, HashMap hilft hier nicht.

Ich dachte mir nun, nehme ich eine TreeMap. Die Suche erfolgt binär und nicht linear (was ziemlich langsam wäre).

Der Baum wird von der JDK-Klasse balanciert, Klasse.

Nur muss ich die Methoden compareTo und equals so ummodeln, dass beim Einfügen in die Map (put) nach der Range sortiert wird.

Beim get muss aber nach Range und Wert verglichen werden.

Nun wollte ich aber die JDK-Klasse nicht aufdröseln oder neu implementieren.

Deshalb gibt es eine abstrakte Hilfs-Klasse RangeOrPoint, die entweder eine Range (Bereich) oder ein Point (konkreter Wert) sein kann und in compareTo und equals per instanceof entscheidet, wie der Vergleich ausgeht:

equals liefert true, wenn Key in Range.

compareTo liefert

0, wenn Key in Range.
-1, wenn Key kleiner als Range from.
1, wenn Key grösser als Range to.

Im herunterladbaren Zip-File RangeMap.zip findet sich eine Implementation oben beschriebener Lösung.

Aufgrund des Feedbacks von der News-Group de.comp.lang.java habe ich die Implementierung so geändert, dass die Unterscheidung um welche konkrete Klasse, Range oder Point, es sich handelt, nicht über instanceof ermittelt wird, sondern jeweils unterschiedliche compareTo-Methoden in den jeweiligen Klassen implementiert sind.

Noch zu tun: Lösung zum Verhindern überlappender Ranges
Eine solche Lösung wird nach meiner Einschätzung aber auch die Performance negativ beeinflussen. Alternativ bleibt die Möglichkeit zur Absicherung gegen überlappende Ranges durch die umgebende Applikation oder durch fachliche Massnahmen wie die Validierung entsprechender Eingaben.


Siehe hierzu auch den Thread auf der News-Group de.comp.lang.java zu diesem Thema.

Download der Quelldateien RangeMap.zip

Achtung: Erweiterungen und Fixes stelle ich ohne Historie und ohne Ankündigung hier bereit.
Deshalb am besten immer die letzte Version runterladen.

Lizenzbedingungen:

Die Programme, Quelltexte und Dokumentationen können ohne irgendwelche Bedingungen kostenlos verwendet werden.
Sie sind Freeware und Open Source. Für Fehler und Folgen wird keinerlei Haftung übernommen.

Hinweise zur Fehlerbeseitigung und Verbesserung sind mir willkommen.

Ich freue mich auch über Feedback bezüglich der erfolgreichen Verwendung meiner Sourcen.

Bei Fragen helfe ich gern mit Hinweisen oder zusätzlicher Dokumentation, falls ich dafür Zeit habe.