有关hash查找的问题
12-16
在构造网络处理器或者类似的硬件电路时,
经常需要进行查找,
例如一个表中存放了32个48位的MAC地址,
现在过来一个MAC地址,要比较这个MAC地址是不是在表中,
知道可以用CAM,
也可以用HASH,
现在的问题是:
如果用HASH实现,那么,怎么确定这个HASH算法,使得发生冲突的可能性最小,
同时如果发生冲突,该怎么处理?
极端情况:1)良好的算法使得所有MAC地址均不会发生冲突;
2)某个算法使得某个情况下,所有32个MAC地址均冲突。
怎么做?或参考什么资料?
经常需要进行查找,
例如一个表中存放了32个48位的MAC地址,
现在过来一个MAC地址,要比较这个MAC地址是不是在表中,
知道可以用CAM,
也可以用HASH,
现在的问题是:
如果用HASH实现,那么,怎么确定这个HASH算法,使得发生冲突的可能性最小,
同时如果发生冲突,该怎么处理?
极端情况:1)良好的算法使得所有MAC地址均不会发生冲突;
2)某个算法使得某个情况下,所有32个MAC地址均冲突。
怎么做?或参考什么资料?
1. 分析MAC地址的大致分布特征,然后调整HASH函数
2. 发生冲突后一般采用线性链表逐个比较冲突的MAC地址
相关文章:
- 请问到哪里查找software defined radio和cognitive radio的相关(05-08)
- 对老人进行定位,方便查找(05-08)
射频专业培训教程推荐