Implementations

C++

#include <concepts>
#include <cstdint>
#include <cstdio>
#include <functional>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>
 
template <typename T>
concept HashableKey = requires(T key) {
	{ std::hash<T>{}(key) } -> std::same_as<std::size_t>;
	requires std::is_default_constructible_v<T>;
};
 
template <typename T>
concept HashableValue = std::is_default_constructible_v<T>;
 
template <HashableKey K, HashableValue V> class HashMap {
  private:
	using sz_t = std::size_t; // just shorter to write
 
	enum class State { occupied, empty, deleted };
 
	// a vector creates elems by value init so you'll have these as 0 aka
	// default vals value init is Slot some{}
	struct Slot {
		K key;
		V value;
		// the default would've been first one so occ
		State state = State::empty;
	};
 
	std::vector<Slot> table_;
	sz_t size_ = 0;
	sz_t deleted_ = 0;
 
	static constexpr double max_load_factor = 0.7;
 
	sz_t hash_key(const K &key) const {
		// can prob store it but this is fine
		return std::hash<K>{}(key) % table_.size();
	}
 
	sz_t probe_next(sz_t index) const { return (index + 1) % table_.size(); }
 
	// keep on probing till you hit what we are looking for
	sz_t find_slot_get(const K &key) const {
 
		for (sz_t index = hash_key(key); table_[index].state != State::empty;
		     index = probe_next(index)) {
			const auto &slot = table_[index];
			if (slot.state == State::occupied && slot.key == key) {
				return index;
			}
		}
 
		// INFO: instead of doing -1 ( which'll underflow ) do a SIZE_MAX
		// though technically you can use -1 as proxy for a and even comparisons
		// would work as literals would be implicitly cast to size_T
		return SIZE_MAX;
	}
	// keep on probing till you get an empty one but also rem the
	// first deleted one ( probe till empty to find if inserted ahead in seq )
	sz_t find_slot_insert(const K &key) const {
		sz_t deleted_idx = SIZE_MAX;
		sz_t index = hash_key(key);
		for (; table_[index].state != State::empty; index = probe_next(index)) {
			const auto &slot = table_[index];
 
			// exists already
			if (slot.state == State::occupied && slot.key == key) {
				return index; // allows for a[] get or put semantics
			}
			if (slot.state == State::deleted && deleted_idx == SIZE_MAX) {
				deleted_idx = index;
			}
		}
 
		return deleted_idx == SIZE_MAX ? index : deleted_idx;
	}
	void maybe_rehash() {
		// check for load factor and rehash if needed
		// note that load CAN be more than threshold - the rehash is eventual
		// on the next element
		auto load = static_cast<double>(size_ + deleted_) / table_.size();
		if (load > max_load_factor)
			rehash();
	}
 
	void rehash() {
		// grow in size and recreate it all
		sz_t new_size = table_.size() * 2 + 1;
		std::vector<Slot> new_table(new_size);
 
		// impl trick so I can use my operators[]
		new_table.swap(table_);
 
		// for (auto &entry : table_ | std::views::filter([](auto x) {
		// 	                   return x.state == State::occupied;
		// I wrote this ^ first but it's so verbose compared to what's below
 
		size_ = deleted_ = 0; // they'll be recomputed
		for (auto &entry : new_table) {
			if (entry.state != State::occupied)
				continue;
 
			operator[](entry.key) = entry.value;
		}
	}
 
  public:
	HashMap() : table_(32) {} // so that it doesn't grow on the first insert
 
	sz_t size() const { return size_; }
 
	V &operator[](const K &key) {
		maybe_rehash();
		// NOTE: rem to do this FIRST as index will be invalidated
		// if you do it later
 
		auto index = find_slot_insert(key);
		auto &slot = table_[index];
 
		if (slot.state == State::deleted) {
			deleted_--;
		} else if (slot.state == State::empty) {
			size_++;
		}
		slot.state = State::occupied;
		slot.key = key;
		// value retain whatever it was - this THEN needs me to make sure
		// I default init vals when I delete stuff
 
		return slot.value;
	}
 
	bool contains(const K &key) const {
		auto index = find_slot_get(key);
		return index != SIZE_MAX;
	}
 
	// a get that does not have insert semantics
	const V *find(const K &key) const {
		auto index = find_slot_get(key);
		return index == SIZE_MAX ? nullptr : &(table_[index].value);
	}
 
	// NOTE: a trick to just write the const one and then strip the const
	V *find(const K &key) {
		return const_cast<V *>(std::as_const(*this).find(key));
	}
 
	bool erase(const K &key) {
		auto index = find_slot_get(key);
		if (index == SIZE_MAX)
			return false; // not in table
 
		// NOTE: rem to default contruct the value for a later use in []
		auto &slot = table_[index];
		slot.state = State::deleted;
		slot.value = V{};
		deleted_++;
		size_--; // NOTE: rem the size change too
 
		return true;
	}
};
 
