Data Structures and Algorithms Lecture Notes

25 April 2011 • Hashing Basics

Data alignment requirements can make this interpretation difficult. Multi-field keys may contain gaps or padding between fields that don’t align properly otherwise. For example, on some system architectures the struct 

struct S {
  char c;
  int i;
  };

contains a three-byte pad between c and i. The contents of pads are undefined, which means that a byte-by-byte comparison of what should be identical instances of struct S may fail due to differences in the bits stored in the pad. 

  struct S 
    s1 = { .c = 'a', .i = 10 },
    s2 = { .c = 'a', .i = 10 };
  assert(0 == memcmp(&s1, &s2, sizeof(struct S))) // may fail.

The problem this causes for hashing is clear: if the hash function includes the pad bytes as part its computation, s1 and s2 could produce different hash values, violating the requirement that identical keys produce identical hash values.

This page last modified on 2006 January 24.