Quote:
I'd probably just make linked lists of every element in an array. That is, each element would be a pointer to a SSN, and each element pointed to by an identifier (I know, I'm not using the term properly).

"John Doe" -> a[1] -> 195484222
"Jane Doe" -> a[2] -> 60958542

So how does "Jane Doe" resolve to a[2]? If I give you "Jane Doe" what process do you use to get me back 60958542? It looks like you're thinking of looping over the list of names until you find Jane, which tells you which index to use to index into "a" which in turn tells you the SSN.

A hash table with a decent hash function would make this O(1) instead of O(n).

Quote:
Sorry if I wasn't clear. I was referring to using an enum to represent ints as a string

Not sure what you mean here.

Quote:
Maybe I'm missing something here, but every diagram I can find of a Hash Table involves huge arrays with only a few keys

That's one way to do it. The hash function optimizes this, however. You can consider an array from (integer -> value) to be an extreme worst-case scenario hash table, where the hash function simply returns the key. The better your hash function (and the more clever your underlying bucket implementation), the better the hash table will be.