如果IP地址在范围内,则给出以下列表。
LOW HIGH
192.168.10.34 192.168.11.200
200.50.1.1 200.50.2.2
假设迭代所有范围内的所有地址并将它们存储在HashSet中将使用过多的内存。
因此,我们需要保持范围,实际上这些范围实际上只是移位的数字(低和高)。如何将范围存储在树中,然后使用有效的搜索来查找特定地址是否在范围内。
我看过RangeTree,但它似乎是在笛卡尔平面上搜索点,似乎不适合我的用例。KDTree允许人们搜索最近的邻居,并且当k == 2时,它与范围树基本相同。
我想要所有匹配项,因为可能有多个匹配项。
什么会在这里工作?我非常确定这是一个已解决的问题。
问题来源:Stack Overflow
TreeMap假设您没有重叠范围,则可以使用标准。
只需创建一个TreeMap,以范围的下限为键,并以整个范围作为值。使用查找范围,floorEntry(K key)并验证该值是否在范围内。
使用简单Integer而不是IpAddress对象的示例,但是任何Comparable对象都可以用作范围边界。
public final class RangeMap<T extends Comparable<T>> {
private TreeMap<T, Range<T>> map = new TreeMap<>();
public void add(Range<T> range) {
Entry<T, Range<T>> entry = this.map.floorEntry(range.getUpperInclusive());
if (entry != null && entry.getValue().overlaps(range))
throw new IllegalArgumentException("Overlap: " + range + " vs " + entry.getValue());
entry = this.map.ceilingEntry(range.getLowerInclusive());
if (entry != null && entry.getValue().overlaps(range))
throw new IllegalArgumentException("Overlap: " + range + " vs " + entry.getValue());
this.map.put(range.getLowerInclusive(), range);
}
public boolean contains(T value) {
Entry<T, Range<T>> entry = this.map.floorEntry(value);
return (entry != null && entry.getValue().contains(value));
}
public Range<T> get(T value) {
Entry<T, Range<T>> entry = this.map.floorEntry(value);
return (entry != null && entry.getValue().contains(value) ? entry.getValue() : null);
}
}
public final class Range<T extends Comparable<T>> {
private final T lowerInclusive;
private final T upperInclusive;
public Range(T lowerInclusive, T upperInclusive) {
this.lowerInclusive = lowerInclusive;
this.upperInclusive = upperInclusive;
}
public T getLowerInclusive() {
return this.lowerInclusive;
}
public T getUpperInclusive() {
return this.upperInclusive;
}
public boolean contains(T value) {
return (value.compareTo(this.lowerInclusive) >= 0 &&
value.compareTo(this.upperInclusive) <= 0);
}
public boolean overlaps(Range<T> that) {
return (this.lowerInclusive.compareTo(that.upperInclusive) <= 0 &&
this.upperInclusive.compareTo(that.lowerInclusive) >= 0);
}
@Override
public String toString() {
return "(" + this.lowerInclusive + "-" + this.upperInclusive + ")";
}
}
测试
RangeMap<Integer> map = new RangeMap<>();
map.add(new Range<>(50, 59));
map.add(new Range<>(70, 79));
for (int i = 40; i <= 90; i += 3)
System.out.println(i + ": " + map.contains(i));
输出量
40: false
43: false
46: false
49: false
52: true
55: true
58: true
61: false
64: false
67: false
70: true
73: true
76: true
79: true
82: false
85: false
88: false
回答来源:Stack Overflow
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。