Assignment 3

Exercise 3 - Simple hash table Develop a simple hashtable with specified size (parameter) that accepts key-value pairs and stores them in an internal structure. ● • The key has to be a string ● ● Use your hash function from exercise 2 • The value can be an object Demonstrate how your hashtable works with multiple inputs Implement add (key, value), get(key), and print () methods

The hash table array has capacity of 10. Capacity is the number of slots present in the array that is used to build the hashtable. The hash function returns the absolute value of the key mod the capacity of the hash table. a) Insert these keys in the hash table: 3,23,11,21,1,7,77,8 where the hash table uses quadratic probing to resolve collisions. b) Search and Delete 3 and 11 from the table. Be careful about changing the status of the table slot to “deleted” after deleting each item. c)Search 23 and 21 from the table and print their position.

2) Hash Innards Homework • Unanswered Select all true statements from the below. Multiple answers: Multiple answers are accepted for this question Select one or more answers and submit. For keyboard navigation. SHOW MORE V a A hash function takes a key and produces an index into the hash table. The next step in this process is often something like 'h%SIZE' so that the hash value of the key will fit within the table b (having SIZE elements, you see). Common techniques involve exclusive or of bits within the key and folding different sections of bits within the key into each other. The best hash method for character strings is to simply add up the ASCIlI values of their individual characters. Coming up with a perfect hash for a given set of keys can be a difficult and time-consuming task.

= Question 3. In the following hash table, we insert elements using hashing with open addressing with quadratic probing. Elements have as keys integer numbers, and the hash function for the i-th probe is given by hash(x, i) (x + ²) %11. We insert, in the given order, the elements with the following keys: 46, 58, 57, 39. Indicate, where these elements will be placed in the table. index value 0 1 2 3 4 5 6 7 8 9 10

import hashlib def hash_function(password, salt, al):  if al == 'md5':    #md5    hash = hashlib.md5(salt.encode() + password.encode())    hash.update(password.encode('utf-8'))    return hash.hexdigest() + ':' + salt  elif (al == 'sha1'):    #sha1      hash = hashlib.sha1()    hash.update(password.encode('utf-8'))    return hash.hexdigest() + ':' + salt  elif al == 'sha224':    #sha224    hash = hashlib.sha224()    hash.update(password.encode('utf-8'))    return hash.hexdigest() + ':' + salt  elif al == 'sha256':    #sha256    hash = hashlib.sha256()    hash.update(password.encode('utf-8'))    return hash.hexdigest() + ':' + salt  elif al == 'blake2b':    #blake2b512    hash = hashlib.blake2b()    hash.update(password.encode('utf-8'))    return hash.hexdigest() + ':' + salt  else:    print("Error: No Algorithm!") if __name__ == "__main__":  # TODO: create a list called hash_list that contains  # the five hashing algorithsm as strings  # md5, sha1, sha224, sha256, blake2b    hash_list =…

Class HashTable: Implement a hash table to store integers (including negative ones).  stored in the table int[] data. Use the hash function:  h(x) = (x · 701) mod 2000.  The table size is 2000. Ensure non-negative indices between 0 and 1999. Implement the following methods: insert(int key): Inserts the integer into the table. Returns true if successful, false if the element is already in the table. search(int key): Searches for the integer in the table. Returns true if found, false otherwise. delete(int key): Deletes the integer from the table. Returns true if successful, false otherwise. Class HashTable2: Implement a second hash table using a different hash function and collision resolution strategy. Keys are integers (including negative ones). Use the hash function: ℎ(�)=(�⋅53)mod  100h(x)=(x⋅53)mod100. The table size is 100. Ensure non-negative indices between 0 and 99. Implement the following methods: insert(int key): Inserts the integer into the table. Returns true if…

Course: Data Structure and Algorithms Language: Java Kindly  something and Answer in 1 hour. Read Carefully and give answer with all necesary details. See the image for askii codes. Question6:   In this Problem, you are required to insert some keys into a hash table, using given hash functions. You have to Draw a Hash table with the inserted keys. Write total number of collisions encountered when a particular collision resolution technique is used. size= 13, H(X) = sum of Ascii codes of key % HTSIZE Keys: Mia, Bea, Zoe, Jan, Ada, Sam, Leo, Meo, Ben, Tim, Ted, Zod Use Linear probing: H’(X) = [H(X) +f(i))] % HTSIZE  where f(i)=i  where i=0,1,2,….

