与爱共舞面试：问了个1000w IP池，精确的，网段和通配符三种，传入一个IP，全部返回匹配上的三种?

## 一、精确匹配（HashSet） ### **思路说明：** - **数据结构选择：** 使用`HashSet<String>`存储所有精确IP。 - **匹配原理：** 传入的IP直接调用`Set.contains()`判断是否存在于集合中。 - **效率分析：** - 时间复杂度：O(1)（理想情况下） - 非常适合大规模精确IP查询。 ### **实现细节：** ```java Set<String> exactIPs = new HashSet<>(); exactIPs.add("192.168.1.1"); // 匹配时直接调用 if(exactIPs.contains("192.168.1.1")){ // 匹配成功 } ``` ## 二、CIDR网段匹配（位掩码方式） ### **什么是CIDR？** - CIDR形式如：`192.168.0.0/24` - 表示网段，其中`/24`为子网掩码长度，表示前24位固定，后8位可变。 ### **匹配原理：** - 将CIDR表示法的网络地址和目标IP分别转化成整数（二进制表示）。 - 利用子网掩码长度计算出网络地址的整数表示。 - 通过**位运算**判断IP是否在网段内： ```pseudo 网络地址整数 = 网络IP >> (32 - 子网掩码长度) 目标地址整数 = 目标IP >> (32 - 子网掩码长度) 如果两个结果相同，则目标IP属于网段 ``` ### **举个详细例子：** 例如判断IP：`192.168.1.50` 是否属于 `192.168.1.0/24` 1. 转成二进制： ``` 192.168.1.0 -> 11000000 10101000 00000001 00000000 192.168.1.50 -> 11000000 10101000 00000001 00110010 ``` 2. 网段`/24`，前24位固定，即比较前24位： ``` 11000000 10101000 00000001 | 00000000 11000000 10101000 00000001 | 00110010 ↑ 从此处分隔，前24位完全相同 ``` 3. 因此属于此网段。 ### **实现细节：** 核心实现代码： ```java boolean matches(InetAddress address) { byte[] networkBytes = network.getAddress(); byte[] ipBytes = address.getAddress(); int shift = 32 - mask; int networkInt = bytesToInt(networkBytes); int ipInt = bytesToInt(ipBytes); return (networkInt >> shift) == (ipInt >> shift); } private int bytesToInt(byte[] bytes) { int val = 0; for (byte b : bytes) { val = (val << 8) | (b & 0xFF); } return val; } ``` - 利用Java的位操作快速判断，提高效率。 - 转换IP为int后高效计算。 ## 三、通配符匹配（分段简单匹配） ### **什么是通配符匹配？** - 通配符形式如：`192.168.*.*`，`*`表示任意值（0-255）。 ### **匹配原理：** - 将IP和通配符地址按`.`进行分割成数组。 - 逐个比较每段： - 若通配符是`*`，该段直接匹配成功。 - 若通配符为数字，则与对应IP段进行精确比较。 ### **举个例子：** 判断 `192.168.5.100` 是否匹配通配符 `192.168.*.*`： - 拆分： ``` IP: 192 | 168 | 5 | 100 通配符: 192 | 168 | * | * ``` - 比较逐段： - `192 == 192` ✔️ - `168 == 168` ✔️ - `5 vs *` ✔️ (匹配) - `100 vs *` ✔️ (匹配) - 全部匹配成功，返回true。 ### **实现细节：** 核心代码： ```java private boolean wildcardMatch(String ip, String wildcard) { String[] ipParts = ip.split("\\."); String[] wildcardParts = wildcard.split("\\."); for (int i = 0; i < 4; i++) { if (!wildcardParts[i].equals("*") && !wildcardParts[i].equals(ipParts[i])) { return false; } } return true; } ``` - 简单的字符串分割和逐段对比，代码易懂。 - 时间复杂度：O(1)（固定4段），效率高。 ## 总结对比： | 匹配方式 | 数据结构 | 匹配原理 | 性能优势 | |------------|-------------|------------------------|-----------------------| | 精确匹配 | HashSet | O(1)哈希查找 | 极高效，适合大量精确IP | | CIDR匹配 | 位运算掩码 | 二进制位对比 | 高效，适合大量CIDR网段 | | 通配符匹配 | 字符串拆分 | 按`.`拆分逐段对比 | 简单高效，适合常见通配符|

你可以参考以下实现方式： ```java import java.net.InetAddress; import java.net.UnknownHostException; import java.util.*; public class IPMatcher { private final Set<String> exactIPs = new HashSet<>(); private final List<Subnet> cidrList = new ArrayList<>(); private final List<String> wildcardList = new ArrayList<>(); public void addExactIP(String ip) { exactIPs.add(ip); } public void addCIDR(String cidr) throws UnknownHostException { cidrList.add(new Subnet(cidr)); } public void addWildcard(String wildcard) { wildcardList.add(wildcard); } public List<String> match(String ip) throws UnknownHostException { List<String> matches = new ArrayList<>(); // 精确匹配 if (exactIPs.contains(ip)) { matches.add("Exact: " + ip); } // CIDR匹配 InetAddress address = InetAddress.getByName(ip); for (Subnet subnet : cidrList) { if (subnet.matches(address)) { matches.add("CIDR: " + subnet.cidr); } } // 通配符匹配 for (String wildcard : wildcardList) { if (wildcardMatch(ip, wildcard)) { matches.add("Wildcard: " + wildcard); } } return matches; } private boolean wildcardMatch(String ip, String wildcard) { String[] ipParts = ip.split("\\."); String[] wildcardParts = wildcard.split("\\."); for (int i = 0; i < 4; i++) { if (!wildcardParts[i].equals("*") && !wildcardParts[i].equals(ipParts[i])) { return false; } } return true; } // 内部类表示网段 static class Subnet { private final String cidr; private final InetAddress network; private final int mask; Subnet(String cidr) throws UnknownHostException { this.cidr = cidr; String[] parts = cidr.split("/"); this.network = InetAddress.getByName(parts[0]); this.mask = Integer.parseInt(parts[1]); } boolean matches(InetAddress address) { byte[] networkBytes = network.getAddress(); byte[] ipBytes = address.getAddress(); int shift = 32 - mask; int networkInt = bytesToInt(networkBytes); int ipInt = bytesToInt(ipBytes); return (networkInt >> shift) == (ipInt >> shift); } private int bytesToInt(byte[] bytes) { int val = 0; for (byte b : bytes) { val = (val << 8) | (b & 0xFF); } return val; } } // 测试示例 public static void main(String[] args) throws Exception { IPMatcher matcher = new IPMatcher(); // 添加数据 matcher.addExactIP("192.168.1.1"); matcher.addCIDR("10.0.0.0/8"); matcher.addWildcard("172.16.*.*"); // 测试匹配 String testIP = "172.16.5.10"; List<String> matches = matcher.match(testIP); System.out.println("匹配结果："); matches.forEach(System.out::println); } } ``` 上面代码提供了三种IP匹配方式的完整实现，并且包含了使用示例： - **精确匹配**：使用`HashSet`快速判断； - **CIDR网段匹配**：使用二进制掩码计算； - **通配符匹配**：简单分割匹配。