用于四路散列表的方法和装置

摘要

多个散列表被计算所得的每个散列表的不同索引同时访问。每个索引识别散列表之一的存储散列项的位置。为了搜索发送项，由在搜索关键字上产生的散列函数计算的索引所识别的位置被搜索，以匹配搜索关键字。如果不要求单一周期内插入，并且由在插入关键字上产生散列函数计算的索引识别的所有位置都已被占用，为了插入发送项，数据库则被重新排序，以便发送项能够插入由计算所得插入关键字的索引之一识别的位置。如果要求单一周期内插入，并且由计算的索引识别所有位置都已被占用，则由计算而得的插入关键字的索引之一识别的位置之一，可被发送项随机地重写。

主权项

1.一种网络开关，包括：多个同样大小的散列表，每个散列表包括多个位置，每个位置能存储可被索引访问的发送项；散列函数逻辑执行装置，根据依赖于目的地址的关键字，利用每个散列表对应的散列函数同时地为每个散列表计算独立的索引，关键字的数目大于多个散列表中的位置的总数，与关键字有关的发送项被存储在多个被索引的位置之一，被索引的位置由其它关键字共享，致使对发送项的搜索在一个搜索周期中被完成；发送项插入逻辑执行装置，当检索到由第一关键字计算的索引识别的散列表中的所有位置都被占用，其中有一个或多个位置被具有第二关键字的发送项占用，将具有第二关键字的发送项之一移动到可用于第二关键字的其它可用位置。