Hash Tables Interview Questions and Answers

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.

Problem

Consider: list1: 1->2->3->4->4->5->6 list2: 1->3->6->4->2->8 Result: list3: 1->2->3->4->6

Solution

1. Create a hash table or set
2. Go through list1 , mark entries as you visit them.

O(N)
3. Go through list2 , mark entries (with different flag) as you visit them.
O(M)

4. Traverse hash table and find all the entries with both flags. Create list3 as you find entries.

O(H)
Total Complexity:
O(N)+ O(M) + O(Max(N,H,M)) => O(N)
Complexity Analysis:
Time Complexity: O(n)

Searching through large quantities of data is a very resource-intensive process. Imagine you’ve got a table listing every inhabitant of a big city, with lots of different fields for each entry (first name, second name, address, etc.). Finding just one term would be very time-consuming and require a lot of computing power. To simplify the process, each entry in the table can be converted into a unique hash value. The search term is then converted to a hash value. This limits the number of letters, digits and symbols that have to be compared, which is much more efficient than searching every field that exists in the data table.

MD5 is a so-called cryptographic hash function. Although MD5 was initially designed to be used as a cryptographic hash function, it has been found to suffer from extensive vulnerabilities. It can still be used as a checksum to verify data integrity, but only against unintentional corruption. This basically means that you can give in any bitstring as input for the function, and you will get out a fixed-size bitstring (128-bit in the case of MD5) as output. The output is usually called "digest". The digest depends solely on the input and nothing else. Thus in itself it can be used as an integrity proof, but not as authenticity, if the underlying hash function has the necessary properties (in this case collision- resistance). This means that for two different outputs the digest itself should be also different. The problem is that the digest's size is fixed, which in turn means that with sufficient number of messages it will always be possible to find a collision (i.e., two different inputs yielding the same output). One should also note that there is nowadays no justification to use MD5, as weaknesses have been

discovered (namely post-fix collision attacks). Also using SHA-256/512 on modern hardware is usually faster then
MD5.

A hash function lies at the heart of a hashing algorithm. Basically, it’s a processing unit that takes in data of arbitrary length and gives you the output of a fixed length – the hash value. But, to get the hash value of a pre- set length, you first need to divide the input data into fixed sized blocks. This is because a hash function takes in data at a fixed-length. These blocks are called ‘data blocks.’ The size of the data block(s) differs from one algorithm to another. But for a particular algorithm, it remains the same. For example, SHA-1 takes in the message/data in blocks of 512-bit only. 99% of the time, the message won’t be in the multiples of 512-bit. For such cases (almost all cases), a technique called Padding is used. Using a padding technique, the entire message is divided into fixed-size data blocks. The hash function is repeated as many times as the number of data blocks. This is how it’s done:

The naive implementation has

O(
n2) as worst case but
O(
1) space complexity.
/*

Without a buffer, we can iterate with two pointers:

* “current” does a normal iteration,
* while “runner” iterates through all prior nodes to check for dups.

Runner will only see one dup per node, because if there were multiple duplicates they would have been removed already.

*/
public static void deleteDups(LinkedListNode head)
{
  if (head == null) return;
  LinkedListNode previous = head;
  LinkedListNode current = previous.next;
  while (current != null)
  {
    LinkedListNode runner = head;
    while (runner != current) {
      // Check for earlier dups
      if (runner.data == current.data)
      {
        LinkedListNode tmp = current.next;
        // remove current
        previous.next = tmp;
        current = tmp;
        // update current to next node
        break;
        // all other dups have already been removed
      }
    runner = runner.next;
  }

if (runner == current) {
  // current not updated - update now
  previous = current;
  current = current.next;
}
}
}

How about using a HashMap? This way it will take

