首页 | 本学科首页   官方微博 | 高级检索  
     


Tightly controlled linear hashing without separate overflow storage
Authors:James K. Mullin
Affiliation:(1) Computer Science Department, University of Western Ontario, N6A 5B9 London, Ontario, Canada
Abstract:
A hashing method is presented where the amount of storage required for a file can expand and shrink by very large factors. The performance of this method as measured by lookup time, insertion time and deletion time is very good even when the total storage utilization is as high as 90 percent. The user can completely control the storage utilization between two chosen bounds so that the storage requirement varies linearly with the number of records currently in the file.Unlike previous methods, no separate overflow storage pool is involved and one need not be concerned with expected and worst case requirements for overflow space. Indeed, the absence of requirements for such a separate overflow pool could allow the use of this method with primitive microprocessor operating systems.The choice of hashing functions is discussed and simulation results show great danger in blindly using the popular remainder method.Both an elementary analysis and simulation results are given.This research was supported by the National Science and Engineering Research Council of Canada.
Keywords:hashing  linear hashing  dynamic hashing
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号