I'm trying to understand hash tables - can someone explain it to me - clearly?

Question

I want to understand the correct use and implementation of hash tables in php (sorry).

I read somewhere that an in-experienced programmer created a hash table and then iterated through it. Now, I understand why that is wrong but I haven't quite got the full knowledge to know if my understanding is correct (if you know what I mean).

So could someone explain to me how to implement a hash table in php (presumably an associative array) and perhaps more importantly, how to access the values 'with a hash' and what that actually means?

Answer 1

Simple Hash Table Overview

As a refresher, a hash table is a way to store a value under a specific key in a data structure. For instance, I could store value "a" under the key 1, and then later retrieve it by looking up the key 1 in the hash table.

The simplest example of a hash table that I can think of off the top of my head is a hash table that can only store integers, where the key for the hash table entry is also the value being stored. Let's say your table is of size 8, and it's basically an array in memory:

---------------------------------
|   |   |   |   |   |   |   |   |
---------------------------------
  0   1   2   3   4   5   6   7  

Hash Function

Hash functions give you an index on where to store your value. A pretty simple hash function for this table would be to add 1 to the value you want to store, and then mod it by 8 (the table size). In other words, your hash function is (n+1)%8, where n is the integer you want to store.

Inserts

If you want to insert a value into this hash table, you call your hash function (in this case (n+1)%8) on the value you want to insert to give you an index. For instance, if we want to insert 14, we would call (14 + 1) % 8 and get index 7, so we'd insert it the value in index 7.

---------------------------------
|   |   |   |   |   |   |   |14 |
---------------------------------
  0   1   2   3   4   5   6   7  

Similarly, we can insert 33, 82, and 191 like so:

---------------------------------
|191|   |33 |82 |   |   |   |14 |
---------------------------------
  0   1   2   3   4   5   6   7  

Collisions

But what happens if we try to insert something that would collide with an entry? 2 should go in index 3, but it is taken by 82. There are multiple ways to solve this issue, the simplest is to call our hash function again and again repeatedly until we find an empty space.

So the logic is as follows:

1. (2+1)%8 = 3
2. Index 3 is full
3. Plug 3 back into our hash function. (3 + 1) % 8 = 4, which is empty.
4. Place our value into index 4.

Now the hash table looks like this, with the value 2 stored at index 4.

---------------------------------
|191|   |33 |82 |2  |   |   |14 |
---------------------------------
  0   1   2   3   4   5   6   7  

The downside with this solution is that pretty soon, our table will get full! If you know that your data size is limited, this shouldn't be an issue as long as your table is large enough to hold all possible values. If you want to be able to hold more, you can handle collisions differently. Let's move back to where we were before inserting 2.

---------------------------------
|191|   |33 |82 |   |   |   |14 |
---------------------------------
  0   1   2   3   4   5   6   7  

If you recall, (2+1)%8 gives us index 3, which is taken. If you don't want your hash table to fill up, you can use each table index as a linked-list, and append to the list at that index. So instead of calling the hash function again, we'll simply append to the list at index 3:

            -----
            | 2 |
---------------------------------
|191|   |33 |82 |   |   |   |14 |
---------------------------------
  0   1   2   3   4   5   6   7  

This list can then grow as much as memory will allow. I can insert 18, and it will just be appended to 2:

            -----
            |18 |
            -----
            | 2 |
---------------------------------
|191|   |33 |82 |   |   |   |14 |
---------------------------------
  0   1   2   3   4   5   6   7  

Lookups

Lookup up values in your hash table is quick, given that your hash table is of a pretty large size. You simply call your hash function, and get the index. Let's say you want to see if 82 is in your table. The lookup function would call (82+1)%8 = 3, and look at the item in index 3, and return it for you. If you looked up 16, the lookup function would look in index 1, and see that it does not exist.

Lookups Need to Handle Collisions, too!

If you try to look up the value 2, your hash table would have to use the same collision logic it used for storing the data as for retrieving the data. Depending on the way your hash table works, you would either hash the key over and over until you find the entry you are looking for (or find a blank space), or you would iterate through your linked list until you found the item (or got to the end of the list)

Summary

So, hash tables are a good way to store and access key-value pairs quickly. In this example we used the same key as the value, but in real world hash tables the keys aren't so limited. Hash functions will work on the keys to generate an index, and then the key/value can be stored at that index. Hash tables aren't really meant to be iterated through, although it's possible to do so. As you can see, hash tables can have lots of blank spaces, and iterating through them would be a waste of time. Even if the hash table has logic for skipping blank space lookups in its iterator, you would be better suited using a data structure that is designed for iterators, like linked lists.

Answer 2

Imagine a library with thousands of books. You need to organize the books so that you'd be able to find each by title as quickly as possible.

One (common) way to do this is to sort the books alphabetically. If your title starts with say "G" you find the "G" area, then look for the second letter, say "ö", then "d", "e", "l", narrowing down your search, and so on, until you find the book. This, though, may take long and besides, when new books arrive you sometimes need to reorganize your layout to make room for the new arrivals.

That's binary search. It's good.

There is, however, a quicker way of doing this. Let's say you enumerate all the bookcases and shelves, and then for each book you calculate a special, hopefully unique, number that maps to a bookcase/shelf where the book should be found. The way you calculate the "key" doesn't matter much as long as it gives a random-looking number. For example, you could add character codes of all the letters in the title and then divide that by some prime number (possibly not the best method, but works anyway).

That's hashing. It's much quicker, because you don't need to go through whole bookcases and shelves looking up the next letter in the title. Hashing is usually a one-shot operation, unless you have a "collision" when two or more books resolve to the same key. But that's fine, you know they lie next to each other and, depending on the quality of the hash function, there shouldn't be too many under the same key.

Hash tables have some limitations and whims (rehashing/resizing), which keeps binary search around as a viable competitor. It's not all black & white with regard to which method is better. But that's a different story.

P.S. Sorry for not answering your question directly (write a hash table in PHP), but that's details and it's called "programming" ;)

Answer 3

The hash table in PHP, as far as my knowledge goes, is simply implemented via a:

$my_hash = array(
    1 => "Bob",
    2 => "Alice",
    3 => "Jack"
);

You then access the data via calls such as:

echo $my_hash[2]; // Will echo "Alice"

You use the foreach() function to iterate over the array's contents.

The best way to understand hash tables is to read something like http://en.wikipedia.org/wiki/Hash_table, but roughly it boils down to this: the left hand side of every line inside that array() call are the keys. These keys will be put through a hash calculation and the result is a hash. You have probably seen MD5 or SHA hashes before, it looks quite similar to this. A specific part of this hash, typically the first X characters but sometimes the complete hash, will be used to identify the so-called 'buckets', which are the storage areas for the values (the right hand side).

Then whenever you access your hashtable, you use the key to get to the value. The key gets calculated to a hash again and the hash is used to quickly look up the associated value. So hash tables allow for a faster look up than just searching lineary if everything was just stored. The only downside is that some hash implementations suffer from collisions, which is the same calculated hash for two different keys. In general, it's not something you have to worry about much.

I hope this provides some background, but please try to read up more about the subject if you are interested in it. My explanation is very rudimentary and I am sure there's enough holes in there, but it should suffice for a quick explanation.