在Golang中检查IP地址片中IP的有效方法 [英] Efficient way to check IP in slice of IP addresses in Golang
问题描述
我正在用 Golang 开发一个网络应用程序.我有一部分 IP 地址.每次收到请求时，我都会使用 net.LookupIP(host) 来找出返回 net.IP 片段的主机 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?
顺便说一句，在 Python 中，我们有一个 set 数据结构，这使得上述问题很容易解决，但是 Go 呢?
By the way in Python we have a set data structure which makes above question so easy to resolve but what about Go?
推荐答案
带set"
构建我们的集合
Go 中没有内置 Set 类型，但您可以优雅地使用 map[Type]bool 作为集合，例如:
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
注意:我们利用了这样一个事实，即如果键不在映射中，索引映射会导致 零值 为值类型，在 bool 的情况下为 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).
在 Go Playground 上尝试一下.
注意#2:有一些技巧可以使将地图作为一组处理的代码更短，您可以在以下答案中检查它们:检查一个值是否在列表中.
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.
现在我们只需要一个类型来表示 net.IP 可用作映射中的键类型(有关什么构成映射键类型，请参阅此问题:如何防止类型被用作映射键?).
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?).
不幸的是，net.IP 本身不符合条件，因为它是一个切片:
Unfortunately net.IP itself does not qualify, because it is a slice:
type IP []byte
而且切片没有可比性.有关详细信息，请参阅此问题:Hash with key as an array type 和这个:为什么在 Go 中有数组?
And slices are not comparable. See this question for details: Hash with key as an array type and this: Why have arrays in Go?
一种简单的方法是将其转换为规范的 string 值，我们就完成了.为此，我们可以简单地将 IP 的字节转换为十六进制 string.但是一个 IPv4 地址可能会显示为 IPv6，所以我们应该先将其转换为 IPv6:
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())
}
注意:IP 地址的字节可能不是有效的 UTF-8 编码 string(这是 Go 在内存中存储 string 的方式)，但是 Go 中的字符串 值表示任意字节序列，因此以下方法也有效，更简单且更高效:
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
}
我们可以使用这样的 IP 字符串作为键.使用 IP 填充您的地图以进行检查:
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.")
}
如果您有多个 IP 要检查(由 net.LookupIP() 返回/code>)，这是一个单一的 for 循环:
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{
// ...
}
替代方案
排序切片
或者，我们可以简单地将禁止的 IP 存储在切片 []net.IP 中，并保持排序.如果是排序的，我们可以用二分查找在里面找一个IP(标准库sort.Search()).
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()).
是的，与上述 (hash)map 解决方案的 O(1) 复杂度相比，二分查找的复杂度为 O(log2(n)).但这种替代方案还有另一个优点:
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:
枚举单个 IP 并不总是可行的.有时(通常)列出 IP 范围更容易.第一种解决方案对于处理 IP 范围是不可行的，但这种解决方案可能是:您可以在 O(log2(n)) 时间内找到覆盖 IP 地址的范围.
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地址片中IP的有效方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
