开发者社区> 问答> 正文

什么是正确的Java数据结构和搜索算法来搜索一组IP范围以包含在内

如果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

展开
收起
montos 2020-03-27 14:38:22 651 0
1 条回答
写回答
取消 提交回答
  • 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

    2020-03-27 14:40:13
    赞同 展开评论 打赏
问答排行榜
最热
最新

相关电子书

更多
Spring Cloud Alibaba - 重新定义 Java Cloud-Native 立即下载
The Reactive Cloud Native Arch 立即下载
JAVA开发手册1.5.0 立即下载