Data Structures for coding interviews

So we can use the character(‘s number value) as the index in our array, and store the count for that character at that index in the array:

With this array, we can look up (and edit) the count for any character in constant time. In our hash table, the counts are the values and the words (“lies,” etc.) are the keys (analogous to the indices in an array). Here’s a common one: instead of storing the actual values in our array, let’s have each array slot hold a pointer to a linked list holding the counts for all the words that hash to that index:

One problem—how do we know which count is for “lies” and which is for “foes”?

Source: www.interviewcake.com