Disclosed are exemplary techniques for compressing ATM cells by substituting reduced headers for the original headers. A header table may be maintained at the transmitting end whereby headers are stored in table entries based on a table index generated from a hash function applied to the headers. A copy of the header table may be maintained at the receiving end and may be updated by populating idle cells with header table contents. Upon receipt of a reduced ATM cell at the receiving end, the reduced header may be replaced with a full header obtained from the copy of the header table maintained at the receiving end. The present invention further provides techniques for registration and management of hash collisions.