You have approx. 350 customers. N 350 You can obtain information about each cust

Question

You have approx. 350 customers. N 350 You can obtain information about each customer such as name, phone number, SSN, address, items they like to buy, etc. and assign customer number (note: customer numbers will not be reused/recycled as cuatomers go away) You want to look up their records using some key that will be used to hash into the customer table. Write the answers on a sheet of paper. Add your full names at the top of the sheet now. 1. what key do you think is usually good to use to look up a customer? what does it look like (give an example) State Issued ID# D7231445 Note that you can even combine two pieces of infomation. 2. what is the table size and defend your choice radix n 350 439 it is not close to a small power of the radix is a prime number and n/ts is about 808 (prime number? Avoided Base small? Load factor is 808?? Answer these.) 3- how will transform this key into a 31ot number and detend your choice Straight Folding and mod ts? Reverse folding and mod ts? Square and take the middle part? something unique? 4. informally analyze under what circumstance collisions will occur Give reasons and examples

Explanation / Answer

2)A hash table is a collection of items which are stored in such a way as to make it easy to find them later. Each position of the hash table, often called a slot, can hold an item and is named by an integer value starting at 0.

The fixed process to convert a key to a hash key is known as a hash function. This function will be used whenever access to the table is needed.

One common method of determining a hash key is the division method of hashing. The formula that will be used is:

hash key = key % number of slots in the table

given n=350

where table size(ts)=439

Once the hash values have been computed, we can insert each item into the hash table at the designated position as shown in Figure 5. Note that 6 of the 11 slots are now occupied. This is referred to as the load factor, and is commonly denoted by

=numberofitems ablesize

=350#9=0.797

is nothing but load factor.

3)The folding method for constructing hash functions begins by dividing the item into equal-size pieces (the last piece may not be of equal size). These pieces are then added together to give the resulting hash value. For example, if our item was the phone number 436-555-4601, we would take the digits and divide them into groups of 2 (43,65,55,46,01). After the addition, 43+65+55+46+01 43+65+55+46+01, we get 210. If we assume our hash table has 11 slots, then we need to perform the extra step of dividing by 11 and keeping the remainder. In this case 210 % 11 210 % 11 is 1, so the phone number 436-555-4601 hashes to slot 1. Some folding methods go one step further and reverse every other piece before the addition. For the above example, we get 43+56+55+64+01=219 43+56+55+64+01=219 which gives 219 % 11=10219 % 11=10.

here our Problem folding the customer items is 350

2(7 2 3 1 4 4 5)=15

folding the items is 350%15=23

Another numerical technique for constructing a hash function is called the mid-square method. We first square the item, and then extract some portion of the resulting digits. For example, if the item were 44, we would first compute 442=1,936 442=1,936. By extracting the middle two digits, 93, and performing the remainder step, we get 5 (93 % 11 ,93 % 11).

in this problem perform the mid square method like customer item is 350 we would like 3502=122,500 by extracting the middle two digits 25 and performing the reminder step 7(25%15).

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.