3.9 Simulating a Hash Table for Fast Array Lookup

NN 4, IE 4

3.9.1 Problem

You want to be able to go directly to an entry in an array (especially an array of objects or multidimensional array) without having to loop through the entire array in search of that item.

3.9.2 Solution

By taking advantage of the fact that a JavaScript array is a JavaScript object, you can define properties for an array without interfering with the true array portion of the object. Properties can be referenced by name either by string (in parentheses, like array index value) or following a period like a typical object property.

The key to implementing this construction for an existing array is that you must generate a property for each entry with a unique value. If you are implementing this for an array of objects, use a property value that is unique for each entry as the hash table lookup index.

As a simple example with the coworker objects created in other recipes of this chapter, we'll assume no two coworkers have the same name. Thus, we'll use the name property of the coworker objects as property names for the hash table. Immediately after the array of coworker objects is populated, we execute the following statements:

for (var i = 0; i < employeeDB.length; i++) {
    employeeDB[employeeDB[i].name] = employeeDB[i];
}

Without the hash table, to find the age of a coworker, you have to loop through the employeeDB array in search of a match against the name property of each entry. With the simulated hash table, however, simply reference the unique object bearing the name of the person you're looking for, and retrieve the age property of that object:

var JeansAge = employeeDB["Jean"].age;

You typically use the string way of referring to the object because variable lookup information will likely be coming from a text source: a text input box or a string value of a select element.

3.9.3 Discussion

I cannot overemphasize the importance of the uniqueness of the property name. If you unknowingly have two assignments to the same property value, the last one to execute is the one that sticks.

If one property of an object is not enough to make it unique, you may need to combine values to obtain that uniqueness. For example, the following table's data could be made into a convenient array of objects:

Description	Q1	Q2	Q3	Q4
East	2300	3105	2909	4800
Central	1800	1940	2470	4350
West	900	1200	1923	3810

Each cell of numeric data should be its own object, with other properties assisting in identifying the context of the number. For example:

var sales = new Array( );
sales[sales.length] = {period:"q1", region:"east", total:2300};
sales[sales.length] = {period:"q2", region:"east", total:3105};
...
sales[sales.length] = {period:"q4", region:"west", total:3810};

None of the label properties�the properties you'd likely be using to look up sales information�is totally unique. The East region is shared by four objects, and the Q1 period is shared by three objects. But a combination of the region and period names generates a unique identifier for a given object. Thus, if we use a name of the form region_period (e.g., east_q1), other scripts can perform lookups to reach individual records. Therefore, the hash table maker comes after the object creation statements above:

for (var i = 0; i < sales.length; i++) {
    sales[sales[i].region + "_" + sales[i].period] = sales[i];
}

To access the third quarter sales for the central region, use the following reference:

sales["central_q3"].total

When a hash table entry is assigned a reference to an object (as happens in the preceding examples), each hash table entry simply points to the original object without duplicating the data. Any change you assign to an object's property in the array of objects is reflected in the hash table reference to that object's property.

Any time you have a large multidimensional array or collection of objects through which your scripts will be looking for matching records, try to add the simulated hash table to your array. It gives you the best of both worlds: the ability to iterate through the collection when you need to use every entry, and the ability to dive into a specific record without any looping.

3.9.4 See Also

Recipe 8.13, Recipe 10.8, and Recipe 14.5 for real-world examples of the simulated hash table in action.