Top 31 Hash Tables Interview Questions And Answers

Question 1

What is Hash Table?

Accepted Answer

A **hash table** (hash map) is a data structure that implements an **associative** array abstract data type, a **structure** that can **map keys to values**. Hash tables implement an associative array, which is indexed by arbitrary objects (keys). A hash table uses a **hash function** to compute an **index**, also called a **hash value**, into an **array of buckets** or slots, from which the desired **value** can be found.

![](https://i.stack.imgur.com/0yjYd.png)

Question 2

Provide a simple example of Hash Function

Accepted Answer

A one\-way function is not just a hash function \- a function that loses information \- but a function `f` for which, given an image `y`, it is difficult to find a pre\-image x such that `f(x)=y`.

A very simple example of a hash function that does not use any advanced math, is this simple** parity function**:

```sh
def hash(n: Nat)
  if n.even?
    0
  else
    1
  end
end

```

As you can see, it maps a large input space (the natural numbers) into a small output space (the set `{0, 1}`). And it is one\-way: if I tell you that the result is `1`, you can't tell me what the input was.

This is why they are called one-way: you can compute an image but you can't find a pre-image for a given image.

Question 3

Detect if a List is Cyclic using Hash Table

Accepted Answer

To detect if a list is cyclic, we can check whether a node had been visited before. A natural way is to use a hash table.

**Algorithm**

We go through each node one by one and record each node's reference (or memory address) in a hash table. If the current node is `null`, we have reached the end of the list and it must not be cyclic. If current node’s reference is in the hash table, then return true.

Question 4

What is Hashing?

Accepted Answer

**Hashing** is the practice of using **an algorithm (or hash function)** to map data of _any_ size to a _fixed_ length. This is called a hash value (or sometimes hash code or hash sums or even a hash digest if you’re feeling fancy). In hashing, keys are converted into _hash values_ or _indexes_ by using **hash functions**. Hashing is a one-way function.

Question 5

Explain what is Hash Value?

Accepted Answer

A **Hash Value** (also called as Hashes or Checksum) is a string value (of specific length), which is the result of calculation of a Hashing Algorithm. Hash Values have different uses:

1. Indexing for Hash Tables
2. Determine the Integrity of any Data (which can be a file, folder, email, attachments, downloads etc).

Question 6

What is the difference between _Hashing_ and _Hash Tables_?

Accepted Answer

* **Hashing** is simply the act of turning a data chunk of arbitrary length into a fixed-width value (hereinafter called a hash value) that can be used to represent that chunk in situations where dealing with the original data chunk would be inconvenient.

* A **hash table** is one of those situations; it simply stores references to such data chunks in a table indexed by each chunk's hash value. This way, instead of potentially comparing your desired key chunk against a huge number of chunks, you simply compute the hash value of the key chunk and do a much faster lookup with that hash value.

Question 7

Define what is a Hash Function?

Accepted Answer

A **hash function** is any function that can be used to map data of arbitrary size to fixed-size values. The values returned by a hash function are called _hash values_, hash codes, digests, or simply hashes. The values are used to index a fixed-size table called a hash table. Use of a hash function to index a hash table is called _hashing_ or _scatter storage addressing_.

Mathematically speaking, a **hash function** is usually defined as a mapping from the universe of elements you want to store in the hash table to the range `{0, 1, 2, .., numBuckets - 1}`.

Some properties of Hash Functions are:

* Very fast to compute (nearly constant)
* One way; can not be reversed
* Output does not reveal information on input
* Hard to find collisions (different data with same hash)
* Implementation is based on parity-preserving bit operations (XOR and ADD), multiply, or divide.

Question 8

What is the space complexity of a Hash Table?

Accepted Answer

The space complexity of a datastructure indicates how much space it occupies in relation to the amount of elements it holds. For example a space complexity of `O(1)` would mean that the datastructure alway consumes constant space no matter how many elements you put in there. `O(n)` would mean that the space consumption grows linearly with the amount of elements in it.

A **hashtable** typically has a space complexity of `O(n)`.

Question 9

Explain in simple terms how Hash Tables are implemented?

Accepted Answer

Hash tables are _often_ implemented as **arrays of linked lists**. If we imagine a table storing people's names, after a few insertions it might be laid out in memory as below, where `(enclosed numbers), like (42)` are *hash values* of the _name_.

```js
bucket#  bucket content / linked list

[0]      --> "sue"(780) --> null
[1]      null
[2]      --> "fred"(42) --> "bill"(9282) --> "jane"(42) --> null
[3]      --> "mary"(73) --> null
[4]      null
[5]      --> "masayuki"(75) --> "sarwar"(105) --> null
[6]      --> "margaret"(2626) --> null
[7]      null
[8]      --> "bob"(308) --> null
[9]      null
```
A few points:
  - each of the array entries (indices `[0]`, `[1]`...) is known as a ***bucket***, and starts a - possibly empty - linked list of *values* (aka *elements*, in this example - people's *names*)
  - each value (e.g. `"fred"` with hash `42`) is linked from bucket `[hash % number_of_buckets]` e.g. `42 % 10 == [2]`; `%` is the [*modulo operator*](https://en.wikipedia.org/wiki/Modulo_operation) - the remainder when divided by the number of buckets
  - multiple data values may ***collide*** at and be linked from the same bucket, most often because their hash values collide after the modulo operation (e.g. `42 % 10 == [2]`, and `9282 % 10 == [2]`), but occasionally because the hash values are the same (e.g. `"fred"` and `"jane"` both shown with hash `42` above)
    - most hash tables handle collisions - with slightly reduced performance but no functional confusion - by comparing the full value (here text) of a value being sought or inserted to each value already in the linked list at the hashed-to bucket

- If the table size grows, hash tables implemented as above tend to resize themselves (i.e. create a bigger array of buckets, create new/updated linked lists there-from, delete the old array) to keep the ratio of values to buckets (aka ***load factor***) somewhere in the 0.5 to 1.0 range.
- The buckets don't necessarily have to be lists or arrays, they can be any container type, such as a balanced BST. That means `O(log n)` worst case for collisions. But this is why it's important to choose a good hashing function to avoid putting too many elements into one bucket.

Question 10

What is the significance of load factor of a Hash Table?

Accepted Answer

Any Hash Table has two parameters that affect its performance: _initial capacity_ and _load factor_. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created.

If the table size grows, hash tables tend to resize themselves (i.e. create a bigger array of buckets, create new/updated linked lists there-from, delete the old array) to keep **the ratio of values to buckets (aka load factor)** somewhere in the 0.5 to 1.0 range. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased.

As a general rule, the default load factor `(.75)` (used in Java HashMap) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost.

Top 31 Hash Tables Interview Questions

What is Hash Table?

Provide a simple example of Hash Function

What is the space complexity of a Hash Table?

Explain what is Hash Value?

What is the difference between Hashing and Hash Tables?

Define what is a Hash Function?

What is Hashing?

What is MD5?

What is hashing algorithm? How it works?

How can Hash Functions be used to perform lookups?

What does "bucket entries" mean in the context of a hashtable?

What is Hash Collision?

What is complexity of Hash Table?

What is the significance of load factor of a Hash Table?

Explain in simple terms how Hash Tables are implemented?

What are some main advantages of Tries over Hash Tables

How To Choose Between a Hash Table and a Trie (Prefix Tree)?

Explain some technics to handle collision in Hash Tables

What is the difference between HashMap and HashTable?

Explain when to use Hashing on practice?

Is it possible to decrypt MD5 hashes? Explain.

Explain types of Resistance any Cryptographic Hash Function shall have?

Why all hash functions are "broken"? Explain.

What is a Salt and How Does It Make Password Hashing More Secure?

What is the difference between a Hash Function and a Cryptographic Hash Function?

Compare lookup operation in Trie vs Hash Table

Detect if a List is Cyclic using Hash Table

Remove duplicates from an unsorted Linked List

Find similar elements from two Linked Lists and return the result as a Linked List

How can I pair socks from a pile efficiently?

How come that hash values are not reversible?