What is the difference between array and hash?

Answer 1

An array stores elements in a sequential order from zero (or one) up to the size of the array (possibly minus one, if starting from zero). Arrays come from the classic days of computer programming performed with assembler code, where one would often have a base pointer (BP or BX) plus an index (SI or DI) plus a constant offset, if any.

To address the fourth element in an array, one would specify the BP of the array's initial index (index 0), then add an index to it. For example, add [bp+di], ax would add the contents of AX (a 16-bit register) to the memory location referenced by BP with DI added to it, both also 16-bit registers in classic assembler. Some languages, such as BASIC, ignored the zero index or used it for other purposes.

Arrays are generally fixed in size-- reallocation is necessary to increase or decrease the size of the array. They must also be initially allocated with some amount of memory before they can be used. Newer languages offer dynamic arrays, sometimes called vectors (a point with a line that has an infinite length) to represent arrays that automatically scale capacity as it is filled.

Hashes, in contrast, do not use traditional indexes; they are not represented by the bp + di model, but instead use objects as their indices. This leads to certain inconveniences, because objects are not necessarily sorted from smallest to largest, or lexicographical order, but simply by computed indexes based on the key's hash. Most languages smooth out this limitation by using b-trees (binary trees) to store the keys and their indices, so that iterations over the values of the hash are in key order, but this is not strictly a requirement.

Hashes have no maximum size, unlike traditional arrays. Increasing the size of the hash is a simple as assigning a new key a value. In this respect, they are similar to vectors, but they answer an important question: how does one find an element in a vector in constant time? The answer, of course, is that vectors must be traversed from the first index to the target index in order to find the value, so searches require linear time to find a value.

By using keys, the search complexity is reduced from linear time to constant time, offering a significant advantage on looking up data versus using a vector, linked list, or even an array of objects. Hashes use constant time look ups, just like an array does, but gives the added flexibility of specifying how the data is indexed, instead of just a number. This is especially useful for algorithms involving translating data (ETL) or looking up data that meets a certain criteria repeatedly in constant time, which can have a savings factor of hundreds or thousands times more than an array.

Answer 2

The main difference is usage...a hash is an array, of sorts. Speaking of sorts, the comparison between a hash and an array takes on meaning when you compare a "sorted array" and a hash. Otherwise, an array is just a series of memory locations containing data in whatever order you cram data in. This is an indexed array, BTW, not a virtual structure, like a doubly-linked list (DLL).

A sorted array (of any number of dimensions) has a sort time roughly N^2, so as the array gets bigger, you still search easily (using binary search), but the maintenance of the sort gets expensive. A hash uses a key-algorithm on the data (like what is the ASCII value of the first 3 characters MOD 25 ... or whatever), and thus quickly determines which of 25 buckets to dump the value. It's 'kinda' sorted, but not really. It just quickly tells you which bucket to dig through. Fancier hash algorithms are tuned to the nature of the data, and either naturally or heuristically maintain balance (equalized buckets). In this way, you insert data into a hash quickly, and then you have a roughly constant search time (rather than 0.5*N), reduced by whatever factor your hashing algorithm allows.

The simplest way to think of hash is to imagine the phone book split into 26 separate books (hashed on first letter of last name). You can imagine a 2-D array storing all the 'A' names in the first "row" of a row-major 2-D array, all the 'B' names in the second row, etc. This example isn't balanced, but then again, the hash isn't all that fancy either. You can then make the arrays dynamic, apply a better hash, etc. and come up with an easily inserted data structure with a constant search time. This can be nice for a list with low data volume, lots of inserts and proportionally few searches or deletes. It won't be in any sort of order, but it's less costly (in processor time) to maintain than a sorted array(s) or binary tree structures. Unfortunately, they're of limited utility, but in the right situation, they can be quite useful.

For instance, during collection of data, one might use a hash to just get the data roughly together, and make finding/eliminating the occasional duplicate value a little easier, but wait to sort until all data aquisition is done. Thus, you might incur the sorting expense only once, after you have all the data stored in a relatively inexpensive hashed table or array, instead of each time a record is added.