HashTable vs. Dictionary vs. HashSet

Learn the difference between Hash Table, Dictionary, and HashSet. In addition, look at some of their key features.

Introduction

Before solving any challenges regarding hash tables, it is necessary to look at the implementations of HashTable, Dictionary, and HashSet and see how they are different. All three are built-in data structures in C#. It is also a common misconception that these three structures are the same, but they are very different from each other.

🔍 Hashtable

Hashtable is a collection of key/value pairs arranged based on the hash code of the key. It is the non-generic type of collection, which is defined in System.Collections namespace.

It provides the basic functionality of hashing, along with some helper functions that help in the process of insertion, deletion, and search.

Some of the key features of HashTable are given below:

  • A HashTable stores key-value pairs (examples given below) to map a key to the value:

abc>123abc->123

xyz>456xyz->456

  • HashTable cannot contain duplicate keys. However, it can have duplicate values.
  • HashTable does not store elements in any order either by the key or the value.

  • In HashTable, you can store key/value pairs of the same type or of a different type.

  • On average, the complexity of the basic operation is O(1)O(1). It will go up to O(n)O(n) in the worst-case.

Member functions

Some of the commonly used member functions of Hashtable are given below:

Function Definition
Add (object key, object? value) Adds an element with the specified key and value into the Hashtable
Clear () Removes all elements from the Hashtable
Contains (object key) / ContainsKey (object key) Determines whether the Hashtable contains a specific key
ContainsValue (object value) Determines whether the Hashtable contains a specific value

🔍 Dictionary

Dictionary is a generic collection, which is generally used to store key/value pairs. Dictionary is defined under System.Collection.Generics namespace.

A Dictionary<> is an implementation of IDictionary<> and is implemented using a hash table so the key value pairs are not stored in sorted order.

Some of the key features of Dictionary are given below:

  • A Dictionary stores key-value pairs (examples given below) of same type to map a key to the value:

abc>123abc->123

xyz>456xyz->456

  • Dictionary cannot contain duplicate keys. However, it can have duplicate values.
  • In Dictionary, you can store key/value pairs of the same type only.
  • The data retrieval in Dictionary is faster than Hashtable due to no boxing/unboxing.
  • On average, the complexity of the basic operation is O(1)O(1). It will go up to O(n)O(n) in the worst-case.

Member functions

Some of the commonly used member functions of Dictionary are given below:

Function Definition
Count Returns the # of key-value pairs in a Dictionary
Add (key, value) Adds a key-value pair to the Dictionary
Clear () Removes all key-value pairs from the Dictionary
ContainsKey (object key) Determines whether the Dictionary contains a specific key
Remove(key) Removes the key-value pair from the Dictionary

🔍 HashSet

HashSet is a container in C#, which implements ISet interface. It is also implemented using Hashtable, but it is still quite different from the Hashtable.

Some of the key features of HashSet are listed below:

  • HashSet is a container that implements the ISet interface, and this interface only stores values and not a key-value pair. The value of an element will be its key at the same time.

1>11->1

abc>abcabc->abc

  • HashSet does not allow storing duplicate elements as a set can only contain unique elements.
  • On average, the complexity of the basic operation is O(1)O(1). It will go up to O(n)O(n) in the worst-case.

Member functions

Some of the commonly used member functions of HashSet are given below:

Function Definition
Count Returns the number of elements in HashSet
Remove(T) Removes the specific element in the HashSet
Add(T) Adds an element to the set.
Contains(T) Checks if the specific element is available in HashSet
Remove(T) Removes the specific element from HashSet

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.