int main() {
	static_assert(HashableKey<int>); // for lsp
 
	HashMap<std::string, int> len_map;
 
	len_map["abc"] = 3;
	(void)len_map.size();
	(void)len_map.contains("abc");
	(void)len_map.find("abc");
 
	auto *a = len_map.find("abc");
	*a = 5;
	std::printf("len is %d\n", len_map["abc"]);
 
	(void)len_map.erase("abc");
}

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.NoSuchElementException;
import java.util.Iterator;
import java.util.List;
 
// WARN:
// ideally this impl should've used nulls to represent empty
// this is more along the lines of my cpp impl as I wrote that first
// not using records and using nulls would be a ligher on memory impl
// not necessarily "cleaner"
 
// WARN: also remember to do .equals instead of ==
 
// a type param cannot be a pair, which makes sense, I mean even in cpp
// it would've been a pair wrapper
record Entry<K, V>(K key, V value) {
}
 
// K is an Object atleast so has an equals defined which may not be good
// but it's there. This doesn't need to be a type constraint just documented
// that hey - your equals need to be good
final class HashMap<K, V> implements Iterable<Entry<K, V>> {
    private static enum State {
        empty,
        occupied,
        deleted
    }
 
    // NOTE: that I don't need to ( but should ) use .key() instead of .key
    // this works because record is priv inside of hashmap so hashmap can
    // access privates of record
 
    // WARN: it's better if this wasn't a record ( to not churn heap )
    // but leaving the impl as it is for now
    private static record Slot<K, V>(K key, V value, State state) {
        // NOTE: you don't NEED the default constructible requirement since
        // values can just be null
 
        // NOTE: static factory using generics, could also have overloaded the ctor
        static <K, V> Slot<K, V> empty() {
            return new Slot<>(null, null, State.empty);
        }
 
        // record will have the full 3 arg ctor implicit
    }
 
    // not specific reason to use ArrayList, I don't really use the resizable
    // properties of it ( we assign a new one when we grow )
    // but easier to use with generics
    private List<Slot<K, V>> table = new ArrayList<>(Collections.nCopies(32, Slot.<K, V>empty()));
    private int size = 0;
    private int deleted = 0;
    private final double loadFactorThreshold = 0.7;
 
    private int hash(K key) {
        var code = key.hashCode() % table.size();
        // WARN: hashcode can be negative
        if (code < 0)
            code += table.size();
        return code;
    }
 
    private int probeNext(int index) {
        return (index + 1) % table.size();
    }
 
    private int indexForPut(final K key) {
        var index = hash(key);
        int deletedIndex = -1;
 
        while (table.get(index).state != State.empty) {
            var slot = table.get(index);
            if (slot.state == State.occupied && slot.key.equals(key)) {
                // NOTE: i often do a -1 here initially, my bias
                return index; // already present
            }
            if (slot.state == State.deleted && deletedIndex == -1) {
                deletedIndex = index;
            }
            index = probeNext(index);
        }
 
        return deletedIndex == -1 ? index : deletedIndex;
    }
 
    private int indexForGet(final K key) {
        var index = hash(key);
 
        while (table.get(index).state != State.empty) {
            var slot = table.get(index);
            if (slot.state == State.occupied && slot.key.equals(key)) {
                return index;
            }
 
            index = probeNext(index);
 
        }
 
        return -1; // not present
    }
 
    private void maybeRehash() {
        double load = (double) (size + deleted) / table.size();
        if (load > loadFactorThreshold) {
            rehash();
        }
    }
 
    private void rehash() {
        var oldTable = table;
        table = new ArrayList<>(Collections.nCopies(2 * oldTable.size() + 1, Slot.<K, V>empty()));
 
        size = deleted = 0;
        for (var slot : oldTable) {
            // WARN: again this'll be a LOT of churn via the puts
            if (slot.state == State.occupied) {
                put(slot.key, slot.value);
            }
        }
    }
 
    public V put(K key, V value) {
        // java semantics to return the old value
        maybeRehash();
 
        var index = indexForPut(key);
        var slot = table.get(index);
        V ret = null;
 
        if (slot.state == State.deleted) {
            deleted--;
            size++;
        } else if (slot.state == State.occupied)
            ret = slot.value;
        else {
            size++;
        }
 
        table.set(index, new Slot<>(key, value, State.occupied));
        return ret;
    }
 
    public V get(final K key) {
        var index = indexForGet(key);
        if (index == -1)
            throw new NoSuchElementException();
        return table.get(index).value;
    }
 
