Get the nearest / next match in a .NET Hashtable (or other structure)

Question

I have a script at work where we have several different data tables in a format similar to the following:

Table Name: HingeArms Hght Part #1 Part #2 33 S-HG-088-00 S-HG-089-00 41 S-HG-084-00 S-HG-085-00 49 S-HG-033-00 S-HG-036-00 57 S-HG-034-00 S-HG-037-00 

If the first column (and possibly more) contains numerical data sorted in ascending order and represents a range for determining the correct record of data to receive (for example, height <= 33, then part 1 = S-HG-088-00, height < = 41, then part 1 = S-HG-084-00, etc.)

I need to find and select the closest match to a given value. For example, given height = 34.25, I need to get the second entry in the above set:

 41 S-HG-084-00 S-HG-085-00 

These tables are currently stored in the VB.NET Hashtable cache for data loaded from a CSV file, where the key for the Hashtable is an integral part of the table name and one or more columns from the table that represent the "key" for writing. For example, for the above Hashtable Add table for the first record would be:

 ht.Add("HingeArms,33","S-HG-088-00,S-HG-089-00") 

This seems less optimal, and I have some flexibility to change the structure if necessary (the cache contains data from other tables where direct search is possible ... these "range" tables were simply dumped because it was "easy",). I was looking for the Next method in the Hashtable / Dictionary to give me the closest matching record in a range, but this is clearly not available in stock classes in VB.NET.

Any ideas on how I can do what I'm looking for with a Hashtable or in another framework? It must be executed, since the search will often be called up in different sections of the code. Any thoughts would be greatly appreciated. Thanks.

Answer 1

A hash table is not a good data structure for this, because the elements are scattered around the internal array according to their hash code, not their values.

Use a sorted array or List <T> and do a binary search like

Setup:

 var values = new List<HingeArm> { new HingeArm(33, "S-HG-088-00", "S-HG-089-00"), new HingeArm(41, "S-HG-084-00", "S-HG-085-00"), new HingeArm(49, "S-HG-033-00", "S-HG-036-00"), new HingeArm(57, "S-HG-034-00", "S-HG-037-00"), }; values.Sort((x, y) => x.Height.CompareTo(y.Height)); var keys = values.Select(x => x.Height).ToList(); 

Search:

 var index = keys.BinarySearch(34.25); if (index < 0) { index = ~index; } var result = values[index]; // result == { Height = 41, Part1 = "S-HG-084-00", Part2 = "S-HG-085-00" } 

Answer 2

How about LINQ-to-Objects (this in no way means that it is a solution for execution, by the way.)

 var ht = new Dictionary<string, string>(); ht.Add("HingeArms,33", "S-HG-088-00,S-HG-089-00"); decimal wantedHeight = 34.25m; var foundIt = ht.Select(x => new { Height = decimal.Parse(x.Key.Split(',')[1]), x.Key, x.Value }).Where( x => x.Height < wantedHeight).OrderBy(x => x.Height).SingleOrDefault(); if (foundIt != null) { // Do Something with your item in foundIt } 

Answer 3

You can use a sorted .NET array in combination with Array.BinarySearch (). If you get a non-negative value, this is an exact match index. Otherwise, if the result is negative, use the formula

 int index = ~Array.BinarySearch(sortedArray, value) - 1 

to get the index of the previous “closest” match.

The nearest value is determined by the comparator you are using. It should be the same that you used when sorting the array. Cm:

http://gmamaladze.wordpress.com/2011/07/22/back-to-the-roots-net-binary-search-and-the-meaning-of-the-negative-number-of-the-array- binarysearch-return-value /