Chiave racchiusa nell'intervallo intero

Question

Non so se è possibile, ma sto cercando di creare un Hashtable su dove Intervallo è una classe con 2 valori interi/lunghi, un inizio e una fine e volevo fare qualcosa in questo modo:

Hashtable<Interval, WhateverObject> test = new Hashtable<Interval, WhateverObject>(); 
test.put(new Interval(100, 200), new WhateverObject()); 
test.get(new Interval(150, 150)) // returns the new WhateverObject i created above because 150 is betwwen 100 and 200 
test.get(new Interval(250, 250)) // doesn't find the value because there is no key that contains 250 in it's interval 

Quindi, in pratica quello che voglio è che una chiave tra un intervallo di valori in un oggetto di intervallo dare il WhateverObject corrispondente. So che devo sovrascrivere equals() e hashcode() nell'oggetto intervallo, il problema principale che penso è in qualche modo avere tutti i valori tra 100 e 200 (in questo specifico esempio) per dare lo stesso hash.

Eventuali ideologie se questo è possibile?

Grazie

Answer 1

Non è necessario reinventare la ruota, utilizzare NavigableMap.Esempio di codice:

final NavigableMap<Integer, String> map = new TreeMap<Integer, String>(); 
map.put(0, "Cry Baby"); 
map.put(6, "School Time"); 
map.put(16, "Got a car yet?"); 
map.put(21, "Tequila anyone?"); 
map.put(45, "Time to buy a corvette"); 

System.out.println(map.floorEntry(3).getValue()); 
System.out.println(map.floorEntry(10).getValue()); 
System.out.println(map.floorEntry(18).getValue()); 

uscita:

Cry Baby
Scuola Tempo
Hai una macchina ancora?

Answer 2

