在Golang中检查IP地址片段的有效方法 [英] Efficient way to check IP in slice of IP addresses in Golang

问题描述

我正在Golang开发一个网络应用程序。我有一部分IP地址。每次发出请求时，我都使用 net.LookupIP（host）来找出主机的IP地址，该主机返回一个 net.IP 。什么是最好的方法来比较这些？

顺便说一下在Python中，我们有一个 set 数据结构，它使上面的问题很容易解决，但是Go怎么样？

解决方案

使用set

构建我们的集合

Go中没有内置的 Set 类型，但您可以优雅地使用 map [Type] bool 作为一个集合，例如：

  //创建一个包含2个值的集合：[1，2] 
m：= map [int] bool {1：true，2：true} 
 
 //测试一个元素：
 fmt.Println（m [1]）// true 
 fmt.Println（m [3]）// false 
 
 // Set一个元素：
m [3] = true 
 fmt.Println（m [3]）// true 
 
 //删除元素：
 delete（m， 1）
 fmt.Println（m [1]）// false 
  

注意：我们利用了这样一个事实，即如果一个关键字不在地图中，索引地图将导致零值，如果 bool ，则值类型为 false code>，正确地告诉元素不在映射（set）中。

在 Go Playground 。

^{注＃2 ：有一些技巧可以使代码处理地图的时间更短，您可以在此答案中检查它们：检查是否值在列表中。}

使用 net.IP / h3>

现在我们只需要一种代表 net.IP ，它可以用作映射中的键类型（请参阅以下有关构成映射键类型的问题：如何预防nt一种用作映射键的类型？）。

不幸的是， net.IP 本身会没有资格，因为它是一个片段：

  type IP [] byte 
  

切片不具有可比性。有关详细信息，请参阅以下问题：将密钥散列为数组类型和这：为什么有数组在Go？

一个简单的方法是将它转换为规范的 string 值，我们就完成了。为此，我们可以简单地将IP的字节转换为十六进制 string 。但是IPv4地址可能会以IPv6的形式出现，因此我们应该先将其转换为IPv6： $ b

  func Key（ip net.IP）string {
 return hex.EncodeToString（ip.To16（））
} 
  

注意：IP地址的字节可能不是有效的UTF-8编码字符串（这就是Go如何存储 string 在内存中），但是在中的 string 值代表任意字节序列，所以下面的内容也可以工作，简单得多，而且更重要高效：

func Key（ip net.IP）string {
return string（ ip.To16（））//简单[]字节=>字符串转换
}


我们可以使用这样的IP字符串作为键。使用IP填充您的地图以检查：

  //填充禁止的IP：
 forbIPs：= map [string] bool {
 Key（ip1）：true，
 Key（ip2）：true，
} 
 
 //现在检查单个IP：
 ipToCheck：= ... 
 if forbIPs [Key（ipToCheck）] {
 fmt.Println（Forbidden！）
} else {
 fmt .Println（Allowed。）
} 
  

如果您有多个IP需要检查如 net.LookupIP（） ），它是循环中的单个：



  ips，err：= net.LookupIP（host）
 //检查err 
