Browse Prior Art Database

Hop list : An optimized solution for fast lookup Disclosure Number: IPCOM000249578D
Publication Date: 2017-Mar-03
Document File: 2 page(s) / 30K

Publishing Venue

The Prior Art Database


This research disclosure talks about an innovative method to improve and optimize look up efficiency using Hash Tables. It introduces a new data-structure known as "Hop-list" and dictates its ingrediants.

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


Hop list : An optimized solution for fast lookup

Hash Table is a data structure that allow relation between two entities such as data of arbitrary length with data of fixed length. Hash Tables in general provides a key : value pair of mapping on a certain range. Applications of Hash Table include HRMS to search employee database. The best case complexity shall be O(1) for look-up, delete and insert operations.

However , with chained probing the worst case look-up shall become O(n). There are various hashing techniques that discuss solutions to resolve worst case complexity including cuckoo hashing, hopscotch hashing and more which involves rebuilding of hash table involving cumbersome exercise. Both collision and rebuilding table should be avoided as far as possible for an efficient look-up.

A creative hashing technique that shall improve the look-up complexity with chain addressing technique is discussed here. The core idea behind this publication is to improve the performance of the hash table when collision occurs in case of chaining.

Consider a Hash Table with chained hashing. The Hash Table shall have chain of either singly linked list or doubly linked list at the index of the table. In normal chaining all the entries that hashes at the collided location , say index 1 on the hash table shall appear one after the other in same chain forming a bucket of entries. The novel hashing table will have the following contents.

Ingredients : > Two hash functions [hv1 & hv2] with different algorithms. > Hash node- Contains data and hash value computed from h2(x) > Hop/load factor - This is number of elements that a sub-chain can hold for considering a

hop to next sub-chain. The hop factor can be square root of bucket size or bucket size/(N) where N is a

random number which can li...