O(
n) time and
O(
n) space. I will write psuedocode.
function removeDup(LinkedList list){
  HashMap map = new HashMap();
  for(i=0; i<list.length;i++)
  if list.get(i) not in map
  map.add(list.get(i))
  else
  list.remove(i)
  end
  end
  end

Of course we assume that HashMap has

O(
1) read and write.

Another solution is to use a mergesort and removes duplicate from start to end of the list. This takes

O(
n log n)

mergesort is

O(
n log n)

removing duplicate from a sorted list is

O(
n)
therefore the entire operation takes
O(
n log n)

A bucket is simply a fast-access location (like an array index) that is the the result of the hash function. The idea with hashing is to turn a complex input value into a different value which can be used to rapidly extract or store data.

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.

Hash tables are O(1) average and amortized time complexity case complexity, however it suffers from O(n) worst case time complexity (when you have only one bucket in the hash table, then the search complexity is O(n) ). A hashtable typically has a space complexity of O(n) . Hash tables suffer from O(n) worst time complexity due to two reasons:

1. If too many elements were hashed into the same key: looking inside this key may take O(n) time (for linked

lists)

2. Once a hash table has passed its load balance - it has to rehash (create a new bigger table, and re-insert each element to the table). However, it is said to be O(1) average and amortized case because:
3. It is very rare that many items will be hashed to the same key if you chose a good hash function and you don't have too big load balance.
4. The rehash operation, which is O(n) , can at most happen after n/2 ops, which are all assumed O(1) : Thus when you sum the average time per op, you get : (n*O(1) + O(n)) / n) = O(1)

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. 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 - 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.

There’s always a chance that two different inputs for hash function will generate the same hash value. This is known as a hash collision. If a collision happens, you just compare the actual objects you are hashing to see if they match. What is the probability of a hash collision? This question is just a general form of the birthday problem from mathematics: Given k randomly generated values, where each value is a non-negative integer less than N, what is the probability that at least two of them are equal? Take the well-known hash function CRC32, for example. If you feed this function the two strings “plumless” and “buckeroo”, it generates the same value. This is known as a hash collision. Assuming your hash values are 32-bit, 64-bit or 160-bit, the following table contains a range of small probabilities:

The input material can be an infinite length, where the output is always 128 bits long (for MD5 hash). This means that an infinite number of input strings will generate the same output. If you pick a random number and divide it by 2 but only write down the remainder, you'll get either a 0 or 1 - even or odd, respectively. Is it possible to take that 0 or 1 and get the original number?

Problem

Yesterday I was pairing the socks from the clean laundry and figured out the way I was doing it is not very efficient. I was doing a naive search — picking one sock and "iterating" the pile in order to find its pair. So, the question is basically given a pile of n pairs of socks, containing 2n elements (assume each sock has exactly one matching pair), what is the best way to pair them up efficiently with up to logarithmic extra space?

Solution

Use sorting. The theoretical limit is O(n) because you need to touch each sock (unless some are already paired somehow). You can achieve O(n) with radix sort. You just need to pick some attributes for the buckets.

i. First you can choose (hers, mine) - split them into 2 piles, ii. then use colors (can have any order for the colors, e.g. alphabetically by color name) - split them into piles by color (remember to keep the initial order from step 1 for all socks in the same pile), iii. then length of the sock, iv. then texture v. And so on... If you can pick a limited number of attributes, but enough attributes that can uniquely identify each pair, you should be done in O(k * n) , which is O(n) if we can consider k is limited. As the architecture of the human brain is completely different than a modern CPU humans can win over CPU algorithms using the fact that "finding a matching pair" can be one operation (Single instruction, multiple data (SIMD)) for a set that isn't too big.

spread_all_socks_on_flat_surface();
while (socks_left_on_a_surface()) {
  // Thanks to human visual SIMD, this is one, quick operation.
  pair = notice_any_matching_pair();
  remove_socks_pair_from_surface(pair);
}
Sorting is a little too much. We don't need order; we just need equality groups. So hashing would be
enough (and faster).

i. For each color of socks, form a pile. Iterate over all socks in your input basket and distribute them onto the color piles. ii. Iterate over each pile and distribute it by some other metric (e.g. pattern) into the second set of piles iii. Recursively apply this scheme until you have distributed all socks onto very small piles that you can visually process immediately

There are multiple techniques available to handle collision: Chaining: In chaining we use array indexes to store the values. If hash code of second value also points to the same index then we replace that index value with an linked list and all values pointing to that index are stored in the linked list and actual array index points to the head of the the linked list. But if there is only one hash code pointing to an index of array then the value is directly stored in that index. Same logic is applied while retrieving the values. This is used in Java HashMap/Hashtable to avoid collisions. Linear probing: This technique is used when we have more index in the table than the values to be stored. Linear probing technique works on the concept of keep incrementing until you find an empty slot. The pseudo code looks like this:

index = h(k)
while( val(index) is occupied)
index = (index+1) mod n
Double hashing technique: In this technique we use two hashing functions h1(k) and h2(k). If the slot at
h1(k) is occupied then the second hashing function h2(k) used to increment the index. The pseudo-code

looks like this:

index = h1(k)
while( val(index) is occupied)
index = (index + h2(k)) mod n

