Home > Uncategorized > Use a Hash Map instead

Use a Hash Map instead

I learned a valuable lesson just before coming to Sentry that I’ve shared with my co-workers and thought I’d share here at well.

If you find yourself searching through an array try to turn it into a hash/map instead.

Instead of an O(N) operation (looking at every element in an array), you can often turn it into a direct access hash map O(1).  Remember Big-O notation? Make sure you keep that in your hip pocket.  You never know who may ask about it (Amazon and Google will).

You rarely write your own search function since most languages provide one for you.  The PHP function in_array($needle, $haystack)) is your O(N) search and will only get worse as the size of the array gets bigger.  It’s tempting to throw that in whenever needed.

Here’s a quick PHP snippet that I recently worked through with another developer.

// $worksheet_names is still an array, but we
// use the index/key of the array instead of the value.
$worksheet_names = array();

foreach ($results as $row) {
     ...
     // instead of in_array, we look directly at the index.
     // previously in_array($name, $worksheet_names)
     while (isset($worksheet_names[$name])) {
         $name = substr($name,0,24) . "($duplicate_sheet_counter)";
         $duplicate_sheet_counter += 1;
     }
     $row['worksheet_name'] = $name;
     // previously $worksheet_names[] = $name;
     $worksheet_names[$name] = true;
}
Other Uses
Another helpful trick is to keep track of duplicate values in an array.  What’s the easiest way to get the number of occurrences for all these values?
<?php

$a = array (1, 2, 3, 3, 1, 4, 5, 3, 4);

$map = array();
foreach  ($a as $entry) {
     if (!isset($map[$entry])) {
          $map[$entry] = 1;
     } else {
          $map[$entry]++;
     }
}

print_r($map);
Array
(
    [1] => 2
    [2] => 1
    [3] => 3
    [4] => 2
    [5] => 1
)
Advertisements
Categories: Uncategorized Tags:
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: