Hash tables vs. associative arrays

Question

Recently, I have read about hash tables in a very famous book, "Introduction to Algorithms". I haven't used them in any real applications yet, but I want to. But I don't know how to start.
What are some samples of using it, for example, how to realize a dictionary application (like ABBYY Lingvo) using hash tables?

And finally I would like to know what is the difference between hash tables and associative arrays in PHP, I mean which technology should I use and in which situations?

If I am wrong (I beg pardon) please correct me, because actually I am starting with hash tables and I have just basic (theoretical) knowledge about them.

Answer 1

In PHP, associative arrays are implemented as hash tables, with a bit of extra functionality.

However, technically speaking, an associative array is not identical to a hash table; it's simply implemented in part with a hash table behind the scenes. Because most of its implementation is a hash table, it can do everything a hash table can, but it can do more, too.

For example, you can loop through an associative array using a for loop, which you can't do with a hash table.

So while they're similar, an associative array can actually do a superset of what a hash table can do, so they're not exactly the same thing. Think of it as hash tables plus extra functionality.

Code examples:

Using an associative array as a hash table:

$favoriteColor = array();
$favoriteColor['bob'] = 'blue';
$favoriteColor['Peter'] = 'red';
$favoriteColor['Sally'] = 'pink';
echo 'bob likes: ' . $favoriteColor['bob'] . "\n";
echo 'Sally likes: ' . $favoriteColor['Sally'] . "\n";
// Output: bob likes blue
//         Sally likes pink

Looping through an associative array:

$idTable = array();
$idTable['Tyler'] = 1;
$idTable['Bill'] = 20;
$idTable['Marc'] = 4;
// Up until here, we're using the array as a hash table.

// Now we loop through the array - you can't do this with a hash table:
foreach($idTable as $person => $id)
    echo 'id: ' . $id . ' | person: ' . $person . "\n";

// Output: id: 1 | person: Tyler
//         id: 20 | person: Bill
//         id: 4 | person: Marc

Note especially how in the second example, the order of each element is maintained (Tyler, Bill, and Marc) based on the order in which they were entered into the array. This is a major difference between associative arrays and hash tables. A hash table does not maintain any connection between the items it holds, whereas a PHP associative array does (you can even sort a PHP associative array).

Answer 2

PHP arrays are basically hash tables.

Answer 3

The difference between an associative array and a hash table is that an associative array is a data type, while a hash table is a data implementation. Obviously the associative array type is very important in many current programming languages: Perl, Python, PHP, etc. A hash table is the main way to implement an associative array, but not quite the only way. And associative arrays are the main use of hash tables, but not quite the only use. So it's not that they are the same, but if you already have associative arrays, then you usually shouldn't worry about the difference.

For performance reasons, it can be important to know that your associative arrays in your favorite language are implemented as hashes. And it can be important to have some idea of the overhead cost of that implementation. Hash tables are slower and use more memory than linear arrays as you see them in C.

Perl lumps the two concepts together by calling associative arrays "hashes". Like a number of features of Perl, it isn't quite wrong, but it's sloppy.

Answer 4

An array in PHP is actually an ordered map, not a hash table.

The main difference between map and hash table consists in inability to remember the order in which elements have been added. On the other hand, hash tables are much faster than maps. The complexity of fetching an element from a map is O(n·log_n) and from a hash table it is O(1).

Answer 5

An associative array is an array where you don't access elements by an index, but by a key. How this works internally is implementation specific (there is no rule how it must work). An associative array could be implemented by a hash table (most implementations will do that), but it could also be implemented by some sort of tree structure or a skip list or the algorithm just iterates over all elements in the array and looks for a key that matches (this would be awfully slow, but it works).

A hash table is a way how to store data where values are associated to keys and where you intend to find values for keys within a (usually almost) constant time. This sounds exactly like what you expect of an associative array, that's why most of the time hash tables are used for implementing those arrays, but that is not mandatory.