Browse Prior Art Database

Optimization : Improving hashing efficiency for average and worst case lookup

IP.com Disclosure Number: IPCOM000249420D
Publication Date: 2017-Feb-27
Document File: 2 page(s) / 26K

Publishing Venue

The IP.com Prior Art Database

Abstract

Optimization : Improving hashing efficiency for average and worst case lookup

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

1

Optimization : Improving hashing efficiency for average and worst case lookup

Disclosed is a research publication that talks about optimization of hash data structure for average and worst case look-up.

Optimization : Hash Table is a data structure that allow relation between two entities such as data of arbitrary length maps with data of fixed length. Hash Table in general provides a key::value pair of mapping on a certain range. The best case complexity of Look-up , Delete and Insert shall be O(1). However , with chained probing the worst case look-up shall become O(n). Various hashing techniques to resolve worst case complexity include cuckoo hashing, bloom filters and they involve rebuilding of hash table. Rebuilding of hash table is a cumbersome exercise. The goal here will be to avoid both collision and rebuilding table as far as possible for an efficient look-up.

Going forward in this section , a deep dive into a hashing technique that shall improve the look-up time complexity with chain addressing technique shall be taken.

Now, 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. With this technique hashing is achieved using two hash functions , h1(x) and h2(x). The contents are discussed below :

Ingredients :

Contains two hash functions [hv1 & hv2] with different algorithms. They can be a  universal hash functions as well. Contains hash-node which holds data and hash value computed from h2(x). Anchor to middle of chain. Anchor to end of chain.

Algorithm :

Insert(x) Compute hash value for h1(x) and h2(x) from hash-functions, hv1and hv2 respecti...