Re: Generating hash tables from known input (bibliography)

Peter Sherwood:


      "Minimal Perfect Hash Functions Made Simple", by Richard J. Cichelli,
      CACM 23 #1 17-19 (1980) describes a method for creating perfect hash
      functions from character strings of the form


hash value <- key length + key 1st char + key last char


here is a somewhat more detailed bibliography. Also must-see:
[ftp.cs.uq.oz.au, in directory pub/TECHREPORTS/department
as TR0234.ps.Z]:


%A George Havas
%A Bohdan S. Majevski
%T Optimal algorithms for minimal perfect hashing
%R Technical Report 234
%I The University of Queensland, Key Centre for Software Technology
%C Queensland
%D July 1992


oz
---
ps: I have not had the time to clean-up this biblio, but I hope
        it is still useful. please send me any corrections, additions,
        etc.
---
%A Anderson, M.R.
%A Anderson, M.G.
%T Comments on Perfect Hashing Functions: A Single
Probe Retrieving Method for Static Sets
%J C.ACM
%V 22(2):104-105
%D (Feb 1979)


%A Berman, F.
%A Bock, M.E.
%A Dittert, E.
%A O'DoneIl, M.I.
%A Plank, P.
%T Collections of functions for perfect hashing
%J SIAM J on Computing
%V 15(2):604-618
%D (May 1986)


%A Brain, M.D.
%A Tharp, A.L.
%T Perfect Hashing Using Sparse Matrix Packing
%J Inform. Systems, l
%V 5(3):281-290
%D (1990)


%A Cercone, N.
%A Boates, I.
%A lcrause, M.
%T An Interactive System for Finding Perfect Hashing Functions
%J IEEE Software
%V 2(6):38-53
%D (1985)


%A Chang, C.C.
%T The Study of an Ordered Minimal Perfect Hashing Scheme
%J C.ACM
%V 27(4):384-387
%D (Apr 1984)


%A Chang, C.C.
%A Lee, R.C.T.
%T A Letter-oriented minimal perfect hashing
%J Computer Journal
%V 29(3):277-281
%D (June 1986)


%A Cichelli, R.I.
%T Minimal Perfect Hash Functions Made Simple
%J C.ACM
%V 23(I):17-19
%D (Ian 1980)


%A Cormack, G.V.
%A Horspool, R.N.S.
%A Kaiserswerth, M.
%T Practical perfect hashing
%J Computer Journal
%V 28(l):54-55
%D (Feb 1985)


%A Dietzfelbinger, M.
%A Karlin, A.R.
%A Mehlhorn, K.
%A Meyer auf der Heide, F.
%A Rohn ert, H.
%A Tarjan, R.E.
%T Dynamic Perfect Hashing
%J Proceedings FOCS, White Plains NY
%V 29:524-531
%D (Oct 1988)


%A Sprugnoli, R.
%T Perfect Hashing Functions: A Single Probe
Retrieving Method for Static Sets
%J C.ACM
%V 20(11):841-850
%D (Nov 1977)


%A Winters, V.G.
%T Minimal perfect hashing in polynomial time
%J BIT
%V 30(2):235-244
%D (1990)


%A Yang, W.P.
%A Du, M.W.
%T A Dynamic Perfect Hash Function defined by an
Extended Hash Indicator Table
%J Proceedings VLDB, Singapore
%V 10:245-254
%D (1984)


%A Yang, W.P.
%A Du, M .W.
%T A backtracking method for constructing perfect
hash functions from a set of mapping functions
%J BIT
%V 25(1):148-164
%D (1985)
--

Return to the comp.compilers page.
Search the comp.compilers archives again.