    public boolean containsKey(final K key) {
        return indexForGet(key) != -1;
    }
 
    public V erase(final K key) {
        var index = indexForGet(key);
        if (index == -1)
            throw new NoSuchElementException();
 
        var slot = table.get(index);
        table.set(index, new Slot<>(null, null, State.deleted));
        size--;
        deleted++;
        return slot.value;
    }
 
    @Override
    public Iterator<Entry<K, V>> iterator() {
        // I think I could've also used an array list iterator here
        // but needlessly overcomplicating
        return new Iterator<>() {
            private int index = 0;
            private int seen = 0;
 
            @Override
            public boolean hasNext() {
                return seen < size;
            }
 
            @Override
            public Entry<K, V> next() {
                if (!hasNext())
                    throw new NoSuchElementException();
 
                while (table.get(index).state != State.occupied) {
                    index++;
                }
 
                seen++;
                var slot = table.get(index);
                index++; // NOTE: rem this
                return new Entry<>(slot.key, slot.value);
            }
        };
    }
}

Notes

Core

There’s two

separate chaining where you have a vector of vector and iterate on collision
open addressing is similar except you loop over probe positions on collision

In both cases you resize on a load factor threshold and must rehash the full table again the hash to index mapping would need to change as size has changed.

For open addressing

linear
quad
double hash based probings

minor note: in sep chaining, once you hit the bucket, iter order does not matter while in case of sep chaining it must be same as the insert order though as impls go - usually via an array in sep chaining, the order is the same this is just a LOGICAL correctness related difference.

a “Slot” can be occupied, deleted or empty. Empty means probinh can stop, deleted means you can insert here but lookup still needs to keep on probing.

cpp

concepts

a concept is a compile time constraint on template on templated args so say template<Typename T extends Comparable just like java does it

// previous would've been a static_assert
template<typename T>
concept Integral = std::is_integral_v<T>;
 
// can then use it like
template<Integral T>
class Box{};
 
// or joining multiple concepts
template<typename T>
requires Integral<T> && SomeOther<T> // can think of it like an anon concept
class Box{};
 
// or making a new concept that's sum of multiple concepts
template<typename T>
concept HashKey = Hashable<T> && EqualityComparable<T>;
 
// and then just do
template<HashKey K>
class HashMap{};
 
// NOTE: requires is the JUICE
template<typename T>
// can define any no of vars, it just says say THESE exist
concept Example = requires(T a,T b,int c) {
    // then THESE must hold
    // valid or { valid } -> then result is
    a.size();
    typename T::some_type_in_scope;
    // the first type is supplied as decltype(a+b) implicity
    { a == b } -> std::convertible_to<bool>;
    { a + b } -> std::same_as<T>;
 
    // if you want to check some type bool to be true
    // use requires again
    requires std::is_default_constructible_v<T>;
};
 
// you only need requires when you need a body
concept Example = std::is_default_contructible<T> && ...;

NOTE: this syntax is getting very very confusing

static convs vs constexpr

Note that a const simply can be created at runtime or compile time. A static const a constexpr is basically same I believe.

https://stackoverflow.com/questions/41125651/constexpr-vs-static-const-which-one-to-prefer

Prefer just a constexpr. You do need a static if you want it a shared class member. Note that constexpr is const ( more like a superset of const ) and is inline too always.

Enum class

these are modern enums in cpp

enum class State{
    A,
    B
};
 
State s = State::A;
 
as opposed to leaking A and B in scope.
Also these are not interchangeable with ints now ( must cast if you want )

Lambda what can I omit?

auto min = []{}; is the smallest lambda

Also you can’t do auto x = cond ? lambda 1 : lambda 2 as each lambda has a uniq compiler generated type so auto can’t merge those. You would need an std::func todo the type erasure.:w

making const and non const variations

you can just make the const one and have const stripped away in non const ones

V *find(const K &key) {
    return const_cast<V *>(std::as_const(*this).find(key));
}

as_const would cast it to a const type ( just cast no ctor call ) so this’ll resolve the find and later we use const_cast to remove the const.

Java

Lang

no default values on args via equals, replacement is overloading
java has no way to do a = default ctor when a default ctro is omitted. you must write it in full
making a function cosnt is just not possible
chained assignments are possible in java
new ArrayList<>(10) gives capacity as 10 not size
hashCode() can be negative

Records

records are immutable

Compare

I always forget to do .equals and .compareTo and instead use operators. remember this bias.

Lest I Forget

Hash Map

Implementations

C++

Java

Notes

Core

cpp

concepts

static convs vs constexpr

Enum class

Lambda what can I omit?

making const and non const variations

Java

Lang

Records

Compare