struct search_within_hash_table { // Function takes no parameters, searches a hash table for a book with an ISBN // matching the target ISBN, and returns a pointer to that found book if such // a book is found, nullptr otherwise. Book* operator()(const Book& unused) { //// TO-DO (21) ||| (/ //// // Write the lines of code to search for the Book within "my_hash_table" // with an ISBN matching "target_isbn". Return a pointer to that book // immediately upon finding it, or a null pointer when you know the book is // not in the container. // // NOTE: Do not implement a linear search, i.e., do not loop from beginning // to end. ///// END-TO-DO (21) |||// //// } std::unordered_map& my_hash_table; const std::string target_isbn; };

Python  Why am I still getting an error? # Problem 1# Implement a hashtable using an array. Your implementation should include public methods for insertion, deletion, and# search, as well as helper methods for resizing. The hash table is resized when the loadfactor becomes greater than 0.6# during insertion of a new item. You will be using linear probing technique for collision resolution. Assume the key to# be an integer and use the hash function h(k) = k mod m where m is the size of the hashtable. class HashTableProb:    def __init__(self, size=10):        # Initialize the hashtable with the given size and an empty array to hold the key-value pairs.        self.__size = size # size of the hashtable        self.__hashtable = [None for _ in range(size)]        self.__itemcount = 0 # Keeps track of the number of items in the current hashtable     def __contains__(self, key):        return self.__searchkey(key)     def __next_prime(self, x):        def is_prime(x):            return…

All of these statements are related to hash function, hash table.

60. The field on which the equality condition is placed is hashing technique is called a. hash field b. cluster filed c. spanned field d. sequential field

Assume a hash table utilizes an array of 13 elements and that collisions are handled by separate chaining. Considering the hash function is defined as: h(k)=k mod 13. i) Draw the contents of the table after inserting elements with the following keys: 36, 243, 261, 180, 217, 180, 21, 16, 182, 202, 91, 97, 166, 78, 33, 70, 51, 58.

Java - A chained hash table has an array size of 512; what is the maximum number of entries that can be placed in the table?

A A hash function works like an array index. Select one: a. False b. True

In java Create a hash table using an array with elements 324,221,563,679,234,569,890,5678,654 then perform the following operations. 1) Insert 227 2) Delete 679 and Insert 9 3) Insert 67 4) Display the hash table content Note: This hash table uses technique linear probing when encounters a collision.

Hashing is the problem of finding an appropriate mapping of keys into addresses.a) Trueb) False

Exercise 1- Hashing a String • We can create hash functions for character-based items such as strings by converting the string to a numeric and then hash this value. Develop a function called hash that takes a string and a table (array) size and returns the hash value in the range from 0 to tablesize-1. 99 +97 +116 312 312 % 11

Case study: An event company asks you to design the data structure and program prototype for their running event system. The participant for the running event is expected to reach more than 1000 in various categories. You decided to use hashing function method to store the information for each participant's BIB number in the hash table. To begin the problem solving, suppose that 10 registered runners need to be stored in a hash table, HT, with a size of 13. The sample BIB number of the runners are: 101, 102, 103, 104, 107, 111, 121, 217, 157, and 185. Furthermore, you set the hash function to determine the index of the participant in the HT as: hash (BIB) = BIB % table size (or 13) However, if the hash index given by hash(BIB) is already occupied (collision), the linear probing hash function will be used as: hash (BIB) = (Hash (BIB)+1) % 17 and, further collision with hash function: hash (BIB) = (Hash(BIB)+2) % 17 or, hash(BIB) = (Hash (BIB) + n) % 17, where n is probe increment. Refer…

A hash function should be independent of the capacity of the hash table. Select one: a. False O b. True

Exercise 1 - Hashing a String • We can create hash functions for character-based items such as strings by converting the string to a numeric and then hash this value. ● Develop a function called hash that takes a string and a table (array) size and returns the hash value in the range from 0 to tablesize-1. 99 +97 +116 = 312 312 % 11 4

Data Structure & Algorithm: Describe and show by fully java coded example how a hash table works. You should test this with various array sizes and run it several times and record the execution times. At least four array sizes are recommended. 10, 15, 20, 25. It is recommended you write the classes and then demonstrate/test them using another class

Using the modulus operator within a hash function or on the output of a hash function: Will always cause rehashing. Will cause the hash table to shrink. Can cause collisions. O Will always produce a unique hash bucket.

