Java Language
Implement hash tables using open addressing and
chaining
Test your implementation with sample values.
Please find the code below:
Custom Node class:
package different; //custom Node class public class Node<K,V> { //key K key; //value V value; //next node Node<K,V> next; //default constructor public Node(K key, V value){ this.key = key; this.value = value; } }
Custom Map class:
import java.util.ArrayList; public class MyMap<K,V> { //list to store values ArrayList<Node<K,V>> myList; //capacity of list int capacity; //size of the list int size; //default constructor public MyMap(){ myList = new ArrayList<>(); //intial capacity capacity = 10; //intital size; size = 0; for(int i=0;i<capacity;i++){ myList.add(null); } } //get size public int size(){ return size; } //check if it's empty public boolean isEmpty(){ return myList.isEmpty(); } //find index int getIndex(K key){ return key.hashCode() % capacity; } //add a key public void add(K key, V value){ //get the first index for the key int index = getIndex(key); //get the node at index Node<K,V> chain_head = myList.get(index); //check if the key is present at that value while(chain_head!=null){ if(chain_head.key.equals(key)){ //update the value chain_head.value = value; return; } chain_head = chain_head.next; } //Else insert key into the cahin size++; chain_head = myList.get(index); Node<K,V> newNode = new Node<>(key, value); newNode.next = chain_head; myList.set(index,newNode); //If list is full by 80% then increase the capacity of the list if((size*1.0)/capacity >= 0.80){ ArrayList<Node<K,V>> newList = myList; myList = new ArrayList<>(); capacity = 2 * capacity; size = 0; for(int i=0;i<capacity;i++){ myList.add(null); } for(Node<K,V> node : newList){ while(node!=null){ add(node.key,node.value); node = node.next; } } } } //get the value for given key public V get(K key){ //find the fitst node in chain for given key int index = getIndex(key); Node<K,V> chain_head = myList.get(index); while(chain_head!=null){ if(chain_head.key.equals(key)){ return chain_head.value; } chain_head = chain_head.next; } return null; } //remove value for given key public V remove(K key){ //find the fitst node in chain for given key int index = getIndex(key); Node<K,V> chain_head = myList.get(index); //serach for the given key node Node<K,V> prev = null; while(chain_head!=null){ if(chain_head.key.equals(key)){ break; } prev = chain_head; chain_head = chain_head.next; } if(chain_head==null){ return null; } size--; if(prev!=null){ prev.next = chain_head.next; } else{ myList.set(index,chain_head.next); } return chain_head.value; } public static void main(String[] args) { MyMap<String,Integer> myMap = new MyMap<>(); myMap.add("One",1); myMap.add("Two",2); myMap.add("Three",3); myMap.add("Four",4); System.out.println("Size: " + myMap.size()); System.out.println("Removed Value: " + myMap.remove("Three")); System.out.println("Size: " + myMap.size()); System.out.println("Is Empty?: " + myMap.isEmpty()); System.out.println("Value with Key \"One\": " + myMap.get("One")); } }
Output:
Java Language Implement hash tables using open addressing and chaining Test your implementation with sample values.
Java: Reimplement separate chaining hash tables using singly linked lists instead of using java.util.LinkedList.
This week you worked with hash tables and a variety of ways to handle collisions. For this lab, please implement a hash table that uses a linked list to handle chaining for collision avoidance. You can be creative with your implementation, what I will grade on this lab is your effective hash table implementation ( linked list and chaining ).
Title: Implementation of chained hashing in Java or Python Description: Implement a double linked list with a procedure for adding list elements. Implement a hash table using chaining and the linked list discussed above. Use Array size m = 7 A hash function of: h = k mod 7 Insert 100 random key values into the table. Key values should be between 0 and 99. Implement a Search procedure that tells whether a particular key value is in the hash...
Part 5. Suppose that your hash function resolves collisions using the open addressing method with double hashing. The double hashing method uses two hash functions h and h'. Assume that the table size N = 13, h(k) = k mod 13, h'(k) = 1 + (k mod 11), and the current content of the hash table is: 0 1 2 3 6 7 8 9 10 11 12 4 17 5 98 If you insert k = 14 to this...
Question 8: (a) We create a Hash Table of size 7, using open addressing and linear probing with the hash function h(n)=n%7. Write the content of the array after inserting the following values in sequence: 11, 28,46, 7,67, 88,0. (3 marks) . loj [1] [2] [3] [41-5] 问 (b) Explain the issue linear probing has and how it can be addressed. (3 marks)
Implement a StringHash class using python using open addressing and linear probing, it should contain the following methods: Using strings for the data 1. StringHash(size) — create a new hashTable with a default size of 11 for your array, but allow the user to specify an alternate size if desired 2. addItem(string) — place value into the hashTable iv. bool PindItem(string value) — return true if the value is present, else false 3. findItem(string value) — return true if the...
4. Hashing and Hash Tables. You need to use the ASCII table in the last page for this question. Study the following hash functions for ASCII C strings that are at least 3-char long unsigned hash1(const char, unsigned unsigned vto]+01997 return (v % m); unsigned hash2Cconst char unsigned) unsigned v-o]k(2] 877 return 1 + (v % ( -1)); (a) Given that m-, 7, compute the hash values and fill the following table (3%) String k hash1k, ) hash2(k, 7) aph...
Hash Tables. In C programming language, solve these problems efficiently using Hashtables and analyze the running time of your solution. 1. Given an unsorted array of length N, print all elements that appear more than once. 2. Find the intersection of K unsorted arrays of N elements each. The intersection consists of elements that appear in all the K arrays.
Using Java programming language Your assignment is to implement a recursive reverse sorting algorithm. It should meet the following requirements: 1. The program shall graphically prompt the user for a file. 2. The program shall read the selected file which will contain 1 integer per line. 3. The program shall sort the values it reads from the file from largest to smallest. 4. The program shall write the values to an output file from largest to smallest in the same...
Please answer this problem in C++, Thank you! Read and study the sample program: "hashing with chaining using singly linked lists", as well as "hashing with chaining using doubly linked lists". Notice this program is complete except it doesn't include the remove function. Write the remove function and test it with the rest of the program including the given main program. Upload your C++ source file. ---Here is the referenced program: "hashing with chaining using singly linked lists". Below this...