文章基本信息

标题：A Hybrid Chaining Model with AVL and Binary Search Tree to Enhance Search Speed in Hashing
本地全文：下载
作者：Akshay Saxena ; Harsh Anand ; Tribikram Pradhan 等
期刊名称：International Journal of Hybrid Information Technology
印刷版ISSN：1738-9968
出版年度：2015
卷号：8
期号：3
页码：185-194
DOI：10.14257/ijhit.2015.8.3.18
出版社：SERSC
摘要：The main idea behind any hash function is to find a one to one correspondence between a key value and an index in the hash table where the key value can be placed. In closed hashing, it is very difficult to handle the situation of table overflow in a satisfactory manner. Key values are haphazardly placed and generally majority of the keys are placed far away from their hash location. Thus, the number of probes is greatly increased which degrades the overall performance. To resolve this problem another hashing method known as open hashing (separate chaining) is employed. But this type of hashing is still not efficient in case of searching because here all the elements that have the same hash function are inserted in a sequential order. Due to this, traversal of all the previously inserted elements is required when we are searching for the last element. So the overall complexity will be O (n). In this paper, we propose a hybrid chaining model which is a combination of Binary Search Tree and AVL Tree to achieve a complexity of O (log n).
关键词：Hashing; AVL Tree; Binary Search Tree (BST); Separate Chaining Method; ; Hybrid Chaining Model