Data Structures & Algorithms Lecture Notes

8 December> 2010 • 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 24 January 2006.