paper6

.EQ
delim $$
define <- ?< "\h'-0.5m'" up 10 "\(em" down 10 ?
define gtorder ?"\z>\d\~\u"?
define EXIST ?"\z\-\d\z\-\r\-\d\v'0.2m'\(br\v'-0.2m'"?
define ALL ?"\o'V-'"?
define 0M '0~...~M-1'
define LH 'lo~...~hi'
define RR 'bold R'
define HH 'bold H'
define KK 'bold K'
define or '"\fBor\fI"~'
define and '"\fBand\fI"~'
define if '"\fBif\fI"~'
define then '"\fBthen\fI"~'
define else '"\fBelse\fI"~'
define repeat '"\fBrepeat\fI"~'
define until '"\fBuntil\fI"~'
define while '"\fBwhile\fI"~'
define do '"\fBdo\fI"~'
define case '"\fBcase\fI"~'
define end '"\fBend\fI"~'
define begin '"\fBbegin\fI"~'
define elseif '"\fBelseif\fI"~' 
define for '"\fBfor\fI"~'
define From '"\fBfrom\fI"~'
define To '"\fBto\fI"~'
define exit '"\fBexit\fI"~'
.EN
.ls 1	
.ce
COMPACT HASH TABLES USING BIDIRECTIONAL LINEAR PROBING
.sp 3
.ce
John G. Cleary
.ce
The University of Calgary, Alberta, Canada.
.sp 3
.sp 20
\u1\dAuthors Present Address: Man-Machine Systems Group, Department of
Computer Science, The University of Calgary, 2500 University Drive NW
Calgary, Canada T2N 1N4.
.sp
\u2\dThis research was supported by
the Natural Sciences and Engineering Research Council of Canada.
.sp 2
.ls 2
.bp
Index Terms --  Searching, hash storage, open addressing, 
bidirectional linear probing,
address calculation, information retrieval, scatter storage, 
performance analysis, memory compaction.
.bp
.pp
Abstract -- An algorithm is developed which reduces the memory 
requirements of hash tables.
This  is achieved by storing only
a  part of each key along with a few extra bits needed to ensure that
all keys are stored unambiguously.  The fraction of each key stored
decreases as the size of the hash table increases.  Significant reductions
in total memory usage can be achieved especially when the key size is not
much larger than the size of a memory index and when only a small amount
of data is stored with each key.
The algorithm is  based on 
bidirectional linear probing.
Search and insertion times are shown by simulation 
to be similar to those
for ordinary bidirectional linear probing.
.bp
.sh "1 Introduction"
.pp
The retrieval of a single item from among many others is a common problem
in computer science.  I am particularly concerned here with the case where 
the item is retrieved on the basis of a single label
or key attached to each entry and where the keys are not ordered in any
particular way.
There is a well known solution
to this problem in the form of hash tables.
Knuth [8], Knott [7] and Maurer and Lewis [11] provide good introductions to 
this subject.
.pp
An efficient version of hashing called
.ul
bidirectional linear probing 
(BLP),
was developed by Amble and Knuth [1].
As it forms the basis of what follows it is described in more detail in the
following section.  Section 3 shows how it can be modified so as to 
significantly reduce its memory requirements.  This is done by storing only
a small part of each key -- a few extra bits are needed to ensure 
that different keys, that look the same after truncation, are correctly
distinguished.
.pp
The execution time of this compact hashing algorithm is considered in
Section 4.  It is shown by simulation to be 
similar to  ordinary BLP
for both successful searches and insertion.  It is significantly
better for unsuccessful searches.  
.pp
A hashing scheme similar to compact hashing in that not all of the key is
stored has been proposed by Andreae [2] (Chapter 1).  However, his technique 
has a small but finite probability of retrieving an incorrect key.
Although compact hashing
is not based on this earlier technique it provided the impetus to
seek the current solution.
.pp
In hashing algorithms using an overflow area and a linked list of synonyms
or by variations of this using buckets (see Maurer and Lewis [11]) only the
remainder of each key need be stored.  This has been known since at least
1965 (Feldman and Low [6] and Knuth [8] sec. 6.4, exercise 13, p543).  
However, each entry (including the original hash location) requires a pointer
to the next overflow record.  This pointer will about the same size as the
reduction in the key size.  So, there is no net memory saving  over
open addressing techniques such as BLP.
.pp
Amongst the possible applications of compact hashing is the storage
of trees and TRIES without the use of pointers but still preserving
a $log N$ retrieval time. 
It is hoped to report on this application in more detail later.
.pp
Pascal versions of the algorithms described below are available
from the author.
.sh "2 Bidirectional linear probing."
.pp
I will now introduce the open addressing technique which forms the basis
of compact hashing.
The 
.ul
hash table
in which the keys will be stored is an array $T[ 0M ]$ .  I will
be concerned only with the the keys themselves as the 
items associated with each key do not 
significantly affect the algorithms.  In order to compute the location
for each key I will use two functions: $t$ which randomises the original
keys, and $h$ which computes a value in the range $0M$.  
.pp
Let $KK$ be the set of all possible keys and $HH$ be the set of all possible
transformed keys.  Then $t: KK -> HH$ is an invertible function.
This function is introduced
to ensure that the keys stored are  random and so, as a consequence,
the hashing
procedure has a satisfactory
average performance.  In what follows these transformed
keys will be used rather than the original keys.  For example, it is the 
transformed keys that are stored in $T$.  (-1 is used to indicate an unoccupied
location in $T$.)
.pp
$h: HH ->"{" 0M "}"$ and has the 
property that for
$H sub 1 ~, H sub 2 ~ "\(mo" HH$
$H sub 1 ~<=~ H sub 2~~ "\fBiff\fP"~~h(H sub 1 ) ~<=~ h(H sub 2 )$.  
As a consequence the keys will be mapped 
into the hash table in the same order as the values of their transformed
keys.  
This ordering is essential to the compaction attained later.
Suitable functions $t$ and $h$ have been extensively discussed 
(Carter and Wegman, [3]; Knott [7]; Lum, [9]; Lum, Yuen and Dodd, [10]).
These authors show that there are functions which almost always make
the distribution of transformed keys random.  I will not consider any
particular functions for $t$ although some examples of $h$ will be introduced
later.
.pp
To retrieve a key, $K$, from the hash table the transformed key and the 
hash location are first computed.  If the (transformed) key stored at the
hash location is greater than $t(K)$ then the table is searched upward 
until one of three things happen.  Either an empty location will be found,
$T[j]=-1$, or the sought key will be found, $T[j]=t(K)$, or a key greater
than the sought key will be found, $T[j]>t(K)$.  If the first key examined
is less than $t(K)$ then an analogous search is done down the hash table.
The search is successful if the sought key is found, that is
if the last location examined is equal to $t(K)$, and is unsuccessful
otherwise.  (See Amble and Knuth [1] for the details of this algorithm).
.pp
For a given set of keys there are many ways that they can be arranged in $T$
so that the search algorithm above will  still work correctly.
There is thus
freedom, when designing an algorithm to insert new keys, to choose different 
strategies for positioning the keys.
There are two conditions that must be satisfied when a new key is inserted.
One is that all keys in the memory must remain in ascending order
and the other is that there must be no empty locations between the original hash
location of any key and its actual storage position.  These imply that all
keys sharing the same initial hash location must form a single unbroken group.
.pp
Within these constraints one would like to insert a new key so as to minimise 
later retrieval times and the time to do the insertion itself.  Intuitively
keys which share the same initial hash location should be centered around that
initial address.  There are two ways of inserting keys which cause little
disturbance to the memory.  One is to find the position where the key should
be placed according to its ordering and then to create a gap for it by
moving 
.ul
up 
all entries from this position up to the next empty location.  The second way is
symmetric to this and creates a gap by moving entries 
.ul
down 
one location.
The insertion algorithm given by  Amble and Knuth [1] chooses which of these
two moves to make using a strategy which is  guaranteed to minimise the number
of locations in $T$ which are examined during later successful or unsuccessful
searches, although it is not guaranteed to minimise the insertion time itself.
.pp
One  consequence of this insertion strategy is that sometimes it is necessary
to move entries below 0 and above $M$ in the array $T$.  One solution to this
would be to make the array circular and move entries from 0 to $M-1$ and
vice versa.  However, following Amble and Knuth [1], I will instead extend
the array $T$ and other arrays to be defined later at their top and bottom.
This gives 'breathing room' for the array to expand.  An extra 20 entries
at the top and bottom were found to be quite sufficient for all
the simulation runs reported in Section 4.  Accordingly I will define
$lo ~=~-20$ and $hi~=~M+19$ and define the array $T$ over the range
$lo$ to $hi$.
.sh "3 Compact Hashing Using Bidirectional Linear Probing"
.pp
I will now show that the memory required to store the keys in BLP can be
significantly reduced.  First consider the case when
the number of possible keys in $KK$ is less than $M$, then every possible key
can be assigned its own location in $T$ without possibility of collision.
In this case $T$ degenerates to an ordinary indexed array and the keys need
never be stored.  At worst a single bit might be needed to say whether
a particular key has been stored or not.  This raises the question of whether
it is necessary to hold the entire key in memory if the key space $KK$ is slightly
larger than $M$.  For example if $KK$ were, say, four times larger than $M$
then it might be possible to hold only two bits of the key rather than the entire
key.  The reasoning here is that the main function of the stored keys is to
ensure that entries which collide at the same location can be correctly
separated.
Provided $h$ is suitably chosen at most four keys can be mapped to a 
single location.  The two bits might then be sufficient to store four
different values for these four keys.  It is in fact 
possible to realise this
reduction in stored key size although a fixed amount of extra information 
is needed
at each location in order to correctly handle collisions.
.pp
So that I can talk about the part of the key which is in excess of the
address space I will now introduce a 
.ul
remainder function
$r$.  $r$ maps from the transformed keys $HH$ to a set of remainders 
$RR~==~"{"0,~1,~2,~...,~Rm-1"}"$.  
It  is these remainders that will be stored in lieu
of the transformed keys.  
The essential property
of $r$ is that $r(H)$ and $h(H)$ together are sufficient to uniquely 
determine $H$.  
.pp
.ne 9
Formally,
.sp
	$RR ~~==~~ "{"0,~1,~2,~...,~Rm-1"}"$
