[C#] Maps, Hashtables, and Sets

📋 This is my note-taking from what I learned in the course!

• https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.dictionary-2?view=net-8.0
• https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.sorteddictionary-2?view=net-8.0
• https://learn.microsoft.com/en-us/dotnet/fundamentals/runtime-libraries/system-collections-generic-hashset%7Bt%7D
• https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.sortedset-1?view=net-8.0

Maps, Hash Tables, and Sets

Maps

Definition

A map is a collection of key-value pairs where each key is unique.

Main Operations

• get(k): Returns the value associated with key k. If k does not exist, returns null.
• put(k, v): Inserts the key-value pair (k, v) into the map. If k already exists, it updates the value and returns the old value. Otherwise, returns null.
• remove(k): Removes the entry with key k and returns its value. If k does not exist, returns null.
• size(): Returns the number of key-value pairs in the map.
• isEmpty(): Checks if the map is empty.
• entrySet(): Returns a set of all entries in the map.
• keySet(): Returns a set of all keys in the map.
• values(): Returns a collection of all values in the map.

Example Operations

Map<Integer, String> map = new HashMap<>();
map.isEmpty(); // true
map.put(5, "A"); // null
map.put(7, "B"); // null
map.put(2, "C"); // null
map.put(8, "D"); // null
map.put(2, "E"); // "C"
map.get(7); // "B"
map.get(4); // null
map.size(); // 4
map.remove(5); // "A"
map.isEmpty(); // false

Simple List-Based Map

An unsorted list can be used to implement a map. It stores key-value pairs in an arbitrary order. This method is inefficient for large maps but can work for small collections.

List-Based Map Algorithms

get(k) Algorithm

public V get(K key) {
    for (Entry<K, V> entry : list) {
        if (entry.getKey().equals(key)) {
            return entry.getValue();
        }
    }
    return null;
}

put(k, v) Algorithm

public V put(K key, V value) {
    for (Entry<K, V> entry : list) {
        if (entry.getKey().equals(key)) {
            V oldValue = entry.getValue();
            entry.setValue(value);
            return oldValue;
        }
    }
    list.add(new Entry<>(key, value));
    return null;
}

remove(k) Algorithm

public V remove(K key) {
    Iterator<Entry<K, V>> iterator = list.iterator();
    while (iterator.hasNext()) {
        Entry<K, V> entry = iterator.next();
        if (entry.getKey().equals(key)) {
            V value = entry.getValue();
            iterator.remove();
            return value;
        }
    }
    return null;
}

Hash Tables

Definition

A hash table is an efficient way to implement a map using a hash function to index entries.

Hash Function

A hash function maps keys to integers in a fixed range [0, N - 1]. Example:

int hashFunction(int key, int N) {
    return key % N;
}

Collision Handling

When two keys hash to the same index, a collision occurs. Common techniques to handle collisions include:

Separate Chaining

Each bucket in the hash table points to a linked list of entries.

public V get(K key) {
    int index = hashFunction(key, table.length);
    for (Entry<K, V> entry : table[index]) {
        if (entry.getKey().equals(key)) {
            return entry.getValue();
        }
    }
    return null;
}

Linear Probing

Places the colliding item in the next available cell.

public V get(K key) {
    int index = hashFunction(key, table.length);
    while (table[index] != null) {
        if (table[index].getKey().equals(key)) {
            return table[index].getValue();
        }
        index = (index + 1) % table.length;
    }
    return null;
}

Double Hashing

Uses a secondary hash function to find the next available cell.

public V get(K key) {
    int index = hashFunction(key, table.length);
    int step = secondaryHashFunction(key, table.length);
    while (table[index] != null) {
        if (table[index].getKey().equals(key)) {
            return table[index].getValue();
        }
        index = (index + step) % table.length;
    }
    return null;
}

Hash Functions and Compression Functions

• Division Method: h2(y) = y % N
• MAD Method: h2(y) = (a * y + b) % N

Sets and Multimaps

Sets

A set is an unordered collection of unique elements.

Operations

• add(e): Adds element e to the set.
• remove(e): Removes element e from the set.
• contains(e): Checks if element e is in the set.
• size(): Returns the number of elements in the set.
• isEmpty(): Checks if the set is empty.

Example using HashSet in Java

Set<String> set = new HashSet<>();
set.add("apple");
set.add("banana");
set.add("apple"); // Duplicate, not added
set.contains("banana"); // true
set.remove("apple"); // "apple" removed

Multimaps

A multimap allows multiple values for a single key.

Operations

• put(k, v): Adds value v to the key k.
• get(k): Returns a collection of values associated with key k.
• remove(k): Removes all values associated with key k.
• containsKey(k): Checks if the key k exists.

Example using Multimap in Java

Multimap<String, String> multimap = ArrayListMultimap.create();
multimap.put("fruit", "apple");
multimap.put("fruit", "banana");
multimap.put("vegetable", "carrot");
Collection<String> fruits = multimap.get("fruit"); // [apple, banana]
multimap.remove("fruit"); // Removes all values associated with "fruit"

---

Back to Top

See other articles in Category CS