Browse Prior Art Database

Minimizing the hash node/bucket allocations and hash operations while searching different fields across different hash tables.

IP.com Disclosure Number: IPCOM000255766D
Publication Date: 2018-Oct-12
Document File: 5 page(s) / 196K

Publishing Venue

The IP.com Prior Art Database

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 34% of the total text.

Minimizing the hash node/bucket allocations and hash operations while searching different fields across different hash tables.

This article contains a new method to create and allocate the hash bucket nodes which will result in overall reduced memory consumption. It compares a traditional method of creating different hash tables to search different entries of a structure with the proposed method. In the current hash table implementations, fields like either “name” or “id” fields of an object/structure are used for searching values in a single hash table. This means that only a value of a single kind/type can be searched over a hash table. If an object containing different fields were to be searched in a hash table using any of the different fields within this object, then different hash tables would be required. That is, one hash table for each of the different fields within the object, and each hash table with its own set of hash buckets. Moreover, as these fields belong to the same object, each hash table would have the entire instance of the object’s data in one of its hash bucket node. This leads to the need for the data to be consistent across all the hash tables. So, updating a node means updating all other instances of this node in its respective hash bucket across the different hash tables. The problem that this article addresses is how to minimize the hash bucket allocation and the hash search operations for an object with many fields. Especially where any of these fields would be used for searching across different hash tables. The object/structure referred to in the document is assumed to consist of different kinds of primitive data types. Currently, most of the hash implementations would address the problem by having different hash tables, one table per different field in the object. The following is a list of the drawbacks with such implementation: a. More Memory consumption owing to several hash buckets spread across N-different hash tables. b. Data from a structure will be duplicated across N different hash tables. c. Multiple look ups in different hash table while removing old objects or adding new objects or updating existing objects in the program. This article does not claim to have an efficiency of O(1) as that would depend on the hash algorithm used to generate the hashes. This article discusses optimization solutions mainly for the hash buckets also known as extendible hashing which is a common mechanism used to resolve hash collisions.

This article provides a mechanism to store the data in a hash table in a way that minimizes the hash bucket allocation and the hash search operations for an object that can be searched via any of its fields. The core of this approach is in creating a pointer (/a set of pointers) per field in the object to indicate its position in the hash bucket list. That is, if there are N-fields in the object which can be used for searching this object (that is if N-fields need to be hashed), then ther...