home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / programm / 2580 < prev    next >
Encoding:
Text File  |  1992-09-08  |  1.7 KB  |  42 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!cs.utexas.edu!torn!cunews!nrcnet0!bnrgate!bcrka451!bcrki65!sjm
  3. From: sjm@bcrki65.bnr.ca (Stuart MacMartin)
  4. Subject: Re: Dynamic Hashing Algorithm needed
  5. Message-ID: <1992Sep8.172711.3195@bcrka451.bnr.ca>
  6. Sender: 5E00 Corkstown News Server
  7. Reply-To: sjm@bcrki65.bnr.ca (Stuart MacMartin)
  8. Organization: Bell-Northern Research, Ottawa, Canada
  9. References: <dwagon.715675729@nella9.cc.monash.edu.au> 
  10. Date: Tue, 8 Sep 1992 17:27:11 GMT
  11. Lines: 29
  12.  
  13. In article <dwagon.715675729@nella9.cc.monash.edu.au>
  14. dwagon@nella9.cc.monash.edu.au (Dougal Scott) writes:
  15. >Does anyone have an algorithm for dynamic hashing? I remember reading about it
  16. >somewhere, but cannot remember where.
  17. >-- 
  18.  
  19. Dynamic File Structure for Partial Match Retrieval
  20. Based on Overflow Bucket Sharing.  Tak-Sun Yuen and David Hung-Chang Du,
  21. IEEE Transactions on software engineering vol. SE-12 No.8 August 1986
  22.  
  23. Note: The hash value is unconstrained; the hash table uses only n bits of it
  24. in any overflow bucket.  The full hash value of each key is held with
  25. the key in the overflow bucket, so you might as well use it when scanning
  26. overflow buckets for an exact match.  This saves on expensive comparisons,
  27. e.g. strcpy
  28.  
  29. If you need dynamically-extensible hashing on disk using little memory:
  30.  
  31. University of Warwick Theory of Computation Report no.27:
  32. Spiral Storage: incrementally augmentable hash addressed storage
  33. G.N.N. Martin  March 1979
  34.  
  35. Hope this is what you wanted.
  36.  
  37. Stuart
  38.  
  39. : Stuart MacMartin                                    email: sjm@bnr.ca      :
  40. : Bell-Northern Research                              phone: (613) 763-5625  :
  41. : PO Box 3511, Stn C, Ottawa, K1Y-4H7, CANADA    Standard disclaimers apply. :
  42.