Content-Type: text/html Collision Resolution Tradeoffs

LISCH Deletion

Now we have deleted every eighth record, and added half of them back into the table.

With a Packing Factor of 81%, it took 75 total probes to retrieve all 43 entries.

This gives us an average of 1.744 probes. Which is within 11.378% of the mean number of probes (1.566) given in the text.

The deletion and insertion increased primary clustering, and brought the numbers closer to what is expected for LISCH. Once again, I found the choice of key generation algorithm can greatly affect the outcome.

A slight difference can be attributed to the 1% difference in packing factor between the text's 80% packing factor versus our 81% packing factor.

Contents of stored datafile:
# key hash title artist link 0
0 SinglesVarious  0  Singles  Various  -1 
1         -1 
2 Schubert DipEMF  2  Schubert Dip  EMF  -1 
3 FaceliftAlice in Chains  3  Facelift  Alice in Chains  -1 
4 The Freedom SessionsSarah McLachlan  4  The Freedom Sessions  Sarah McLachlan  29 
5         -1 
6 TenPearl Jam  6  Ten  Pearl Jam  -1 
7 Siamese DreamSmashing Pumpkins  7  Siamese Dream  Smashing Pumpkins  -1 
8 The CrowVarious  8  The Crow  Various  -1 
9 Countdown to ExtensionMegadeath  9  Countdown to Extension  Megadeath  37 
10         -1 
11 Out of TimeREM  11  Out of Time  REM  -1 
12 From the Choirgirl HotelTori Amos  12  From the Choirgirl Hotel  Tori Amos  -1 
13 Best of BeethovenBeethoven  13  Best of Beethoven  Beethoven  42 
14 ViolatorDepeche Mode  14  Violator  Depeche Mode  27 
15 WarU2  14  War  U2  -1 
16 INXSINXS  16  INXS  INXS  48 
17 The Book of SecretsLoreena McKennitt  17  The Book of Secrets  Loreena McKennitt  -1 
18 The Unforgettable FireU2  38  The Unforgettable Fire  U2  44 
19 10 Summoner's TalesSting  42  10 Summoner's Tales  Sting  -1 
20 ChumbawambaChumbawamba  20  Chumbawamba  Chumbawamba  -1 
21 Songs from the TrilogyPhilip Glass  21  Songs from the Trilogy  Philip Glass  45 
22 Ritual de lo HabitualJane's Addiction  22  Ritual de lo Habitual  Jane's Addiction  -1 
23 Piano ManBilly Joel  23  Piano Man  Billy Joel  -1 
24         18 
25         -1 
26 InnuendoQueen  30  Innuendo  Queen  -1 
27 SynchronicityThe Police  14  Synchronicity  The Police  15 
28 DirtAlice in Chains  28  Dirt  Alice in Chains  51 
29 IntrospectivePet Shop Boys  4  Introspective  Pet Shop Boys  -1 
30 DespiteChatterbox  30  Despite  Chatterbox  36 
31 Tragic KingdomNo Doubt  33  Tragic Kingdom  No Doubt  -1 
32 Moving PicturesRush  32  Moving Pictures  Rush  -1 
33 II PornograffittiExtreme  33  II Pornograffitti  Extreme  46 
34 ODELAYBeck  34  ODELAY  Beck  43 
35 Best of Mozart IIIMozart  51  Best of Mozart III  Mozart  -1 
36 Best of Mozart IIMozart  30  Best of Mozart II  Mozart  26 
37 Best of Mozart IMozart  9  Best of Mozart I  Mozart  -1 
38 ElectriclarrylandButthole Surfers  38  Electriclarryland  Butthole Surfers  52 
39 Use Your Illusion 2Guns & Roses  39  Use Your Illusion 2  Guns & Roses  -1 
40         -1 
41 Club Mix 96 Vol 2Various  41  Club Mix 96 Vol 2  Various  50 
42 LustLords of Acid  13  Lust  Lords of Acid  19 
43 Lost BoysVarious  34  Lost Boys  Various  32 
44 FrogstoneSilverchair  52  Frogstone  Silverchair  -1 
45 Information SocietyInformation Society  21  Information Society  Information Society  -1 
46 Vital IdolBilly Idol  33  Vital Idol  Billy Idol  31 
47 Use Your Illusion 1Guns & Roses  38  Use Your Illusion 1  Guns & Roses  18 
48 Dangerous MindsVarious  16  Dangerous Minds  Various  -1 
49 101Depeche Mode  49  101  Depeche Mode  -1 
50 Your Little SecretMelissa Ethridge  41  Your Little Secret  Melissa Ethridge  -1 
51 Best of the DoorsThe Doors  28  Best of the Doors  The Doors  35 
52 DisintegrationCure  38  Disintegration  Cure  47 

Next Section - EICH (Early Insertion Coelescing Hashing)