● 摘要
HASH，一般翻译做“散列”，也有直接音译为"哈希"的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。 数学表述为：h = H(M) ，其中H( )--单向散列函数，M--任意长度明文，H--固定长度散列值。HASH算法是一种多对一的散列映射函数关系。HASH表主要是使用特定的HASH函数将某一关键字的内容存入特定的地址内的一种存储方式。HASH算法是目前在精确匹配查找领域中应用最为广泛的一种算法，其具有查找速度快、存储容量大等特点。在各类精确匹配查找算法中，HASH有着很广泛的应用。本文将主要针对HASH算法的基本原理、HASH算法在路由表算法查找领域的实际应用与逻辑FPGA实现，以及HASH算法的优化算法进行深入的研究和探讨。主要涉及基本HASH算法原理介绍及常用HASH算法函数，然后介绍本课题主要研究的创新HASH算法——RC HASH、two left HASH算法原理及FPGA详细实现方案，最后介绍RC HASH、two left HASH查找算法在路由器上的应用以及实验测试数据对比。另外，本文中所涉及的设计方案还针对于如何降低HASH算法的冲突概率、解决存储空间浪费和访问带宽不足、提高精确匹配查找速率等问题进行了深入的研究和探讨，并通过实验证明了设计方案的合理性和可行性。