Menu
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 want to. But I don't know how to start.
Can anyone give me 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.
Thanks a lot.
481
In arrays, you have to loop over all items before you find what you are looking for while in a hash table you go directly to the location of the item. Inserting an item is also faster in Hash tables since you just hash the key and insert it. In arrays shifting the items is important first before inserting another one.
Searching over a data structure such as an array presents a linear time complexity of O(n). In other words, as the data structure increases in size, the search time increases in a linear fashion. Simply put, using a hash table is faster than searching through an array.
A hash table is different from binary trees and linked lists in the sense that it is implemented with an array. It stores data as key-value pairs. Each data value in a hash table has a key or index that is produced using a technique known as hashing.
In PHP, associative arrays are implemented as hashtables, with a bit of extra functionality.
However technically speaking, an associative array is not identical to a hashtable - it's simply implemented in part with a hashtable behind the scenes. Because most of its implementation is a hashtable, it can do everything a hashtable 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 hashtable.
So while they're similar, an associative array can actually do a superset of what a hashtable can do - so they're not exactly the same thing. Think of it as hashtables plus extra functionality.
Code examples:
Using an associative array as a hashtable:
$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 hashtable. //now we loop through the array - you can't do this with a hashtable: 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 Marc) based on the order in which they were entered into the array. This is a major difference between associative arrays and hashtables. A hashtable maintains no connection between the items it holds, whereas a PHP associative array does (you can even sort a PHP associative array).
77
php arrays ARE basically hash tables
44
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
