Data Centers

On the Performance of Multiple Choice Hash Tables With Moves on Deletes and Inserts

Download Now Free registration required

Executive Summary

High-performance hashing has become a fundamental subroutine for a wide variety of high performance network processing tasks, including header lookup for routing, measurement, and monitoring. In considering hashing alternatives, many possible considerations arise, perhaps the most important being how much time is spent performing lookup, insert, and delete operations, and how much space the table requires. Here time primarily corresponds to the number of hash tables entries that are read and, when items can be moved within the hash table, the number of items that are moved, as computation is often free compared to the time to perform a memory access or a write.

  • Format: PDF
  • Size: 90.5 KB