基于均衡学习的增强哈希桶模型研究

Research on balanced learning-based enhanced hash bucket model

在使用哈希查找表构造IEEE 802.1Q协议中VLAN(虚拟局域网)网桥定义的过滤数据库时,哈希桶常被用于解决多个关键字对应同一个存储地址而造成的"哈希冲突"。传统哈希桶通过唯一的哈希地址获取整个学习表的资源,效率较低。文章提出了一种改进哈希表冲突的优化方法,通过双哈希桶和溢出桶来构造哈希表,并采用均衡学习的方式进行地址学习操作。该方法在双哈希桶溢出的情况下,将溢出条目暂存到溢出桶,并通知软件完成双哈希桶中冲突条目的释放和溢出桶中溢出条目的搬移操作。仿真实验结果表明,新的哈希算法可以有效减少哈希冲突的发生率,提高哈希表存储空间的利用率。

When the hash lookup table is used to construct the filtering database defined by the VLAN-aware bridges in IEEE 802.1Q protocol,the hash bucket is usually used to resolve the hash collisions caused by multiple keywords corresponding to the same storage address.The traditional hash bucket is low in efficiency as it acquires the resources of the entire learning table with only one hash address.This article presents an optimization method to improve collisions of the hash table,i.e.construc-ting the hash table by dual hash buckets and an overflow bucket and performs address learning in a balanced learning approach. When the dual bucket overflow occurs,it stores the overflow-entry in the overflow bucket temporarily and notifies the CPU to release the location of collision-entry and move the overflow-entry.The simulation results show that this new algorithm mini-mizes the hash collisions effectively,and improves the utilization rate of the storage space of the hash table.