Abstract-Hash tabeller är en grundläggande datastruktur i många nätverksapplikationer, inklusive ruttlookups, paketklassificering och övervakning. Ofta en del av databanan, de behöver för att fungera i tråd-hastighet. Men flera associativa minnesåtkomster behövs för att lösa kollisioner, vilket gör dem långsammare än vad som krävs. Detta motiverar oss att överväga minimala perfekta hashsystem, vilket minskar antalet minnesåtkomster till bara 1 och är också utrymmeseffektiva. Befintliga perfekta hashing algoritmer är inte skräddarsydda för nätverksapplikationer eftersom de tar för lång tid att konstruera och är svåra att implementera i hårdvara. Detta dokument introducerar ett hårdvaruvänligt system för minimal perfekt hash, med utrymmeskrav närmar sig 3,7 gånger informationen teoretiska lägre gräns. Vår konstruktion är flera order snabbare än befintliga perfekta hashsystem. Istället för att använda den traditionella kartläggning-partitioning-searching metod, använder vårt system ett Bloom filter, som är känt för sin enkelhet och hastighet. Vi utökar vårt system till den dynamiska inställningen och hanterar därmed tillägg och raderingar.
Bloom filterbaserade sammanfattningar används också för minimal perfekt hashing REF ).
Perfect Hashing for Network Applications
{'venue': '2006 IEEE International Symposium on Information Theory', 'journal': '2006 IEEE International Symposium on Information Theory', 'mag_field_of_study': ['Computer Science']}