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:
|
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.
| 
No comments:
Post a Comment