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.
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).