A hash table is a collection of buckets . Each bucket is a collection of binding

Question

A hash table is a collection of buckets. Each bucket is a collection of bindings. Each binding consists of a key and a value. A key uniquely identifies its binding; a value is data that is somehow pertinent to its key. The mapping of bindings to buckets is determined by the hash table's hash function. A hash function accepts a binding's key and bucket count, and returns the number of the bucket in which that binding should reside.

A collision occurs when more than one binding is mapped to the same bucket. A good hash function distributes bindings fairly uniformly across the hash table's buckets, and thus minimizes collisions. A bad hash function is one that generates many collisions. With a good hash function, the retrieve/insert/delete performance of a hash table is very fast.

Implement a 100-bucket Hash Table ADT which can hold a set of integers. In the case of collision, the chaining resolution method will be used.

Output the content of each bucket.

Explanation / Answer

In this question, We will try to make a generic map without putting any restrictions on the data type of the key and the value. Also every hash node needs to know the next node it is pointing to in the linked list so a next pointer is also required.

The functions we plan to keep in our hash map are

Now, Here goes our code. I have implemented it in Java Language

import java.util.ArrayList;
class HashNode<K, V>
{
K key;
V value;
HashNode<K, V> next;
public HashNode(K key, V value)
{
this.key = key;
this.value = value;
}
}
class Map<K, V>
{
private ArrayList<HashNode<K, V>> bucketArray;
private int numBuckets;
private int size;
public Map()
{
bucketArray = new ArrayList<>();
numBuckets = 10;
size = 0;
for (int i = 0; i < numBuckets; i++)
bucketArray.add(null);
}

public int size() { return size; }
public boolean isEmpty() { return size() == 0; }
private int getBucketIndex(K key)
{
int hashCode = key.hashCode();
int index = hashCode % numBuckets;
return index;
}
public V remove(K key)
{
int bucketIndex = getBucketIndex(key);
HashNode<K, V> head = bucketArray.get(bucketIndex);
HashNode<K, V> prev = null;
while (head != null)
{
if (head.key.equals(key))
break;
prev = head;
head = head.next;
}
if (head == null)
return null;
size--;
if (prev != null)
prev.next = head.next;
else
bucketArray.set(bucketIndex, head.next);
return head.value;
}
public V get(K key)
{
int bucketIndex = getBucketIndex(key);
HashNode<K, V> head = bucketArray.get(bucketIndex);
while (head != null)
{
if (head.key.equals(key))
return head.value;
head = head.next;
}
return null;
}
public void add(K key, V value)
{
int bucketIndex = getBucketIndex(key);
HashNode<K, V> head = bucketArray.get(bucketIndex);
while (head != null)
{
if (head.key.equals(key))
{
head.value = value;
return;
}
head = head.next;
}
size++;
head = bucketArray.get(bucketIndex);
HashNode<K, V> newNode = new HashNode<K, V>(key, value);
newNode.next = head;
bucketArray.set(bucketIndex, newNode);
if ((1.0*size)/numBuckets >= 0.7)
{
ArrayList<HashNode<K, V>> temp = bucketArray;
bucketArray = new ArrayList<>();
numBuckets = 2 * numBuckets;
size = 0;
for (int i = 0; i < numBuckets; i++)
bucketArray.add(null);
for (HashNode<K, V> headNode : temp)
{
while (headNode != null)
{
add(headNode.key, headNode.value);
headNode = headNode.next;
}
}
}
}

// test Map class
public static void main(String[] args)
{
Map<String, Integer>map = new Map<>();
map.add("this",1 );
map.add("coder",2 );
map.add("this",4 );
map.add("hi",5 );
System.out.println(map.size());
System.out.println(map.remove("this"));
System.out.println(map.remove("this"));
System.out.println(map.size());
System.out.println(map.isEmpty());
}
}

OUTPUT

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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