路由
路由入网报文转发到目的网络
路由查找
路由表里会指定目的网段和子网掩码长度(route_prefix/prefix_length)
二进制查找
目的IP与子网掩码做与运算，然后比较和路由前缀是否相等
dip & mask ?= route_prefix
哈希查找
针对IPv4,地址长度32bit
建立32个hash桶，key = hash(route_prefix),存入prefix_length为索引的桶里
|子网掩码长度32|-->|hash(route_prefix1/32)|...|
|子网掩码长度31|-->|hash(route_prefix3/32)|...|
|子网掩码长度30|-->|hash(route_prefix5/32)|...|
|子网掩码长度..|-->|...|
|子网掩码长度2 |-->|hash(route_prefix7/32)|...|
|子网掩码长度1 |-->|hash(route_prefix9/32)|...|
搜寻时，目的IP依次与长度从32减小到1的掩码做运算，然后hash，去对应桶查找
256叉树
前缀树查找
路径压缩
在前缀树查找中，从下往下，每个节点都要比较依次，