[Home]
[Contents]
[Chapter]
[Previous Algorithm]
[Next Algorithm]


Perfect hashing insertion


int insert( input, n, r, A ) dataarray input, r; int n, *A; { extern int m, m2; int d, i, ia, ib, iup, j; datarecord tempr; if( m < n ) return(0); for( i=0; i<m2; i++ ) A[i] = 0; for( i=0; i<n; i++ ) A[ input[i].k % m2 ]++; /* Shellsort input array based on collision counts */ for ( d=n; d>1; ) { if (d<5) d = 1; else d = (5*d-1)/11; for ( i=n-1-d; i>=0; i-- ) { tempr = input[i]; ia = tempr.k % m2; for ( j=i+d; j<n && (A[ia] < A[ib=input[j].k % m2] || A[ia] == A[ib] && ia > ib); j+=d ) input[j-d] = input[j]; input[j-d] = tempr; } } for( i=0; i<n; i=iup ) { ia = input[i].k % m2; iup = i + A[ia]; for( A[ia]=ib=1; ib < 9*m; A[ia] += ib++ ) { for( j=i; j<iup && empty(r[hashfunction(A[ia],input[j].k)]); j++ ) r[hashfunction(A[ia],input[j].k)] = input[j]; if( j >= iup ) break; for( j--; j >= i; j-- ) r[hashfunction(A[ia],input[j].k)].k = NOKEY; } if( ib >= 9*m ) /* Cannot build optimal hashing table with m and m2 */ return(0); } return(1); }

C source (3316.ins.c)



© Addison-Wesley Publishing Co. Inc.