The ‘Hash Map’ Data Structure
Feb 192018Computers read data from memory by its address — and memory addresses are numbers — so arrays are a natural data structure for sequence types which support ‘getting’ values by their numeric index. When we ‘get’ from an array, the computer can use the index to calculate the memory address of the value we want.
To implement a dictionary, we need a way to ‘get’ values by their keys.
An array is an efficient data structure because its indices are a compact range of numbers; but the keys in a dictionary generally aren’t numbers, so it’s not obvious how a key like "foo" can be used to find where in memory the value associated with it is.
If we can’t directly calculate where the value is, we’d have to search for it, and this could be quite slow if there is a lot of data to search through.