Lecture notes for CS 503, Advanced Programming I

Advanced Programming I Lecture Notes

4 April 2006 • 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.