approximation can be developed for some of the cases.  It is shown byAmble and Knuth [1] and Knuth [8] (problem 6.4-47) that the averagelength of a block of consecutive non-empty locations when usingthe optimum insertion strategy is approximately$(1- alpha ) sup -2 ~-~1$.  Let this block length be $L$.  .ppConsider the case of a successful search when no $A$ field is used.A successful scan of a block from an arbitraryposition 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 notexact 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 expectednumber of probes during a successful search.  These values are listed in Table Iand are consistently low by about 10%..ppFor 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 becausethe probability of a $V$ bit being one will be correlated with the size of a block and itsposition within the block).An unsuccessful scan of a block takes $L/2~+~1/2$ probes.  (This assumesthe 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 keywhich shares its home location with a large number of other keys will be smaller thanfor 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%..ppConsidering only the insertion component which is independent of Na thenit is possible to derive an expression for the number of probes.There is an initialscan 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 probabilitythat the entire block will subsequently be moved back up is a half which givesan 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".ppI would like to thank Ian Witten for careful checking of a draft version.Also John Andreae for discussions which showed that something like compacthashing might be possible..sh "References".ls 1.LB "[6]    ".sp.NI "[1]  "[1]\ \ O.\ Amble and D.\ E.\ Knuth, "Ordered Hash Tables,".ulComputer Journal,vol. 17, pp135-142, 1974..sp.NI "[1]  "[2]\ \ J.\ H.\ Andreae,.ulThinking with the teachable machine.London: Academic Press, 1977..sp.NI "[1]  "[3]\ \ J.\ L.\ Carter and M.\ N.\ Wegman, "Universal classes of hash functions,".ulJ. 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 probingcan 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,".ulCACM,vol. 16, p703, 1973..sp.NI "[7]  "[7]\ \ G. D. Knott, "Hashing functions,".ulThe Computer Journal,vol. 18, pp265-278, 1975..sp.NI "[7]  "[8]\ \ D.\ E.\ Knuth, .ulThe 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,".ulCACM,vol. 16, pp603-612, 1973..sp.NI "[12]  "[10]\ \ V.\ Y.\ Lum,\ P.\ S.\ T.\ Yuen and M.\ Dodd, "Key-to-addresstransformation techniques,".ulCACM,vol. 14, pp228-239, 1971..sp.NI "[13]  "[11]\ \ W. D. Maurer and T. G. Lewis, "Hash table methods,".ulComp. 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'.br12	\ -1	0	1	6	6	\00	0.br11	\01	0	1	6	6	\00	0.br10	\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.ceSuccessful 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.ceUnsuccessful 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 2Fig. 1. Example of compact hash memory and search for key..sp 2Fig. 2. Examples showing different values of $#C[i]-#V[i]$..sp 2Fig. 3. Example of calculation and use of array $A$..sp 2.ceList of Tables.sp 2Table I. Average number of probes during a successful search..sp 2Table II. Average number of probes during an unsuccessful search..sp 2Table III. Average number of probes to move block of memory..sp 2