Assignment 1 Hashing DATAIN is a text file which contains 59 records whose format is in KEYDATA, where KEY is a character(string) field of 10 characters and DATA is a character (string) field of 20 characters. Read DATAIN and hash each record using a hash function into the memory data structure.

The hash table consists of a primary and overflow area. The primary area has 20 buckets, each bucket containing 3 hash slots, an overflow pointer and count fields. The overflow area contain an additional number of buckets dedicated to handle collisions. Bucket zeros overflow pointer field may be used to point to the next available overflow bucket in the event of a collision.

A collision occurs when two or more data keys hash to the same bucket. If a collision occurs and there is a vacant slot in the primary bucket, the record is stored in the first available slot. If the primary area bucket is full and an overflow bucket has been allocated, store the record in the next available slot within overflow area bucket. If no overflow bucket has been allocated, allocate one (link the primary area bucket to its overflow bucket using the pointer field). After hashing all records contained within the file DATAIN, write the memory data structure to a file called HASHTABLE and display the contents of all hash buckets in the report format shown below.

DATAIN.dat

TATUNG CO.EL PR. LONG BEACH CA KAMERMAN LCIRRUS BEAVERTON, OR QUADRAM COLOACH AV NORCROSS GE AST RESEARALTON AV IRVINE CA EXPRESS SYREMING SCHAUMBURG IL DAC SW INCSPRING VAL DALLAS TX SUMMIT TECBABSON WELLESLEY, MA SIGMA DESIUNIVER A SAN JOSE CA HERCULES CNINTH ST BERKELEY CA MICROSTUF,H.W. PKWY ROSWELL GE MAXELL CO.OXFORD MOONACHIE NJ PRINCETON.EWING S PRINCETON NJ IOMEGA CORWESTA SOUTH ROY UTAH VEN-TAL INWALSH SANTA CLARA CA TAXAN CORPCITY OF INDUSTRY, CA ORCHID CORWESTINGHO FREMONT CA SSISOFTWARCENTER ST. OREM UTAH GRAPHIC CO5TH AVE. WALTHAM, MA VICTOR CORSCOTTS VALLEY, CALIF NCR COORPOBOWLING DR DAYTON OH MICROMART.CAMPUS D NORCROSS GE HEWLETT PABERNARD SAN DIEGO CA MICROPRO IBOX 57135 HAYWARD CA BORLAND I.SCOTTS V. DR S.V. CA LOGIQUEST.MONTRE QUEBEC CANADA PROSOFT COBELLAI HOLLEYWOOD CA SPECTRUM SWOLFE R SUNNYVALE CA HONEYWELL.BAKER COSTA MESA, CA EMERSON COSTAN ST SANTA ANA CA SOURCE TELPOBOX 1305 MCLEAN VA MICROGRAFXGREEN RICHARDSON, TX IBM CORPORBOCA RATON, FLORIDA INTEL COOR5 ST MOUNTAINVIEW CA MICRODESIGUNVIE WINTER PARK FL QUBIE CORPCALLE S CAMARILLO CA PARADISE STAYLOR S BRISBANE CA EVEREX SYSMILMONT FREMONT, CA INTERLUDE.RICHMOND HOUSTON, TX EPSON AMERBEDA STR TORRANCE CA CHANNELS IKI ST TORONTO CANADA BORTHER I.THENALA DR IRVINE CA MAYNARD ELSEMOR CASSELBERRY FL DIGITAL REGARDEN C MONTEREY CA CORE INTERFEDERA BOCA RATON FL ROSESOFT CUNIVE WAY SEATTLE WA BUSSIN TOL128 AVE BELLEVUE, WA TALLTREE SSNTONIO PALO ALTO CA GENOA SYSTTRIMBLE SAN JOSE, CA CURITS INCUNIO PETERBOROUGH NH OKIDATA COA MOUNTAIN LAUREL NJ COMPUADD CTECH BLVD. AUSTIN TX AMDEK COR.MAINE GROVE VALLY IL DYSAN CORPPAT H SANTA CLARA CA MICROWAY CTEMPOHOUSE LONDON UK TECMAR INTCOCHRAN RD. SOLON OH QUANTUM SWSTAFFO OTTAWA CANADA PROMETHEUSFREMONT S FREMONT CA FUNK SOFTW3RD ST CAMBRIDGE, MA

SEARCH.dat

KALLTREE S DAC SW INC COMPUADD C MICROWAY C TATUNG CO. DYSAN CORP DIGITAL RE QUANTBM SW PROMETHEUS EVEREX SYS MICROMART. PARADISE S SPECTRUM S MICRODESIG MAXELL CO. AMDEK COR, TECMAR INT IBM CORPOR OHCHID COR FUN SOFTW

Hash Table Verification Report Before | After Restoration Bucket 1 Slot 1: Slot 2: Overflow Pointer: xx Bucket n Slot 1: slot 2: Overflow Pointer: xx Hash Table Verification Report Before | After Restoration Bucket 1 Slot 1: Slot 2: Overflow Pointer: xx Bucket n Slot 1: slot 2: Overflow Pointer: xx