Linear probing and double hashing techniques are part of open addressing technique and it can only be used if available slots are more than the number of items to be added. It takes less memory than chaining because there is no extra structure used here but its slow because of lot of movement happen until we find an empty slot. Also in open addressing technique when an item is removed from a slot we put an tombstone to indicate that the item is removed from here that is why its empty.

Tries and hash tables are used for different things: If all you want is the ability to lookup a word, then a hash table will be faster. A well constructed hash table (i.e. a good hash function and a reasonable load factor) has O(1) lookup time. If you want to find common prefixes, ordered retrieval, or do similar things, then you want a trie. Lookup time in a trie is O(m) : it depends on the length of the string you're looking up. And memory wise: A hash table's overhead is typically a constant multiple of the number of words it contains. That is, in addition to the memory required to store the strings, there is per-string overhead to store the mapping between hash code and string. Memory for a trie is a little more involved. In the worst case, there is one node per character. All those little node allocations start adding up. Imagine a dictionary that contains 200,000 words, and the average word length is five characters. That's a million nodes of overhead.

Problem

I have seen people using these terms interchangeably for the same concept. Does it have no difference at all purely in context of data structures?

Solution

In Computing Science terminology, a map is an associative container mapping from a key to a value. In other words, you can do operations like "for key K remember value V" and later "for key K get the value". A map can be implemented in many ways - for example, with a (optionally balanced) binary tree, or a hash table, or even a contiguous array of structs storing the key/value. A hash table is a structure for storing arbitrary data, and that data does not necessarily consist of a separate key and value. For example, I could have a hash table containing the values { 1, 10, 33, 97 } , which would be their own keys. When there is no value distinct from the key, this is sometimes known as a "set", and with a hash table implementation a hash set. So, a hash table stores elements, each of which need not consist of distinct key and value components, but if it does then it's also a hash map.

1. Use a hash function when you want to compare a value but can't store the plain representation (for any number of reasons). Passwords should fit this use-case very well since you don't want to store them plain-text for security reasons (and shouldn't). But what if you wanted to check a filesystem for pirated music files? It would be impractical to store 3 mb per music file. So instead, take the hash of the file, and store that (md5 would store 16 bytes instead of 3mb). That way, you just hash each file and compare to the stored database of hashes (This doesn't work as well in practice because of re-encoding, changing file headers, etc, but it's an example use-case).
2. Use a hash function when you're checking validity of input data. That's what they are designed for. If you have 2 pieces of input, and want to check to see if they are the same, run both through a hash function. The probability of a collision is astronomically low for small input sizes (assuming a good hash function). That's why it's recommended for passwords. For passwords up to 32 characters, md5 has 4 times the output space. SHA1 has 6 times the output space (approximately). SHA512 has about 16 times the output space. You don't really care what the password was, you care if it's the same as the one that was stored. That's why you should use hashes for passwords.
3. Hash functions are also great for signing data. For example, if you're using HMAC, you sign a piece of data by taking a hash of the data concatenated with a known but not transmitted value (a secret value). So, you send the plain-text and the HMAC hash. Then, the receiver simply hashes the submitted data with the known value and checks to see if it matches the transmitted HMAC. If it's the same, you know it wasn't tampered with by a party without the secret value. This is commonly used in secure cookie systems by HTTP frameworks, as well as in message transmission of data over HTTP where you want some assurance of integrity in the data.

No. MD5 is not encryption (though it may be used as part of some encryption algorithms), it is a one way hash function. Much of the original data is actually "lost" as part of the transformation. Think about this: An MD5 is always 128 bits long. That means that there are 2128 possible MD5 hashes. That is a reasonably large number, and yet it is most definitely finite. And yet, there are an infinite number of possible inputs to a given hash function (and most of them contain more than 128 bits, or a measly 16 bytes). So there are actually an infinite number of possibilities for data that would hash to the same value. The thing that makes hashes interesting is that it is incredibly difficult to find two pieces of data that hash to the same value, and the chances of it happening by accident are almost 0. MD5 has been found to have some weaknesses, such that with some complex mathematics, it may be possible to find a collision without trying out 2128 possible input strings. And the fact that most passwords are short, and people often use common values (like "password" or "secret") means that in some cases, you can make a reasonably good guess at someone's password by Googling for the hash or using a Rainbow table. That is one reason why you should always "salt" hashed passwords, so that two identical values, when hashed, will not hash to the same value. Once a piece of data has been run through a hash function, there is no going back.

The following are the main advantages of tries over hash tables: Tries support ordered iteration, whereas iteration over a hash table will result in a pseudorandom order given by the hash function (also, the order of hash collisions is implementation defined), which is usually meaningless. Tries facilitate longest-prefix matching, but hashing does not, as a consequence of the above. Performing such a "closest fit" find can, depending on implementation, be as quick as an exact find. Tries tend to be faster on average at insertion than hash tables because hash tables must rebuild their index when it becomes full - a very expensive operation. Tries therefore have much better bounded worst case time costs, which is important for latency sensitive programs. By avoiding the hash function, tries are generally faster than hash tables for small keys like integers and pointers.

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.

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 orscatter 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.

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).

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**:

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.

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) .

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.

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. Complexity Analysis: Time Complexity: O(n) Space Complexity: O(n) Time complexity :

