Suchwert gleich oder zwischen zwei Werten

Question

Ich habe eine CSV-Datei, die eine Region mit einer Postleitzahl verknüpft. Es sieht aus wie diese (niedrigste-zip, höchste-zip, Region):

1600,1799,1 
1800,1899,1 
4300,4699,1 
2820,2839,2 
2850,2879,2 
2930,2949,2 
5600,5819,3 
5850,6514,3 
6516,6549,3 
6800,6849,3 

ich eine Funktion benötigen, die die Region auf der Postleitzahl basiert zurückgibt. Etwas wie folgt aus:

foo = getRegion(1600) // foo is set to 1 
bar = getRegion(1642) // bar is set to 1 
baz = getRegion(4351) // baz is set to 2 
qux = getRegion(1211) // qux is set to null 

So wie ich das derzeit umgesetzt wird, ein HashMap verwenden. Wenn ich die CSV lese, überspringe ich jeden Wert zwischen 1600 und 1799 und erzeuge ein Schlüssel/Wert-Paar für jede Postleitzahl/Region-Kombination und wiederhole das für jede Zeile in der CSV. Das Ergebnis ist ein HashMap wie folgt aussehen:

1600,1 
1601,1 
1602,1 
... 
1799,1 
1800,2 
1801,2 
... 

Dies schafft eine große HashMap, die Arbeit macht. Gibt es eine (speicher) effiziente Implementierung, die diese kleine Tabelle zu einem großen HashMap explodiert?

Answer 1

So etwas wie unten helfen -

class ZipRange { 
    int start; 
    int end; 
} 

// Fill up this map parsing through csv 
Map<ZipRange, Integer> zipToRegion; 

int zipToSearch = 2870; 

// Create method which returns integer which corresponds to region 
for (ZipRange zip : zipToRegion.keySet()) { 
    if (zipToSearch >= zip.start && zipToSearch <= zip.end) { 
     return zipToRegion.get(zip); 
    } 
} 
return -1; 

Answer 2

Ich glaube, Sie wollen ein segment tree