questo dipende dalla vostra implementazione hashCode. Potresti avere due oggetti con lo stesso valore hashCode.
Si prega di utilizzare Eclipse per generare un metodo hashCode per la classe (nessun punto di re-inventare la ruota

Answer 3

penso che l'attuazione di un get-metodo specializzata sarebbe molto più facile.

Il nuovo metodo può essere parte . di una mappa-wrapper di classe

La chiave-classe: (intervallo è [inferiore, superiore [)

public class Interval { 
    private int upper; 
    private int lower; 

    public Interval(int upper, int lower) { 
     this.upper = upper; 
     this.lower = lower; 
    } 

    public boolean contains(int i) { 
     return i < upper && i >= lower; 
    } 

    @Override 
    public boolean equals(Object obj) { 
     if (obj == null) { 
      return false; 
     } 
     if (getClass() != obj.getClass()) { 
      return false; 
     } 
     final Interval other = (Interval) obj; 
     if (this.upper != other.upper) { 
      return false; 
     } 
     if (this.lower != other.lower) { 
      return false; 
     } 
     return true; 
    } 

    @Override 
    public int hashCode() { 
     int hash = 5; 
     hash = 61 * hash + this.upper; 
     hash = 61 * hash + this.lower; 
     return hash; 
    } 
} 

The map-classe:

public class IntervalMap<T> extends HashMap<Interval, T> { 

    public T get(int key) { 
     for (Interval iv : keySet()) { 
      if (iv.contains(key)) { 
       return super.get(iv); 
      } 
     } 
     return null; 
    } 
} 

Questo è solo un esempio e può certamente essere ottimizzato, e ci sono alcuni difetti così:

Per esempio se Intervalli di sovrapposizione, non c'è GARANZIA sapere quale intervallo viene utilizzato per la ricerca e intervalli non sono garantiti per non sovrapporsi!

Answer 4

È possibile utilizzare uno IntervalTree. Ecco uno che ho fatto prima.

public class IntervalTree<T extends IntervalTree.Interval> { 
    // My intervals. 

    private final List<T> intervals; 
    // My center value. All my intervals contain this center. 
    private final long center; 
    // My interval range. 
    private final long lBound; 
    private final long uBound; 
    // My left tree. All intervals that end below my center. 
    private final IntervalTree<T> left; 
    // My right tree. All intervals that start above my center. 
    private final IntervalTree<T> right; 

    public IntervalTree(List<T> intervals) { 
    if (intervals == null) { 
     throw new NullPointerException(); 
    } 

    // Initially, my root contains all intervals. 
    this.intervals = intervals; 

    // Find my center. 
    center = findCenter(); 

    /* 
    * Builds lefts out of all intervals that end below my center. 
    * Builds rights out of all intervals that start above my center. 
    * What remains contains all the intervals that contain my center. 
    */ 

    // Lefts contains all intervals that end below my center point. 
    final List<T> lefts = new ArrayList<T>(); 
    // Rights contains all intervals that start above my center point. 
    final List<T> rights = new ArrayList<T>(); 

    long uB = Long.MIN_VALUE; 
    long lB = Long.MAX_VALUE; 
    for (T i : intervals) { 
     long start = i.getStart(); 
     long end = i.getEnd(); 
     if (end < center) { 
     lefts.add(i); 
     } else if (start > center) { 
     rights.add(i); 
     } else { 
     // One of mine. 
     lB = Math.min(lB, start); 
     uB = Math.max(uB, end); 
     } 
    } 

    // Remove all those not mine. 
    intervals.removeAll(lefts); 
    intervals.removeAll(rights); 
    uBound = uB; 
    lBound = lB; 

    // Build the subtrees. 
    left = lefts.size() > 0 ? new IntervalTree<T>(lefts) : null; 
    right = rights.size() > 0 ? new IntervalTree<T>(rights) : null; 

    // Build my ascending and descending arrays. 
    /** @todo Build my ascending and descending arrays. */ 
    } 

    /* 
    * Returns a list of all intervals containing the point. 
    */ 
    List<T> query(long point) { 
    // Check my range. 
    if (point >= lBound) { 
     if (point <= uBound) { 
     // In my range but remember, there may also be contributors from left or right. 
     List<T> found = new ArrayList<T>(); 
     // Gather all intersecting ones. 
     // Could be made faster (perhaps) by holding two sorted lists by start and end. 
     for (T i : intervals) { 
      if (i.getStart() <= point && point <= i.getEnd()) { 
      found.add(i); 
      } 
     } 

     // Gather others. 
     if (point < center && left != null) { 
      found.addAll(left.query(point)); 
     } 
     if (point > center && right != null) { 
      found.addAll(right.query(point)); 
     } 

     return found; 
     } else { 
     // To right. 
     return right != null ? right.query(point) : Collections.<T>emptyList(); 
     } 
    } else { 
     // To left. 
     return left != null ? left.query(point) : Collections.<T>emptyList(); 
    } 

    } 

    private long findCenter() { 
    //return average(); 
    return median(); 
    } 

    protected long median() { 
    // Choose the median of all centers. Could choose just ends etc or anything. 
    long[] points = new long[intervals.size()]; 
    int x = 0; 
    for (T i : intervals) { 
     // Take the mid point. 
     points[x++] = (i.getStart() + i.getEnd())/2; 
    } 
    Arrays.sort(points); 
    return points[points.length/2]; 
    } 

    /* 
    * What an interval looks like. 
    */ 
    public interface Interval { 

    public long getStart(); 

    public long getEnd(); 
    } 

    /* 
    * A simple implemementation of an interval. 
    */ 
    public static class SimpleInterval implements Interval { 

    private final long start; 
    private final long end; 

    public SimpleInterval(long start, long end) { 
     this.start = start; 
     this.end = end; 
    } 

    public long getStart() { 
     return start; 
    } 

    public long getEnd() { 
     return end; 
    } 

    @Override 
    public String toString() { 
     return "{" + start + "," + end + "}"; 
    } 
    } 

} 

Answer 5

Un HashTable ingenuo è la soluzione sbagliata qui. Sovrascrivere il metodo equals() non ti fa nulla di buono perché la HashTable confronta prima una chiave con il codice hash, NON il metodo equals(). Il metodo equals() viene controllato solo dopo che il codice hash è stato abbinato.

È facile creare una funzione di hash sull'oggetto intervallo, ma è molto più difficile crearne uno che restituisca lo stesso codice hash per tutti gli intervalli possibili compresi in un altro intervallo. Sovrascrivere il metodo get() (come ad esempio https://stackoverflow.com/a/11189075/1261844) per un HashTable nega completamente i vantaggi di un HashTable, che è molto veloce i tempi di ricerca. Nel punto in cui si sta eseguendo la scansione di ciascun membro di una HashTable, si sa che si sta utilizzando l'HashTable in modo errato.

Direi che Using java map for range searches e https://stackoverflow.com/a/11189080/1261844 sono soluzioni migliori, ma un HashTable non è semplicemente la strada da percorrere per questo.

Answer 6

Affinché Hastable o HashMap funzionino come previsto, non è solo un codice hash uguale, ma anche il metodo equals deve restituire true. Quello che stai richiedendo è quell'intervallo (x, y) .equals (Intervallo (m, n)) per m, n all'interno di x, y. Poiché questo deve essere vero per qualsiasi istanza di Intervallo vivente sovrapposta, la classe deve registrarli tutti e deve implementare ciò che stai cercando di ottenere, anzi.

Quindi in breve la risposta è no.

La biblioteca guava Google sta progettando di offrire un RangeSet e mappa: guava RangeSet

Per piccoli intervalli ragionevoli un approccio semplice sarebbe quella di specializzarsi HashMap mettendo e ottenere i valori più appropriate degli intervalli.

Answer 7

La soluzione di OldCurmudgeon funziona perfettamente per me, ma è molto lenta da inizializzare (sono stati necessari 20 minuti per 70k voci). Se si conosce la vostra lista in entrata degli articoli è già ordinato (ascendente) e ha solo non si sovrappongono gli intervalli, si può fare inizializzare in millisecondi aggiungendo e utilizzando il seguente costruttore:

public IntervalTree(List<T> intervals, boolean constructorFlagToIndicateOrderedNonOverlappingIntervals) { 
    if (intervals == null) throw new NullPointerException(); 

    int centerPoint = intervals.size()/2; 
    T centerInterval = intervals.get(centerPoint); 
    this.intervals = new ArrayList<T>(); 
    this.intervals.add(centerInterval); 
    this.uBound = centerInterval.getEnd(); 
    this.lBound = centerInterval.getStart(); 
    this.center = (this.uBound + this.lBound)/2; 
    List<T> toTheLeft = centerPoint < 1 ? Collections.<T>emptyList() : intervals.subList(0, centerPoint); 
    this.left = toTheLeft.isEmpty() ? null : new IntervalTree<T>(toTheLeft, true); 
    List<T> toTheRight = centerPoint >= intervals.size() ? Collections.<T>emptyList() : intervals.subList(centerPoint+1, intervals.size()); 
    this.right = toTheRight.isEmpty() ? null : new IntervalTree<T>(toTheRight, true); 
}