O(

n) . We visit each of the n elements in the list at most once. Adding a node to the hash table costs only

O(
1) time.
Space complexity:
O(
n) . The space depends on the number of elements added to the hash table, which
contains at most n elements.
Implementation:
Java

public boolean hasCycle(ListNode head) {
  Set<ListNode> nodesSeen = new HashSet<>();
  while (head != null) {
    if (nodesSeen.contains(head)) {
      return true;
    } else {
      nodesSeen.add(head);
    }
  head = head.next;
}
return false;
}

A hash table can look up individual strings very quickly. It's like a thoroughbred racehorse. That's all it can do. A trie, on the other hand, is a workhorse that can do a lot of things. It'll never be as fast at lookups as a hash table,

but it can do lots of things that the hash table can't do. For example, finding all the words in a hash table that start with "pre" will take O(n) time because you have to search all of the words. With a trie, it takes three probes to find the subtree that contains all of those words, and then all you have to do is traverse that subtree. Sure, the worst case is O(n) , but that's only if all the words in your trie start with "pre".

Every cryptographic hash function is a hash function. But not every hash function is a cryptographic hash. The ideal cryptographic hash function has six main properties:

1. Deterministic: the same message always results in the same hash;
2. Quick: it is quick to compute the hash value for any given message;
3. One-way function: it is infeasible to generate a message from its hash value except by trying all possible

messages;

4. Avalanche effect: a small change to a message should change the hash value so extensively that the new hash value appears uncorrelated with the old hash value;
5. Collision resistant weak collision resistance (given a message m1 it must be difficult to find a different message m2 so that m1 and m2 yield the same hash) strong collision resistance (it should be difficult to find any messages m1 and m2 that yield the same

hash)

6. Pre-image attack resistant: given a hash h it must be difficult to find a message m that yields h when hashed. A cryptographic hash function should resist attacks on its pre-image. Non cryptographic hash functions just try to avoid collisions for non malicious input. In exchange for weaker guarantees they are typically (much) faster.

A salt is a fixed-length cryptographically-strong random value that is added to the input of hash functions to create unique hashes for every input, regardless of the input not being unique. A salt makes a hash function look non-deterministic, which is good as we don't want to reveal password duplications through our hashing. The reason that salts are used is that people tend to choose the same passwords, and not at all randomly. Many used passwords out there are short real words, to make it easy to remember, but this also enables for a dictionary attack (Using a pre-arranged listing of words, such as the entries from the English dictionary, with their computed hash, the attacker easily compares the hashes from a stolen passwords table with every hash on the list. If a match is found, the password then can be deduced). Salting is pointless if you don't have a separate salt for each user. The point of salts is to make breaking the hashes a separate task for each user password; if the salt is the same for all of them then that's not the case.

The pigeonhole principle says that try as hard as you will you can not fit more than 2 pigeons in 2 holes (unless you cut the pigeons up). Similarly you can not fit 2^128 + 1 numbers in 2^128 slots. All hash functions result in a hash of finite size, this means that you can always find a collision if you search through "finite size" + 1 sequences. It's just not feasible to do so.

In cryptography, hash functions provide three separate functions.

1. Collision resistance: How hard is it for someone to find two messages ( any two messages) that hash the same.
2. Preimage Resistance: Given a hash, how hard is it to find another message that hashes the same? Also known as a one way hash function.
3. Second preimage resistance: Given a message, find another message that hashes the same. These properties are related but independent. For example, collision resistance implies second preimage resistance, but not the other way around. For any given application, you will have different requirements, needing one or more of these properties. A hash function for securing passwords on a server will usually only require preimage resistance, while message digests require all three.