Follow Me

Hash tables exercises in C Programming in C

  • Hashing using linear probing: Consider the following hash table where the elements with the same hash value are inserted using linear probing. i.e. the keys \(e\) with the same hash value \(v\) are sorted in ascending order starting from \(v\) in a circular manner. \begin{array}{...
  • Hashing using quadratic probing: Consider a hash table \(T[0\cdots m-1]\) where quadratic probing is used to resolve collision. Recall that to resolve collision using quadratic probing when inserting a key $$e$$ in the hash table , addresses \(h(e)\), \(h(e)+1\), \(h(e)+4\), \(\cdots\)...
  • Cuckoo hashing: The idea of Cuckoo hashing is to resolve collisions by using two hash functions instead of only one. In the basic variant of Cuckoo hashing, we use two hash tables $$T_1$$ and $$T_2$$ of equal size $$N$$, and we index each key $$k$$ with the hash fu...
  • Hopscotch hashing: \(Hopscotch\ hashing\) is a scheme in computer programming for resolving hash collisions of values of hash functions in a table using open addressing. \(Hopscotch\ hashing\) was introduced in 2008. The name is derived from the sequence of hops that c...
  • Trace of adding elements to a hash table: Given the elements {4371, 1323, 6173, 4199, 4344, 9679, 1989}, a fixed hash table size of 10, and the hash function \(\texttt{H(X) = X mod 10}\), show for each of the following collision resolution techniques, the final hash table after inserting eac...
  • Hashing with BSTs: Consider a hash table with chaining where the elements with the same hash value are inserted in the same binary search tree (BST) instead of a list. Define the abstract data type (ADT) Hash Table. Write the corresponding declaration of such data stru...
  • Add into a table based on hash coalesced with separated zones: Write a function that adds an element of type (char *) to a hash table in which collisions are resolved by applying the hash coalesced with separated zones. **img**ts7-01.png##img##...
  • Search into a table based on hash coalesced with separated zones: Write a function that searches for a key in a hash table using coalesced hashing with 2 separated zones. **img**ts7-01.png##img## We assume the existence of a hash function $$\texttt{int h(element e)}$$ and a function $$\texttt{is_empty}$$ that deter...
  • Add into a table based on hash with separate chaining: Write a function that adds an element to a hash table in which collisions are resolved by separate chaining (insertion at the end of the list)....
  • Add into a table based on coalesced hash without separated zones: Write a function that adds an element of type (char *) to a hash table in which collisions are resolved by applying the hash coalesced without separated zones....
  • Almost uniform hashing function: Consider a hash table with chaining where the elements (string) of same hash value are inserted in a binary search tree (BST) implemented dynamically. Give necessary declarations and write a function that returns an array that contains the number of ...
  • Hashing with queues: Consider a hash table $$\texttt{T[m]}$$ ($$m$$ is a constant) in which collisions are handled by separate chaining so those collide elements are added to a queue. Give the declaration of the data structure to use. Write a function that adds an elemen...
  • Cycles: A linked list is said to contain a $$\texttt{cycle}$$ (named also $$\texttt{loop}$$) if some nodes are visited more than once while traversing the list. If the list does not contain any cycles, the last element points to $$\texttt{null}$$. Examples *...
  • Hash coalesced with separated zones to separate chaining with BSTs: We consider a hash table T$$_1$$[$$m$$] in which collisions are resolved by applying the hash coalesced with 2 separated zones: primary zone of size $$p$$ and a reserve zone of size $$r$$ ($$m=p+r$$). After adding many elements to T$$_1$$, there has ...
  • Hashing with heaps: Consider a hash table T[m] where separate chaining is used such that keys with the same hash value are stored in a heap (dynamically implemented). We assume the existence of a hash h, and that keys in the heap are of type t_Element, and that 2 keys c...
  • Hashing with a special collision function: Consider a hash table T[m] in which collisions are treated as follows: when there is a collision on a cell of index v, we try to use the cell of index v + 1, then v + 4 then v + 9 ... v+$$i^{2}$$ ... where i is the iteration number, until an empty ce...
  • Delete from a table based on hash coalesced with separated zones: Write a function that deletes an element of type (char *) from a hash table in which collisions are resolved by applying the hash coalesced with separated zones. **img**ts7-01.png##img##...

Back to the list of exercises

© Copyright 2006-2024    |    All rights reserved