.sp
	$r: HH -> RR$
.sp
and	$h( H sub 1 )~=~h( H sub 2 )~and~r( H sub 1 )~=~r( H sub 2 )
~~ "\fBiff\fP" ~~ H sub 1 ~~=~~ H sub 2$ .
.sp
For a given function $h$ there are usually many possible functions $r$.
One particularly simple pair of functions, referred to by Maurer and Lewis [10]
as the 
.ul
division method, 
is $h(H)~~=~~ left floor^ H/Rm right floor$ and
$r(H)~~=~~ H~ "\fBmod\fP"~Rm$ . 
.sp
When $r$ is defined as above and $Rm$ is between $2 sup d$ and $2 sup d+1$ 
the number of bits needed to 
specify a remainder is the number of bits in the key less $d$.
.pp
Consider a new array
$R [ LH ]$ into which the remainders will be stored.   
In what follows $R$ will be kept in place of $T$ but it will be useful to
talk about $T$ as if it were still there.  $R$ and the additional arrays to
be introduced shortly specify just the information in $T$, albeit
more compactly.  Each value $R [i]$ will hold the value $r(T[i])$ with the
exception that when $T[i]$ is $-1$ (marking an empty location) then $R[i]$
is also set to $-1$.  If
there have been no collisions then each $R[i]$ paired with the value $i$
unambiguously gives the transformed key that would have been stored in $T[i]$.
However, if there have been collisions it is not possible
to tell if a value of $R[i]$ is at its home location or if it has been moved
from, say, $i-1$ and corresponds to a key, $H$, where $r(H)~=~ R[i]$ and $h(H)~=~i-1$.
If there were some way to locate for each $R[i]$ where it was originally 
hashed then the original keys could all be unambiguously determined.
This can be done by maintaining two extra arrays of bits, the virgin array $V$,
and the change array $C$.
.pp
The virgin array
$V[ LH ]$ marks those 
locations which have never been hashed to.  That is, $V[i]$ has a value of $1$
stored if any of the stored keys in the hash table has $i$ as its hash
address, and $0$ otherwise.  $V$ is maintained by initialising it to $0$
and thereafter setting $V[h(H)] <-~1$ whenever a key $H$ is inserted in the
memory.  The virginity of a location is unaffected by the move operations
during insertion.
The $V$ array is similar to the array of pass bits recommended in [1].
.pp
To understand the change array $C[ LH ]$ it is necessary to look more closely
at the distribution of values of $R[i]$.  These remainders can be grouped 
according to whether or not they share the same original hash address.
Also recall that the hash table, as in BLP, is ordered, so,
all the remainders in a particular group will occur at 
consecutive locations. 
The change bits $C[i]$ are used to delimit the 
boundaries of these groups.  This is done by marking the first remainder
(the one stored at the lowest address) of each group with a $1$.  All other 
members of a group have $C[i]=0$.  To simplify the search and insertion
algorithms it is also convenient to set $C[i]$ to 1 for all locations
which are empty ($R[i]=-1$).
Thus we have the formal definitions of the
values of $V$ and $C$ in terms of the now notional array $T$ (the array
$A$ is described later):
.bp
.nf
.ls 1
.ta 0.5i +0.75i +0.9i
		\(lt\|$r(T[i])$	$T[i] != -1$
	$R[i]~~==~~$	\(lk\|
		\(lb\|$-1$ 	$T[i]=-1$
.sp
		\(lt\|$1	EXIST~ j~h(T[j])=i$
	$V[i]~~==~~$	\(lk\|
		\(lb\|$0$	otherwise
.sp
		\(lt\|$1	T[i] != T[i-1]~ roman or ~T[i]=-1$
	$C[i]~~==~~$	\(lk\|
		\(lb\|$0$	otherwise
.sp 2
		\(lt\|$a(i)	-Na <= a(i) <= Na$
	$A[i]~~==~~$	\(lk\|
		\(lb\|$inf$	otherwise
.sp
	where
.sp
		$Na ~>=~ 0$
.br
		$a(i)~==~ sum from j=lo to i |C[j]=1~"and"~R[j] != -1|~-~
sum from j=lo to i V[j]$
.fi
.ls 2
.ta 0.5i +0.5i +0.5i +0.5i +0.5i +0.5i +0.5i +0.5i +0.5i +0.5i +0.5i 
.rh "Searching.
For every group of remainders there will somewhere be a $V$ bit equal to $1$ 
and a $C$
bit  at a non-empty location equal to $1$.  That is,
for every $V$ bit which is $1$ there is a corresponding $C$ bit 
which is also $1$.
.FC "Fig. 1."
This correspondence is indicated in 
Fig. 1 by the dotted lines.  When searching for a key $H$ in the table
the location $h(H)$ is examined.  If the $V$ bit is $0$ then the search 
can stop
immediately.  Otherwise a search is made for the corresponding $C$ bit 
which is $1$.  To do this a search is made down (or up) the hash table until
an empty location is found.  The number of $V$ bits which are $1$
from $h(H)$ to this empty
location are counted.  The correct $C$ bit is then found by counting back
up (or down) the array from the empty location
for the same number of $C$ bits which are $1$.  Details of this algorithm
follow.
.ls 1
.sp 
.nf
.ta 1.5c +1.35c +1.35c +1.35c +1.35c +1.35c +1.35c +1.35c +1.35c
.sp
.ne 2
Step 1:	{initialise variables}
	$H <-~ t(K);~~j <-~ h(H);~~rem <-~ r(H);~i <-~ j;~~count <-~ 0;$
	{check virgin bit}
	$if~ V[j]=0~then$ {search unsuccessful} $exit ;$
.sp
.ne 3
Step 2:	{find first empty location down the table}
	$while ~R[i] != -1~do~~begin~~count <-~count - V[i];~i <-~ i-1 ~end ;$
.sp
.ne 4
Step 3:	{search back to find uppermost member of relevant group}
	$while count < 0 ~do~begin~ i <-~i+1;~count <-~count +C[i];~end ;$
	{$i$ now points at the first(lowest) member of the group associated}
	{with the original location $j$}
.sp
.ne 6
Step 4:	{search group associated with $j$}
	$while R[i+1] <= rem ~and C[i+1]=0~do i <-~i+1 ;$
	{check last location to see if key found}
	$if R[i]=rem~ mark then$ {search successful}
	$lineup            else$ {search unsuccessful} ;
.sp 2
.ls 2
.fi
.pp
An example search is illustrated in Fig. 1 for the key 75.
For this example $h$ is computed by dividing by 10 and rounding down, 
$r$ is computed by taking the remainder modulo 10.  
.br
Step 1: The initial hash location
for 75 is 7 and its remainder is 5.  The $V$ bit at location 7 is 1 so the 
search continues.
.br
Step 2:
The first empty location found by searching down the table is at location 3.
There are three $V$ bits with a value of 1 between 7 and 3 at locations 
4, 6 and 7.
.br
Step 3:
Counting back from location 3 three $C$ bits are 1 at locations 4, 5 and 8.
So the $C$ bit at location 8 corresponds to the $V$ bit at the 
original hash location 7.
.br
Step 4:
The group of remainders which share the same initial location 7 can then be 
found in locations 8 and 9.  Thus the remainder 5 at location 8 can be
unambiguously associated with the original key 75 and so it can be
concluded that the information associated with the key 75 is present 
at location 8 in the memory.
.pp
It still remains to specify the update
algorithm and to address some issues of efficiency.  To this end a third
array will be added.
.rh "Speeding up search."
It was found during the simulations reported in Section 4 
that the most time consuming element of this search
is step 2 when the table is scanned for an empty location.  The essential
role played by the empty locations here is to provide a synchronisation
between the 1 bits in the $V$ and $C$ arrays. 
This lengthy search could be eliminated by maintaining two additional arrays,
$#C[ LH ]$ and $#V[ LH ]$, which count from the start of memory the number of 
$C$ and $V$ bits which are 1.  That is:
.br
	$#C[i] ~==~ sum from j=lo to i |C[j]=1~and~R[j] != -1 |$
.br
and	$#V[i] ~==~ sum from j=lo to i V[j]$ .
.br
.pp
In order to find the $C$ bit corresponding to some $V[i]=1$ then all that 
is necessary is to compute the difference $count <-~#C[i]-#V[i]$.  
If $count$ is zero then the remainder stored at $i$ was originally
hashed there and has not been moved.  If $count$ is positive then it is 
necessary to scan down the memory until $'count'$ $C$ bits equal to 1 have been 
found.  If $count$ is negative then it is necessary to scan up the memory
until $'-count'$ $C$ bits which are 1 have been found.  Fig. 2 shows some
examples of the various situations which can arise.
.FC "Fig. 2."
.pp
In fact, it is not necessary to store $#C$ and $#V$ explicitly, it is 
sufficient merely to store the differences $#C[i]-#V[i]$.  To do this the
.ul
At home
array, $A[ LH ]$, will be used.
.pp
At this point it might seem that all earlier gains have been lost because
in the most extreme case $#C[i]-#V[i]~=~M$.  To store a value of $A$
will require as many bits as a memory index -- precisely the gain made by
storing remainders rather than keys!\   However, all is not lost.  The values 
of $A$ tend to cluster closely about 0.  Simulation
shows that a hash memory which is 95% full has 99% of the $A$ values
in the range -15 to +15.  Therefore the following strategy can be
adopted.  Assign a fixed number of bits for storing each value of $A$, say
5 bits.  Use these bits to represent the 31 values -15 to +15 and a 32nd
value for $inf$.  Then anywhere that $#C[i]-#V[i]~<~-15~"or"~>+15$ assign $inf$
to $A[i]$ otherwise assign the true difference.
.pp
When searching for a key a scan can now be done down (or up) the memory
until a location $i$ where $A[i] != inf$ is found.  (At worst this will occur
at the first unoccupied location where $A[i]$ will be zero.)\  From there
a count can be made up (or down) the memory for the appropriate number of
$C$ bits which are 1.
.pp
In the detailed algorithm given below some differences from the simpler search
can be noted.
In step 3, $count$ can be both
positive and negative.  Therefore code is included to scan both up and down
the memory as appropriate.  At the end of step 3, $i$ can be pointing at any
member of the group associated with the original hash location.  (Above
$i$ was always left pointing at the lowest member of the 
group.)\    Therefore code is included for scanning both up and down the
members of the group.  In order to prevent redundant checking of locations
by this code a flag $direction$ is used.  It can take on three values
depending on the direction of the memory scan: $"up"$, $"down"$, and $here$
(no further searching need be done).
.ls 1
.sp 
.nf
.ta 1.5c +1.45c +1.45c +1.35c +1.35c +1.35c +1.35c +1.35c +1.35c
.sp
.ne 2
{Search using at-home count}
Step 1:	{initialise variables}
	$H <-~ t(K);~~j <-~ h(H);~~rem <-~ r(H);~~i <-~ j;~~count <-~ 0;$
	{check virgin bit}
	$if~ V[j]=0~then$ {search unsuccessful} $exit ;$
.sp
.ne 5
Step 2:	{find first well defined $A$ value down the memory}
	$while ~A[i] = inf~do~begin~count <-~count - V[i];~i <-~i-1 ~end ;$
	$count <-~count +A[i];$
.sp
.ne 16
Step 3:	{Search either up or down until a member of sought group is found}
	{Also ensure $direction$ is set for Step 4.}
	$if count < 0 ~then$
		$direction <-~"up";$
		$repeat i <-~i+1;~count <-~count +C[i]~ until count = 0 ;$
		$if R[i] ~>=~ rem ~then direction <-~here;$
	$else if count > 0 ~then$
		$direction <-~"down";$
		$repeat ~count <-~count -C[i];~i <-~i-1~ until count = 0 ;$
		$if R[i] ~<=~ rem ~then direction <-~here;$
	$else${$count = 0$}
		$if R[i] > rem ~then direction <-~"down"$
		$else if R[i] < rem ~then direction <-~"up"$
		$else direction <-~here ;$
.sp
.ne 16
Step 4:	{search group associated with $j$}
	$case direction~ "\fBof\fP"$
	$here:	;${do nothing}
	$"down":	repeat	if C[i] = 1 ~then direction <-~here$
			$else$
			$begin$
				$i <-~i-1;$
				$if R[i] ~<=~ rem ~then direction <-~here;$
			$end$
		$until direction = here ;$
	$"up":	repeat	if C[i+1] = 1 ~then direction <-~here$
			$else$
			$begin$
				$i <-~i+1;$
				$if R[i] ~>=~ rem ~then direction <-~here;$
			$end$
		$until direction = here ;$
	$end ;$
.sp
.ne 4
Step 5:	{check last location to see if key found}
	$if R[i]=rem~ mark then$ {search successful}
	$lineup            else$ {search unsuccessful} ;
.sp 2
.ls 2
.fi
.FC "Fig. 3."
.pp
Fig. 3, gives an example of this searching algorithm.
The same memory and key (75) as in Fig. 1 are used.  For the
purposes of the example each $A$ value is allocated one bit.  This allows 
only two values 0 and $inf$.  The search proceeds as follows:
.br
Step 1: The initial hash location
for 75 is 7 and its remainder is 5.  The $V$ bit at location 7 is 1 so the 
search continues.
.br
Step 2: 
The first $A$ value not equal to $inf$ found by searching down the table 
is at location 6.
There is one $V$ bit with a value of 1 between 7 and 6, at location 7.
$count$ is then set to $A[6]+1~=~1$.  So on the next step one $C$
bit will be sought.
.br
Step 3:
Counting back up from 6 the first $C$ bit equal to 1 is at location 8.
So the $C$ bit at location 8 corresponds to the $V$ bit at the 
original hash location 7.
.br
Step 4:
The group of remainders which share the same initial location 7 can then be 
found in locations 8 and 9.  The remainder 5 at location 8 can thus be
unambiguously associated with the original key 75 and it can be
concluded that the information associated with the key 75 is present 
at location 8 in the memory.
.rh "Insertion."
Insertion of a new key into the memory requires three distinct steps:
first locating whereabouts in the memory the key is to be placed;
second deciding how the memory is to be rearranged to make room for the new
key; and third moving the remainders whilst correctly preserving the
$A$ and $C$ values.  (The $V$ bits remain fixed during the move.)\  
The initial search can be done as explained above with the small addition that
the correct insertion point must still be located when the key is not present.
The second and third steps follow the algorithm in Amble and Knuth [1]
with the addition that the values of the $A$ array must be re-calculated
over the shifted memory locations and the $C$ but not the $V$ bits must
be moved with the keys.  
Details of this can be found in an earlier draft of this paper, [4].
.sh "4 Performance"
.pp
Now I consider how long these algorithms will take to run.  The measure of 
run time that I will use is the number of 
.ul
probes
that each algorithm makes, that is, the number of times locations in the 
hash table are examined or updated.  
CPU time measures were taken as well and correlate well with the empirical 
counts of probes given below.
.FC "Table I"
.FC "Table II"
.rh "Searching."  
Tables I and II list the results of simulations
for successful and unsuccessful searches respectively.  Results are tabulated
for ordinary BLP and for compact hashing with  
different memory loadings and different sizes for
the $A$ field.  If the number of keys stored
in the memory is $N$ then the memory loading is measured by 
$alpha ~==~N/M$, the fraction of locations in the memory which are full. 
Values of
Na were chosen to correspond to $A$ field lengths of 1, 2, 3,
4, and 5 bits, that is for Na equal to 0, 1, 3, 7, and 15 respectively,
and also for the case where no $A$ field was used.
Increasing the size of the $A$ field beyond 5 bits had no effect at
the memory loadings investigated.  So Na equal to 15 is effectively the
same as an unbounded size for the $A$ values.  
.pp
The insertion procedure is 
guaranteed to be optimum only for BLP, not for compact hashing.  If none
of the values in $A$ is $inf$ then the sequence of locations examined by
compact
hashing is the same as for BLP and so the strategy will still be optimum.
(This is easily seen by noting that in compact hashing
$A[h(t(K))]$ determines the direction
of the search depending on whether it is positive or negative.  During the 
subsequent search no
locations past the sought key will be probed.  This is exactly the same
probing behaviour as in BLP.)\ 
However, if no $A$ array is being used or if some values of $A$ are $inf$
then extra locations need to be probed to find an empty location or one which
is not equal to $inf$.
.pp
As expected the figures in Table I show that for Na at 15 and using optimum
insertion the probes for a successful search are almost the same as for BLP.
(The small differences are accounted for by statistical fluctuations
in the simulation results.)\   
.pp 
As Na is decreased the number of probes needed for searching increases.
This
reflects the greater distances that must be traversed to find a value of 
$A$ not equal to $inf$.  It is notable however that even a single bit allocated
to the $A$ fields dramatically improves the performance.  Even at a
memory density of 0.95 some 25% of non-empty locations have $A$ values of 0.
.pp
The pattern for unsuccessful searches is broadly the same as sketched above
for successful searches except that in general unsuccessful searches
are quicker than successful ones.  This is a result of the $V$ bits
which allow many unsuccessful searches to be stopped after a single probe. 
For example even at the maximum possible memory density of 1 some 36% of
$V$ bits are zero.  This results in compact hashing being faster than
the reported values for ordinary BLP.  
However, unsuccessful BLP searches could be
improved to a similar degree by incorporating $V$ bits.
.FC "Table III"
.rh "Insertion."
The probes to insert a new key can be broken down into three components,
those needed to locate the position where the key is to be inserted,
those to decide the direction of movement 
and those to effect the movement of the memory.
The first of these will be slightly larger than
a successful search and so the results of Table I have not been repeated.
The second two are independent of Na as they are dependent only on
the lengths of blocks of adjacent non-empty locations.  The values
for these Na independent components are listed in Table III.
In most cases
this Na independent component is much larger than the search component.
The exception occurs 
where no $A$ values are being used, when the two components
are comparable.
.pp
Cleary [5] examines a random insertion strategy for ordinary BLP
where blocks of entries in the hash table are moved in a randomly chosen
direction
to accomodate a
new entry rather than in the optimum way described by 
Amble and Knuth [1].
It is shown that this strategy can
improve insertion times by a factor of 4 at the expense of small degradations
(at most 15%) in retrieval times.  These
results are shown by simulation to extend to compact hashing.  
Indeed for small values of
Na the optimum and random strategies show no significant differences in
retrieval times.
.rh "Analytic approximation."
While analytic results are not available for the number of probes 
needed for retrieval or insertion an
approximation can be developed for some of the cases.  It is shown by
Amble and Knuth [1] and Knuth [8] (problem 6.4-47) that the average
length of a block of consecutive non-empty locations when using
the optimum insertion strategy is approximately
$(1- alpha ) sup -2 ~-~1$.  
Let this block length be $L$.  
.pp
Consider the case of a successful search when no $A$ field is used.
A successful scan of a block from an arbitrary
position to the end takes on average $L/2~+~1/2$ probes.  
During the initial scan down the memory in the simulations the initial check of the
$V$ bit and the final empty location examined were each counted as a single probe.
This gives a total of $L/2~+~5/2$ probes for the initial scan down. (This is not
exact because there will be a correlation between the position 
of a key's home location within a block 
and the number of keys hashing to that home location).
The scan back up a block will take $L/2~+1/2$ probes (exact for a successful search).
This gives $(1- alpha ) sup -2 +2$ for the expected
number of probes during a successful search.  These values are listed in Table I
and are consistently low by about 10%.
.pp
For an unsuccessful search with no $A$ field the initial scan down the 
memory will take $L/2~+5/2$ probes as above (again this will not be exact because
the probability of a $V$ bit being one will be correlated with the 
size of a block and its
position within the block).
An unsuccessful scan of a block takes $L/2~+~1/2$ probes.  (This assumes
the keys in the block are distributed uniformly.  
This gives the following probabilities that the search will stop at a 
particular location in the block: the first location, $1/2L$; locations 2 
through $L$, $1/L$; the empty $(L+1)$st location, $1/~2L$.
This will not be true for compact hashing because the probability of stopping at a key
which shares its home location with a large number of other keys will be smaller than
for one which shares it with few others.)\ \ Summing these two terms gives $L~+~7/2$
probes.
Given that the keys are distributed randomly there is a probability of 
$e sup {- alpha}$ that a given $V$ bit will be zero.  So the expected number 
of probes overall for an unsuccessful search is 
$e sup {- alpha}~+~(1-e sup {- alpha}) cdot ((1- alpha ) sup -2 + 5/2)$.
These values are listed in Table II and are consistently low by about 5%.
.pp
Considering only the insertion component which is independent of Na then
it is possible to derive an expression for the number of probes.
There is an initial
scan to move the memory down and insert the new key which will scan about half 
the block ($L/2~+~5/2$ probes) 
and a subsequent scan back up of the entire block ($L~+~1$ probes).  
Empirically the probability
that the entire block will subsequently be moved back up is a half which gives
an expected $1/2(L~+~1)$ probes.
Summing these three contributions gives $2(1- alpha ) sup -2 ~+~2$
as the expected number of probes for an insertion (excluding the search time).
Values for this expression are tabulated  in Table III, they are in good 
agreement with the empirical values.
.sh "Acknowledgements"
.pp
I would like to thank Ian Witten for careful checking of a draft version.
Also John Andreae for discussions which showed that something like compact
hashing might be possible.
.sh "References"
.ls 1
.LB "[6]    "
.sp
.NI "[1]  "
[1]\ \ O.\ Amble and D.\ E.\ Knuth, "Ordered Hash Tables,"
.ul
Computer Journal,
vol. 17, pp135-142, 1974.
.sp
.NI "[1]  "
[2]\ \ J.\ H.\ Andreae,
.ul
Thinking with the teachable machine.
London: Academic Press, 1977.
.sp
.NI "[1]  "
[3]\ \ J.\ L.\ Carter and M.\ N.\ Wegman, "Universal classes of hash 
functions,"
.ul
J. Computer System Sci.,
vol. 18, pp143-154, 1979.
.sp
.NI "[2]  "
[4]\ \ J.\ G.\ Cleary, "Compact hash tables,"
Research Report, 82/100/19,
Department of Computer Science, University of Calgary, July 1982.
.sp
.NI "[3]  "
[5]\ \ J.\ G.\ Cleary, "Random insertion for bidirectional linear probing
can be better than optimum," 
Research Report, 82/105/24,
Department of Computer Science, University of Calgary, September 1982.
.sp
.NI "[5]  "
[6]\ \ J. A. Feldman and J. R. Low, "Comment on Brent's Scatter Storage 
Algorithm,"
.ul
CACM,
vol. 16, p703, 1973.
.sp
.NI "[7]  "
[7]\ \ G. D. Knott, "Hashing functions,"
.ul
The Computer Journal,
vol. 18, pp265-278, 1975.
.sp
.NI "[7]  "
[8]\ \ D.\ E.\ Knuth, 
.ul
The art of computer programming:Sorting and searching.
Vol III.
Reading, Massachusetts: Addison Wesley, 1973.
.sp
.NI "[8]  "
[9]\ \ V.\ Y.\ Lum, "General performance analysis of key-to-address 
transformation methods using an abstract file concept,"
.ul
CACM,
vol. 16, pp603-612, 1973.
.sp
.NI "[12]  "
[10]\ \ V.\ Y.\ Lum,\ P.\ S.\ T.\ Yuen and M.\ Dodd, "Key-to-address
transformation techniques,"
.ul
CACM,
vol. 14, pp228-239, 1971.
.sp
.NI "[13]  "
[11]\ \ W. D. Maurer and T. G. Lewis, "Hash table methods,"
.ul
Comp. Surveys,
vol. 7, pp5-19, 1975.
.ls 2
.in 0
.bp 0
\&\ 
.RF
.ta 0.5i +0.75i +0.75i +0.75i +0.75i +0.75i
.nf

	$i	T[i]	R[i]	V[i]	C[i]$
	\l'3.5i'
.br

	12	\0\ -1	\ -1	0	1
.br
	11	101	\01	0	1
.br
	10	\087	\07	1	1
.br
	\09	\076	\06	0	0
.br
	\08	\075	\05	1	1
.br
	\07	\067	\07	1	0   
.br
	\06	\066	\06	1	0
.br
	\05	\065	\05	0	1
.br
	\04	\041	\01	1	1
.br
	\03	\0\ -1	\ -1	0	1
.br
	\02	\019	\09	0	0
.br
	\01	\018	\08	1	0
.br
	\00	\016	\06	0	1
.br
					     Step 1 Step 2 Step 3 Step 4
.br

	$h(H)~=~ left floor^ H/10 right floor$
.br

	$r(H)~=~ H~ roman mod ~10$
.br

.FG ""

.bp 0
\&\ 
.RF
.nf
.ta 0.5i +0.75i +0.75i +0.75i +0.75i
	$count~=~A[i]~=~#C[i]-#V[i]$
.sp
	$count = 0$			$count = 0$
	$C$	$V$		$C$	$V$
	0\|\(rt	1		0\|\(rt	1
	0\|\(rk	0		0\|\(rk	1$<-~i$
	1\|\(rb	1$<-~i$		1\|\(rb	0
.sp
	$count =1>0$		$count = 2 > 0$
	$C$	$V$		$C$	$V$
	0	1$<-~i$		0	1$<-~i$
	1	0		1	0
	0\|\(rt	1		1	1
	0\|\(rk	0		0\|\(rt	0
	1\|\(rb	0		0\|\(rk	0
				1\|\(rb	0
.sp
	$count =-1<0$
	$C$	$V$
	0\|\(rt	0			\|\(rt
	0\|\(rk	0			\|\(rk\ \ Group of entries which hash to 
	1\|\(rb	0			\|\(rb\ \ location i
	0	0
	1	1$<-~i$			\ \ \ Corresponding $C$ and $V$ bits
.FG ""
.bp 0
\&\ 
.RF
.ta 0.5i +0.5i +0.5i +0.5i +0.5i +0.9i +0.6i +0.4i
$i	R[i]	V[i]	C[i]	#V[i]	#C[i]~~#C[i]-#V[i]	A[i]$
.br
\l'4.5i'
.br
12	\ -1	0	1	6	6	\00	0
.br
11	\01	0	1	6	6	\00	0
.br
10	\07	1	1	6	5	\ -1	$inf$
.br
\09	\06	0	0	5	4	\ -1	$inf$
.br
\08	\05	1	1	5	4	\ -1	$inf$
.br
\07	\07	1	0	4	3	\ -1	$inf$
.br
\06	\06	1	0	3	3	\00	0
.br
\05	\05	0	1	2	3	\01	$inf$
.br
\04	\01	1	1	2	2	\00	0
.br
\03	\ -1	0	1	1	1	\00	0
.br
\02	\09	0	0	1	1	\00	0
.br
\01	\08	1	0	1	1	\00	0
.br
\00	\06	0	1	0	1	\01	$inf$
.br
								Step 1 Step 2 Step 3 Step 4
.sp 
Note: 	Only one bit has been allowed for the values of $A$. 
.br
	So the only two possible values are 0 and $inf$.

.FG ""
.bp 0
\&\ 
.RF
.ta 1.5i +0.5i +0.5i +0.5i +0.5i +0.5i +0.5i +0.5i +0.5i
.ce
Successful Search
	\l'4i'

	$alpha$	\0.25	\0.5	\0.75	\0.8	\0.85	\0.9	\0.95
	\l'4i'
	
	$BLP sup 1$	\0\01.1	\0\01.3	\0\01.7	\0\02.0	\0\02.3	\0\02.9	\0\04.2
	
	Na
	15	\0\01.1	\0\01.3	\0\01.7	\0\01.9	\0\02.2	\0\02.8	\0\04.6
	\07	\0\01.1	\0\01.3	\0\01.7	\0\01.9	\0\02.2	\0\02.8	\0\09.7
	\03	\0\01.1	\0\01.3	\0\01.7	\0\01.9	\0\02.4	\0\04.2	\025
	\01	\0\01.1	\0\01.3	\0\02.0	\0\02.5	\0\04.1	\0\08.8	\045
	\00	\0\01.1	\0\01.5	\0\03.3	\0\04.9	\0\07.9	\015	\061
	\0-	\0\04.2	\0\07.1	\020	\030	\049	110	370
	\0*	\0\03.77	\0\06.00	\018.0	\027.0	\046.4	102	402

		$\& sup 1~$Taken from Amble and Knuth [1].
		- No $A$ field used.
		* Analytic approximation to line above.
.FG ""
.bp 0
\&
.RF
.ta 1.5i +0.5i +0.5i +0.5i +0.5i +0.5i +0.5i +0.5i +0.5i
.ce
Unsuccessful Search
	\l'4i'

	$alpha$	\0.25	\0.5	\0.75	\0.8	\0.85	\0.9	\0.95
	\l'4i'

	$BLP sup 1$	\0\01.3	\0\01.5	\0\02.1	\0\02.3	\0\02.6	\0\03.1	\0\04.4

	Na
	15	\0\01.2	\0\01.4	\0\01.8	\0\01.9	\0\02.1	\0\02.4	\0\03.5
	\07	\0\01.2	\0\01.4	\0\01.8	\0\01.9	\0\02.1	\0\02.4	\0\09.7
	\03	\0\01.2	\0\01.4	\0\01.8	\0\01.9	\0\02.2	\0\03.3	\015
	\01	\0\01.2	\0\01.4	\0\01.9	\0\02.2	\0\03.2	\0\06.0	\028
	\00	\0\01.2	\0\01.5	\0\02.6	\0\03.4	\0\05.3	\0\09.9	\036
	\0-	\0\01.7	\0\03.4	\011	\016	\028	\064	220
	\0*	\0\01.72	\0\03.16	\010.2	\015.6	\027.3	\061.2	247

		$\& sup 1~$Taken from Amble and Knuth [1].
		- No $A$ field used.
		* Analytic approximation to line above.
.FG ""
.bp 0
\&
.RF
.ta 1.5i +0.5i +0.5i +0.5i +0.5i +0.5i +0.5i +0.5i +0.5i
	\l'4i'

	$alpha$	\0.25	\0.5	\0.75	\0.8	\0.85	\0.9	\0.95
	\l'4i'

		\0\04.3	\0\08.8	\032	\049	\086	200	700
	*	\0\04.56	\0\09.00	\033.0	\051.0	\089.9\
	201	801

	* Analytic approximation to line above
.FG ""
.bp 0
\&
.ce 
List of Figures
.sp 2
Fig. 1. Example of compact hash memory and search for key.
.sp 2
Fig. 2. Examples showing different values of $#C[i]-#V[i]$.
.sp 2
Fig. 3. Example of calculation and use of array $A$.
.sp 2
.ce
List of Tables
.sp 2
Table I. Average number of probes during a successful search.
.sp 2
Table II. Average number of probes during an unsuccessful search.
.sp 2
Table III. Average number of probes to move block of memory.
.sp 2