是否为_，ip：= range ips {
如果是forbIPs [Key（ip）] {
 //禁止！ 
 
 
 $ / code $ / pre 
 $ b $ h3替代钥匙类型
 
 
请注意，如上所述，切片不具有可比性，但数组是。所以我们也可以使用一个数组作为关键。这就是它的样子：
  func Key（ip net.IP）（a [ 16]字节）{
 copy（a [：]，ip）
 return 
} 
 
 // IP地址：
 forbIPs：= map [[16] byte] bool {
 // ... 
} 
  
 
 
 < h2>替代方案

Sorted slice

另外，我们可以简单地将禁止的IP存储在一个slice [] net.IP ，并保持排序。如果它被排序，我们可以使用二分查找找到它的IP（标准库 sort.Search（） ）。

是，二进制搜索有 O（log2与上面的（散列）地图解决方案的 O（1）复杂性相比，复杂度更高。但是这个选择有另一个亲：



枚举单个IP并不总是实用的。有时（通常）列出IP范围会更容易。第一个解决方案对于处理IP范围是不可行的，但是这个解决方案可能是：您可以在 O（log2（n））时间内找到覆盖IP地址的范围。


I'm developing a network application in Golang. I have a slice of IP addresses. Each time a request comes I use net.LookupIP(host) to find out IP address of host which returns a slice of net.IP. What is the best approach to compare these?

By the way in Python we have a set data structure which makes above question so easy to resolve but what about Go?

解决方案

With a "set"

Building our set

There is no builtin Set type in Go, but you can elegantly use a map[Type]bool as a set, e.g.:

// Create a set with 2 values in it: [1, 2]
m := map[int]bool{1: true, 2: true}

// Test an element:
fmt.Println(m[1]) // true
fmt.Println(m[3]) // false

// Set an element:
m[3] = true
fmt.Println(m[3]) // true

// Delete an element:
delete(m, 1)
fmt.Println(m[1]) // false

Note: we exploited the fact that if a key is not in the map, indexing the map results in the zero value for the value type, which is false in case of bool, properly telling that the element is not in the map (set).

Try it on the Go Playground.

^{Note #2: there are a few tricks to make the code to handle a map as a set shorter, you can check them in this answer: Check if a value is in a list.}

Using net.IP in the set

Now we only need a type representing a net.IP which can be used as the key type in a map (see this question about what constitutes a map key type: How can I prevent a type being used as a map key?).

Unfortunately net.IP itself does not qualify, because it is a slice:

type IP []byte

And slices are not comparable. See this question for details: Hash with key as an array type and this: Why have arrays in Go?

An easy way is to convert it to a canonical string value and we're done. For this we may simply convert the bytes of the IP to a hex string. But an IPv4 address may be presented as IPv6, so we should first convert it to IPv6:

func Key(ip net.IP) string {
    return hex.EncodeToString(ip.To16())
}

Note: bytes of an IP address may not be a valid UTF-8 encoded string (which is how Go stores strings in memory), but string values in Go represent arbitrary byte sequences, so the following also works, is much simpler and is much more efficient:

func Key(ip net.IP) string {
    return string(ip.To16())  // Simple []byte => string conversion
}

We can use such IP strings as the keys. Populate your map with IPs to check against:

// Populate forbidden IPs:
forbIPs := map[string]bool{
    Key(ip1): true,
    Key(ip2): true,
}

// Now check a single IP:
ipToCheck := ...
if forbIPs[Key(ipToCheck)] {
    fmt.Println("Forbidden!")
} else {
    fmt.Println("Allowed.")
}

If you have multiple IPs to check (as returned by net.LookupIP()), it's a single for loop:

ips, err := net.LookupIP(host)
// Check err
for _, ip := range ips {
    if forbIPs[Key(ip)] {
        // FORBIDDEN!
    }
}

Alternative Key type

Note that –as mentioned above– slices are not comparable but arrays are. So we could also use an array as the key. This is how it could look like:

func Key(ip net.IP) (a [16]byte) {
    copy(a[:], ip)
    return
}

// And the IP set:
forbIPs := map[[16]byte]bool{
    // ...
}

Alternatives

Sorted slice

Alternatively we could just simply store the forbidden IPs in a slice []net.IP, and keep it sorted. If it is sorted, we can use binary search to find an IP in it (standard library sort.Search()).

Yes, binary search has O(log2(n)) complexity compared to the O(1) complexity of the (hash)map solution above. But this alternative has another pro:

Enumerating individual IPs is not always practical. Sometimes (often) it is easier to list IP ranges. The first solution is not feasible to handle IP ranges, but this solution may be: you can find ranges that cover an IP address also in O(log2(n)) time.

这篇关于在Golang中检查IP地址片段的有效方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！