An empty hash table hashTable has 20 buckets and a hash function of key % 20. The following operations are performed in order. Select which operations cause a collision. HashInsert(hash Table, 10) HashInsert(hashTable, 15) HashInsert(hash Table, 55) HashInsert(hashTable, 13) HashInsert(hashTable, 33)

#7. HashTable Data Type:    By having each bucket contain a linked list of elements that are hashed to that bucket.    Usage:    >>> table = SeparateChainingHashTable() # Create a new, empty map.    >>> table.put('hello', 'world') # Add a new key-value pair.    >>> len(table) # Return the number of key-value pairs stored in the map.    1    >>> table.get('hello') # Get value by key.    'world'    >>> del table['hello'] # Equivalent to `table.del_('hello')`, deleting key-value pair.    >>> table.get('hello') is None # Return `None` if a key doesn't exist.    True    """    _empty = None     def __init__(self, size=11):        self.size = size        self._len = 0        self._table = [self._empty] * size     def put(self, key, value):        hash_ = self.hash(key)        node_ = self._table[hash_]        if node_ is self._empty:            self._table[hash_] = Node(key, value)        else:            while node_.next is not None:…

Hashing 1. Develop an algorithm to demonstrate hashing using hash table with modulo as the hash function. Assume the size of the hash table as 10. To avoid collisions in case of identical keys for two different elements, use Linear Probing collision resolution technique. 2. Analyse time and space complexity of the designed algorithm 3. Write C++ program to implement Hashing 4. Test and debug the program 5. Obtain the results 6. Document the report

- In class HashTable implement a hash table and consider the following:(i) Keys are integers (therefore also negative!) and should be stored in the tableint[] data.(ii) As a hash function take h(x) = (x · 701) mod 2000. The size of the table istherefore 2000. Be careful when computing the index of a negative key. Forexample, the index of the key x = −10 ish(−10) = (−7010) mod 2000 = (2000(−4) + 990) mod 2000 = 990.Hence, indices should be non-negative integers between 0 and 1999!(iii) Implement insert, which takes an integer and inserts it into a table. Themethod returns true, if the insertion is successful. If an element is already inthe table, the function insert should return false.(iv) Implement search, which takes an integer and finds it in the table. The methodreturns true, if the search is successful and false otherwise.(v) Implement delete, which takes an integer and deletes it form the table. Themethod returns true, if the deletion is successful and false otherwise.(vi)…

3. Double hashing is one of the methods to resolve collision. Write a function to implement this method. The equations used in this method are given below. Note: implement everything within the double hash function. P = (P + INCREMENT(Key)) mod TABLE_SIZE INCREMENT(Key) = 1 + (Key mod INCR)

Cuckoo hashing. Develop a symbol-table implementation that maintains twohash tables and two hash functions. Any given key is in one of the tables, but not both. When inserting a new key, hash to one of the tables; if the table position is occupied, replace that key with the new key and hash the old key into the other table (again kicking out a key that might reside there). If this process cycles, restart. Keep the tables less than half full. This method uses a constant number of equality tests in the worst case for search (trivial) and amortized constant time for insert.

Racket code only please. No loops or use of hash. Allowed functions are: 1. define, let2. lambda3. cons, car, cdr, list, list?, append, empty?, length, equal?4. and, or, not5. if, cond6. map, append-map, andmap, ormap, filter7. +, -, /, *8. Functions you implement

91. If the global depth in extendible hashing is equal to local depth then the operation must be performed in directory array is a. adding b. subtracting c. halving d. doubling

mplement a hash table for strings. Create two hashing functions. It is up to you which type of chaining/probing you use. Add several (>10) strings to the hash table and display the table. Repeat this using a second, different hash function on the same strings. You should make your own hash functions.

The main thing that affects the Big-O of a hash map is the load factor. O True False

A collision occurs in hashing when: O a. two data items hash to the same location. O b. a data item hashes to two locations O c. the table is full O d. the hash function is undefined for a given data item. O e. None of these are correct

Explain the importance of hash functions in the efficient operation of hash maps or dictionaries.

Q: Hash table is a data structure in which keys are mapped to array positions by a hash function. Theprocess of mapping the keys to appropriate locations in a hash table is called hashing. Hash functions areused to reduce the number of collisions.i. Mention the methods to minimize collision.ii. Explain the advantage of using double hashing over linear and quadratic probing techniques.iii. Load the keys given below in a hash table of size 7 in the same order using chaining with thehash function h(key)= key % 7. Show graphically how collisions are resolved using chainingin this particular case.12, 101, 3, 21, 14, 13, 16, 7, 141