B. Use the following hash function to build a hash table of array size (12). has
ID: 3852032 • Letter: B
Question
B. Use the following hash function to build a hash table of array size (12). hashFunction (s) s leftarrow s. toUpperCase (): hash leftarrow ((s. charAt (1) + s.charAt(0)))/2 - 'A') MOD 12 return hash Use the hash function and the table below to insert the following strings in the hash table: Apple, Banana, Jack, Kite, Motorcycle, Book, Computer, Data, Information, Blue, Green, Red, Yellow, Orange, Car. C. What collision handling technique did you use to deal with collisions? D. What is the name of the other collision handling technique?Explanation / Answer
B. Program answer
def get(Apple, banana,jack,kite,motorcycle,book,computer,data,information,blue,green,red,yellow,orange,car):
startslot = self.hashfunction(Apple, banana,jack,kite,motorcycle,book,computer,data,information,blue,green,red,yellow,orange,car(self.slots))
data = None
stop = False
found = False
position = startslot
while self.slots[position] != None and
not found and not stop:
if self.slots[position] == key:
found = True
data = self.data[position]
else:
position=self.rehash(position,len(self.slots))
if position == startslot:
stop = True
return data
def __getitem__(Apple, banana,jack,kite,motorcycle,book,computer,data,information,blue,green,red,yellow,orange,car):
return self.get(key)
def __setitem__(Apple, banana,jack,kite,motorcycle,book,computer,data,information,blue,green,red,yellow,orange,car):
self.put(Apple, banana,jack,kite,motorcycle,book,computer,data,information,blue,green,red,yellow,orange,car)
H=HashTable()
H[0]="apple"
H[1]="banana"
H[2]="jack"
H[3]="kite"
H[4]="motorcycle"
H[5]="book"
H[7]="computer"
H[8]="data"
H[9]="information"
H[10]="orange"
H[11]="car"
H.slots
[0,1,2,3,4,5,6,7,8,9,10,11]
H.data
[Apple, banana,jack,kite,motorcycle,book,computer,data,information,blue,green,red,yellow,orange,car]
c.Different types of collision handling techniques.
Hash Table Collision Handling
They are two basic methods
1. separate chaining and
2. open address.
1. Separate Chain
Hangs an additional data structure off of the buckets. For example the bucket array becomes an array of link list. So to find an item we first go to the bucket then compare keys.. This is a popular method, and if link list is used the hash never fills up.
Explanation
load factor, f = n/N where n is number of items stored in the hash table. Like for the load factor to be less then 1.
The cost for get(k) is on average O(n/N)
Open Addressing
The problem with separate chaining is that the data structure can grow with out bounds. Sometimes this is not appropriate because of finite storage, for example in embedded processors.
2. Open addressing does not introduce a new structure. If a collision occurs then we look for availability in the next spot generated by an algorithm. Open Addressing is generally used where storage space is a premium, i.e. embedded processors. Open addressing not necessarily faster then separate chaining.
Methods for Open Addressing:
1. Linear Probing:
We try to insert Item = (k, e) into bucket A[i] and find it full so the next bucket we try is:
A[(i + 1) mod N]
then try A[(i + 1) mod N], etc.
Illustrate with 11 buckets: Note the probing is linear.
Note the hash table can be filled up.
Also what to do if we remove an Item. Should repair the array A but this is too costly. Instead we mark the bucket as available/deactivated. Then the next use of findElement(k) would skip over the available/deactivated bucket. insertItem(k, e) would insert into a available/deactivated.
Clustering slows down searches.
2. Quadratic Probing:
A[ (i + f(j) )mod N] where j = 0, 1, 2, ... and f(j) = j2
Helps avoids clustering. Secondary clustering can occur. We can imagine a more complicated function for f.
3. Double Hashing:
Use a second hash function h'
A[ (i + f(j) )mod N] where f(j) = j*h'(k) should not evaluate to zero. Example: h'(k) = q - (k mod q). Note that still i = h(k).
d. Other collision Technique.
answer is
2. open address.
Explanation is above , please read above one
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.