Add a new HashMap implementation

Adds a new, cleaned up, HashMap implementation.

* Uses Robin Hood Hashing (https://en.wikipedia.org/wiki/Hash_table#Robin_Hood_hashing).
* Keeps elements in a double linked list for simpler, ordered, iteration.
* Allows keeping iterators for later use in removal (Unlike Map<>, it does not do much
  for performance vs keeping the key, but helps replace old code).
* Uses a more modern C++ iterator API, deprecates the old one.
* Supports custom allocator (in case there is a wish to use a paged one).

This class aims to unify all the associative template usage and replace it by this one:
* Map<> (whereas key order does not matter, which is 99% of cases)
* HashMap<>
* OrderedHashMap<>
* OAHashMap<>

4 files changed, 494 insertions, 675 deletions

diff --git a/core/templates/hash_map.h b/core/templates/hash_map.h
index fa5677cc70..55292d3eb5 100644
--- a/core/templates/hash_map.h
+++ b/core/templates/hash_map.h
@@ -31,524 +31,553 @@
 #ifndef HASH_MAP_H
 #define HASH_MAP_H
 
-#include "core/error/error_macros.h"
 #include "core/math/math_funcs.h"
 #include "core/os/memory.h"
-#include "core/string/ustring.h"
 #include "core/templates/hashfuncs.h"
-#include "core/templates/list.h"
+#include "core/templates/paged_allocator.h"
+#include "core/templates/pair.h"
 
 /**
- * @class HashMap
+ * A HashMap implementation that uses open addressing with Robin Hood hashing.
+ * Robin Hood hashing swaps out entries that have a smaller probing distance
+ * than the to-be-inserted entry, that evens out the average probing distance
+ * and enables faster lookups. Backward shift deletion is employed to further
+ * improve the performance and to avoid infinite loops in rare cases.
  *
- * Implementation of a standard Hashing HashMap, for quick lookups of Data associated with a Key.
- * The implementation provides hashers for the default types, if you need a special kind of hasher, provide
- * your own.
- * @param TKey  Key, search is based on it, needs to be hasheable. It is unique in this container.
- * @param TData Data, data associated with the key
- * @param Hasher Hasher object, needs to provide a valid static hash function for TKey
- * @param Comparator comparator object, needs to be able to safely compare two TKey values.
- * It needs to ensure that x == x for any items inserted in the map. Bear in mind that nan != nan when implementing an equality check.
- * @param MIN_HASH_TABLE_POWER Miminum size of the hash table, as a power of two. You rarely need to change this parameter.
- * @param RELATIONSHIP Relationship at which the hash table is resized. if amount of elements is RELATIONSHIP
- * times bigger than the hash table, table is resized to solve this condition. if RELATIONSHIP is zero, table is always MIN_HASH_TABLE_POWER.
+ * Keys and values are stored in a double linked list by insertion order. This
+ * has a slight performance overhead on lookup, which can be mostly compensated
+ * using a paged allocator if required.
  *
+ * The assignment operator copy the pairs from one map to the other.
  */
 
-template <class TKey, class TData, class Hasher = HashMapHasherDefault, class Comparator = HashMapComparatorDefault<TKey>, uint8_t MIN_HASH_TABLE_POWER = 3, uint8_t RELATIONSHIP = 8>
+template <class TKey, class TValue>
+struct HashMapElement {
+	HashMapElement *next = nullptr;
+	HashMapElement *prev = nullptr;
+	KeyValue<TKey, TValue> data;
+	HashMapElement() {}
+	HashMapElement(const TKey &p_key, const TValue &p_value) :
+			data(p_key, p_value) {}
+};
+
+template <class TKey, class TValue,
+		class Hasher = HashMapHasherDefault,
+		class Comparator = HashMapComparatorDefault<TKey>,
+		class Allocator = DefaultTypedAllocator<HashMapElement<TKey, TValue>>>
 class HashMap {
 public:
-	struct Pair {
-		TKey key;
-		TData data;
+	const uint32_t MIN_CAPACITY_INDEX = 2; // Use a prime.
+	const float MAX_OCCUPANCY = 0.75;
+	const uint32_t EMPTY_HASH = 0;
 
-		Pair(const TKey &p_key) :
-				key(p_key),
-				data() {}
-		Pair(const TKey &p_key, const TData &p_data) :
-				key(p_key),
-				data(p_data) {
-		}
-	};
+private:
+	Allocator element_alloc;
+	HashMapElement<TKey, TValue> **elements = nullptr;
+	uint32_t *hashes = nullptr;
+	HashMapElement<TKey, TValue> *head_element = nullptr;
+	HashMapElement<TKey, TValue> *tail_element = nullptr;
 
-	struct Element {
-	private:
-		friend class HashMap;
+	uint32_t capacity_index = 0;
+	uint32_t num_elements = 0;
 
-		uint32_t hash = 0;
-		Element *next = nullptr;
-		Element() {}
-		Pair pair;
+	_FORCE_INLINE_ uint32_t _hash(const TKey &p_key) const {
+		uint32_t hash = Hasher::hash(p_key);
 
-	public:
-		const TKey &key() const {
-			return pair.key;
+		if (unlikely(hash == EMPTY_HASH)) {
+			hash = EMPTY_HASH + 1;
 		}
 
-		TData &value() {
-			return pair.data;
-		}
+		return hash;
+	}
 
-		const TData &value() const {
-			return pair.value();
+	_FORCE_INLINE_ uint32_t _get_probe_length(uint32_t p_pos, uint32_t p_hash, uint32_t p_capacity) const {
+		uint32_t original_pos = p_hash % p_capacity;
+		return (p_pos - original_pos + p_capacity) % p_capacity;
+	}
+
+	bool _lookup_pos(const TKey &p_key, uint32_t &r_pos) const {
+		if (elements == nullptr) {
+			return false; // Failed lookups, no elements
 		}
 
-		Element(const TKey &p_key) :
-				pair(p_key) {}
-		Element(const Element &p_other) :
-				hash(p_other.hash),
-				pair(p_other.pair.key, p_other.pair.data) {}
-	};
+		uint32_t capacity = hash_table_size_primes[capacity_index];
+		uint32_t hash = _hash(p_key);
+		uint32_t pos = hash % capacity;
+		uint32_t distance = 0;
 
-private:
-	Element **hash_table = nullptr;
-	uint8_t hash_table_power = 0;
-	uint32_t elements = 0;
+		while (true) {
+			if (hashes[pos] == EMPTY_HASH) {
+				return false;
+			}
 
-	void make_hash_table() {
-		ERR_FAIL_COND(hash_table);
+			if (distance > _get_probe_length(pos, hashes[pos], capacity)) {
+				return false;
+			}
 
-		hash_table = memnew_arr(Element *, (1 << MIN_HASH_TABLE_POWER));
+			if (hashes[pos] == hash && Comparator::compare(elements[pos]->data.key, p_key)) {
+				r_pos = pos;
+				return true;
+			}
 
-		hash_table_power = MIN_HASH_TABLE_POWER;
-		elements = 0;
-		for (int i = 0; i < (1 << MIN_HASH_TABLE_POWER); i++) {
-			hash_table[i] = nullptr;
+			pos = (pos + 1) % capacity;
+			distance++;
 		}
 	}
 
-	void erase_hash_table() {
-		ERR_FAIL_COND_MSG(elements, "Cannot erase hash table if there are still elements inside.");
+	void _insert_with_hash(uint32_t p_hash, HashMapElement<TKey, TValue> *p_value) {
+		uint32_t capacity = hash_table_size_primes[capacity_index];
+		uint32_t hash = p_hash;
+		HashMapElement<TKey, TValue> *value = p_value;
+		uint32_t distance = 0;
+		uint32_t pos = hash % capacity;
 
-		memdelete_arr(hash_table);
-		hash_table = nullptr;
-		hash_table_power = 0;
-		elements = 0;
-	}
+		while (true) {
+			if (hashes[pos] == EMPTY_HASH) {
+				elements[pos] = value;
+				hashes[pos] = hash;
 
-	void check_hash_table() {
-		int new_hash_table_power = -1;
+				num_elements++;
 
-		if ((int)elements > ((1 << hash_table_power) * RELATIONSHIP)) {
-			/* rehash up */
-			new_hash_table_power = hash_table_power + 1;
-
-			while ((int)elements > ((1 << new_hash_table_power) * RELATIONSHIP)) {
-				new_hash_table_power++;
+				return;
 			}
 
-		} else if ((hash_table_power > (int)MIN_HASH_TABLE_POWER) && ((int)elements < ((1 << (hash_table_power - 1)) * RELATIONSHIP))) {
-			/* rehash down */
-			new_hash_table_power = hash_table_power - 1;
-
-			while ((int)elements < ((1 << (new_hash_table_power - 1)) * RELATIONSHIP)) {
-				new_hash_table_power--;
+			// Not an empty slot, let's check the probing length of the existing one.
+			uint32_t existing_probe_len = _get_probe_length(pos, hashes[pos], capacity);
+			if (existing_probe_len < distance) {
+				SWAP(hash, hashes[pos]);
+				SWAP(value, elements[pos]);
+				distance = existing_probe_len;
 			}
 
-			if (new_hash_table_power < (int)MIN_HASH_TABLE_POWER) {
-				new_hash_table_power = MIN_HASH_TABLE_POWER;
-			}
+			pos = (pos + 1) % capacity;
+			distance++;
 		}
+	}
 
-		if (new_hash_table_power == -1) {
-			return;
-		}
+	void _resize_and_rehash(uint32_t p_new_capacity_index) {
+		uint32_t old_capacity = hash_table_size_primes[capacity_index];
 
-		Element **new_hash_table = memnew_arr(Element *, ((uint64_t)1 << new_hash_table_power));
-		ERR_FAIL_COND_MSG(!new_hash_table, "Out of memory.");
+		// Capacity can't be 0.
+		capacity_index = MAX((uint32_t)MIN_CAPACITY_INDEX, p_new_capacity_index);
 
-		for (int i = 0; i < (1 << new_hash_table_power); i++) {
-			new_hash_table[i] = nullptr;
-		}
+		uint32_t capacity = hash_table_size_primes[capacity_index];
 
-		if (hash_table) {
-			for (int i = 0; i < (1 << hash_table_power); i++) {
-				while (hash_table[i]) {
-					Element *se = hash_table[i];
-					hash_table[i] = se->next;
-					int new_pos = se->hash & ((1 << new_hash_table_power) - 1);
-					se->next = new_hash_table[new_pos];
-					new_hash_table[new_pos] = se;
-				}
-			}
+		HashMapElement<TKey, TValue> **old_elements = elements;
+		uint32_t *old_hashes = hashes;
 
-			memdelete_arr(hash_table);
-		}
-		hash_table = new_hash_table;
-		hash_table_power = new_hash_table_power;
-	}
+		num_elements = 0;
+		hashes = reinterpret_cast<uint32_t *>(Memory::alloc_static(sizeof(uint32_t) * capacity));
+		elements = reinterpret_cast<HashMapElement<TKey, TValue> **>(Memory::alloc_static(sizeof(HashMapElement<TKey, TValue> *) * capacity));
 
-	/* I want to have only one function.. */
-	_FORCE_INLINE_ const Element *get_element(const TKey &p_key) const {
-		uint32_t hash = Hasher::hash(p_key);
-		uint32_t index = hash & ((1 << hash_table_power) - 1);
+		for (uint32_t i = 0; i < capacity; i++) {
+			hashes[i] = 0;
+			elements[i] = nullptr;
+		}
 
-		Element *e = hash_table[index];
+		if (old_capacity == 0) {
+			// Nothing to do.
+			return;
+		}
 
-		while (e) {
-			/* checking hash first avoids comparing key, which may take longer */
-			if (e->hash == hash && Comparator::compare(e->pair.key, p_key)) {
-				/* the pair exists in this hashtable, so just update data */
-				return e;
+		for (uint32_t i = 0; i < old_capacity; i++) {
+			if (old_hashes[i] == EMPTY_HASH) {
+				continue;
 			}
 
-			e = e->next;
+			_insert_with_hash(old_hashes[i], old_elements[i]);
 		}
 
-		return nullptr;
-	}
-
-	Element *create_element(const TKey &p_key) {
-		/* if element doesn't exist, create it */
-		Element *e = memnew(Element(p_key));
-		ERR_FAIL_COND_V_MSG(!e, nullptr, "Out of memory.");
-		uint32_t hash = Hasher::hash(p_key);
-		uint32_t index = hash & ((1 << hash_table_power) - 1);
-		e->next = hash_table[index];
-		e->hash = hash;
-
-		hash_table[index] = e;
-		elements++;
-
-		return e;
+		Memory::free_static(old_elements);
+		Memory::free_static(old_hashes);
 	}
 
-	void copy_from(const HashMap &p_t) {
-		if (&p_t == this) {
-			return; /* much less bother with that */
-		}
+	_FORCE_INLINE_ HashMapElement<TKey, TValue> *_insert(const TKey &p_key, const TValue &p_value, bool p_front_insert = false) {
+		uint32_t capacity = hash_table_size_primes[capacity_index];
+		if (unlikely(elements == nullptr)) {
+			// Allocate on demand to save memory.
 
-		clear();
+			hashes = reinterpret_cast<uint32_t *>(Memory::alloc_static(sizeof(uint32_t) * capacity));
+			elements = reinterpret_cast<HashMapElement<TKey, TValue> **>(Memory::alloc_static(sizeof(HashMapElement<TKey, TValue> *) * capacity));
 
-		if (!p_t.hash_table || p_t.hash_table_power == 0) {
-			return; /* not copying from empty table */
+			for (uint32_t i = 0; i < capacity; i++) {
+				hashes[i] = EMPTY_HASH;
+				elements[i] = nullptr;
+			}
 		}
 
-		hash_table = memnew_arr(Element *, (uint64_t)1 << p_t.hash_table_power);
-		hash_table_power = p_t.hash_table_power;
-		elements = p_t.elements;
-
-		for (int i = 0; i < (1 << p_t.hash_table_power); i++) {
-			hash_table[i] = nullptr;
+		uint32_t pos = 0;
+		bool exists = _lookup_pos(p_key, pos);
 
-			const Element *e = p_t.hash_table[i];
-
-			while (e) {
-				Element *le = memnew(Element(*e)); /* local element */
+		if (exists) {
+			elements[pos]->data.value = p_value;
+			return elements[pos];
+		} else {
+			if (num_elements + 1 > MAX_OCCUPANCY * capacity) {
+				ERR_FAIL_COND_V_MSG(capacity_index + 1 == HASH_TABLE_SIZE_MAX, nullptr, "Hash table maximum capacity reached, aborting insertion.");
+				_resize_and_rehash(capacity_index + 1);
+			}
 
-				/* add to list and reassign pointers */
-				le->next = hash_table[i];
-				hash_table[i] = le;
+			HashMapElement<TKey, TValue> *elem = element_alloc.new_allocation(HashMapElement<TKey, TValue>(p_key, p_value));
 
-				e = e->next;
+			if (tail_element == nullptr) {
+				head_element = elem;
+				tail_element = elem;
+			} else if (p_front_insert) {
+				head_element->prev = elem;
+				elem->next = head_element;
+				head_element = elem;
+			} else {
+				tail_element->next = elem;
+				elem->prev = tail_element;
+				tail_element = elem;
 			}
+
+			uint32_t hash = _hash(p_key);
+			_insert_with_hash(hash, elem);
+			return elem;
 		}
 	}
 
 public:
-	Element *set(const TKey &p_key, const TData &p_data) {
-		return set(Pair(p_key, p_data));
-	}
+	_FORCE_INLINE_ uint32_t get_capacity() const { return hash_table_size_primes[capacity_index]; }
+	_FORCE_INLINE_ uint32_t size() const { return num_elements; }
 
-	Element *set(const Pair &p_pair) {
-		Element *e = nullptr;
-		if (!hash_table) {
-			make_hash_table(); // if no table, make one
-		} else {
-			e = const_cast<Element *>(get_element(p_pair.key));
-		}
+	/* Standard Godot Container API */
 
-		/* if we made it up to here, the pair doesn't exist, create and assign */
+	bool is_empty() const {
+		return num_elements == 0;
+	}
 
-		if (!e) {
-			e = create_element(p_pair.key);
-			if (!e) {
-				return nullptr;
-			}
-			check_hash_table(); // perform mantenience routine
+	void clear() {
+		if (elements == nullptr) {
+			return;
 		}
+		uint32_t capacity = hash_table_size_primes[capacity_index];
+		for (uint32_t i = 0; i < capacity; i++) {
+			if (hashes[i] == EMPTY_HASH) {
+				continue;
+			}
 
-		e->pair.data = p_pair.data;
-		return e;
-	}
+			hashes[i] = EMPTY_HASH;
+			element_alloc.delete_allocation(elements[i]);
+			elements[i] = nullptr;
+		}
 
-	bool has(const TKey &p_key) const {
-		return getptr(p_key) != nullptr;
+		tail_element = nullptr;
+		head_element = nullptr;
+		num_elements = 0;
 	}
 
-	/**
-	 * Get a key from data, return a const reference.
-	 * WARNING: this doesn't check errors, use either getptr and check nullptr, or check
-	 * first with has(key)
-	 */
-
-	const TData &get(const TKey &p_key) const {
-		const TData *res = getptr(p_key);
-		CRASH_COND_MSG(!res, "Map key not found.");
-		return *res;
+	TValue &get(const TKey &p_key) {
+		uint32_t pos = 0;
+		bool exists = _lookup_pos(p_key, pos);
+		CRASH_COND_MSG(!exists, "HashMap key not found.");
+		return elements[pos]->data.value;
 	}
 
-	TData &get(const TKey &p_key) {
-		TData *res = getptr(p_key);
-		CRASH_COND_MSG(!res, "Map key not found.");
-		return *res;
+	const TValue &get(const TKey &p_key) const {
+		uint32_t pos = 0;
+		bool exists = _lookup_pos(p_key, pos);
+		CRASH_COND_MSG(!exists, "HashMap key not found.");
+		return elements[pos]->data.value;
 	}
 
-	/**
-	 * Same as get, except it can return nullptr when item was not found.
-	 * This is mainly used for speed purposes.
-	 */
+	const TValue *getptr(const TKey &p_key) const {
+		uint32_t pos = 0;
+		bool exists = _lookup_pos(p_key, pos);
 
-	_FORCE_INLINE_ TData *getptr(const TKey &p_key) {
-		if (unlikely(!hash_table)) {
-			return nullptr;
+		if (exists) {
+			return &elements[pos]->data.value;
 		}
+		return nullptr;
+	}
 
-		Element *e = const_cast<Element *>(get_element(p_key));
+	TValue *getptr(const TKey &p_key) {
+		uint32_t pos = 0;
+		bool exists = _lookup_pos(p_key, pos);
 
-		if (e) {
-			return &e->pair.data;
+		if (exists) {
+			return &elements[pos]->data.value;
 		}
-
 		return nullptr;
 	}
 
-	_FORCE_INLINE_ const TData *getptr(const TKey &p_key) const {
-		if (unlikely(!hash_table)) {
-			return nullptr;
-		}
+	_FORCE_INLINE_ bool has(const TKey &p_key) const {
+		uint32_t _pos = 0;
+		return _lookup_pos(p_key, _pos);
+	}
 
-		const Element *e = const_cast<Element *>(get_element(p_key));
+	bool erase(const TKey &p_key) {
+		uint32_t pos = 0;
+		bool exists = _lookup_pos(p_key, pos);
 
-		if (e) {
-			return &e->pair.data;
+		if (!exists) {
+			return false;
 		}
 
-		return nullptr;
-	}
+		uint32_t capacity = hash_table_size_primes[capacity_index];
+		uint32_t next_pos = (pos + 1) % capacity;
+		while (hashes[next_pos] != EMPTY_HASH && _get_probe_length(next_pos, hashes[next_pos], capacity) != 0) {
+			SWAP(hashes[next_pos], hashes[pos]);
+			SWAP(elements[next_pos], elements[pos]);
+			pos = next_pos;
+			next_pos = (pos + 1) % capacity;
+		}
 
-	/**
-	 * Same as get, except it can return nullptr when item was not found.
-	 * This version is custom, will take a hash and a custom key (that should support operator==()
-	 */
+		hashes[pos] = EMPTY_HASH;
 
-	template <class C>
-	_FORCE_INLINE_ TData *custom_getptr(C p_custom_key, uint32_t p_custom_hash) {
-		if (unlikely(!hash_table)) {
-			return nullptr;
+		if (head_element == elements[pos]) {
+			head_element = elements[pos]->next;
 		}
 
-		uint32_t hash = p_custom_hash;
-		uint32_t index = hash & ((1 << hash_table_power) - 1);
-
-		Element *e = hash_table[index];
+		if (tail_element == elements[pos]) {
+			tail_element = elements[pos]->prev;
+		}
 
-		while (e) {
-			/* checking hash first avoids comparing key, which may take longer */
-			if (e->hash == hash && Comparator::compare(e->pair.key, p_custom_key)) {
-				/* the pair exists in this hashtable, so just update data */
-				return &e->pair.data;
-			}
+		if (elements[pos]->prev) {
+			elements[pos]->prev->next = elements[pos]->next;
+		}
 
-			e = e->next;
+		if (elements[pos]->next) {
+			elements[pos]->next->prev = elements[pos]->prev;
 		}
 
-		return nullptr;
+		element_alloc.delete_allocation(elements[pos]);
+		elements[pos] = nullptr;
+
+		num_elements--;
+		return true;
 	}
 
-	template <class C>
-	_FORCE_INLINE_ const TData *custom_getptr(C p_custom_key, uint32_t p_custom_hash) const {
-		if (unlikely(!hash_table)) {
-			return nullptr;
+	// Reserves space for a number of elements, useful to avoid many resizes and rehashes.
+	// If adding a known (possibly large) number of elements at once, must be larger than old capacity.
+	void reserve(uint32_t p_new_capacity) {
+		uint32_t new_index = capacity_index;
+
+		while (hash_table_size_primes[new_index] < p_new_capacity) {
+			ERR_FAIL_COND_MSG(new_index + 1 == (uint32_t)HASH_TABLE_SIZE_MAX, nullptr);
+			new_index++;
 		}
 
-		uint32_t hash = p_custom_hash;
-		uint32_t index = hash & ((1 << hash_table_power) - 1);
+		if (new_index == capacity_index) {
+			return;
+		}
+
+		if (elements == nullptr) {
+			capacity_index = new_index;
+			return; // Unallocated yet.
+		}
+		_resize_and_rehash(new_index);
+	}
 
-		const Element *e = hash_table[index];
+	/** Iterator API **/
 
-		while (e) {
-			/* checking hash first avoids comparing key, which may take longer */
-			if (e->hash == hash && Comparator::compare(e->pair.key, p_custom_key)) {
-				/* the pair exists in this hashtable, so just update data */
-				return &e->pair.data;
+	struct Iterator {
+		_FORCE_INLINE_ KeyValue<TKey, TValue> &operator*() const {
+			return E->data;
+		}
+		_FORCE_INLINE_ KeyValue<TKey, TValue> *operator->() const { return &E->data; }
+		_FORCE_INLINE_ Iterator &operator++() {
+			if (E) {
+				E = E->next;
 			}
-
-			e = e->next;
+			return *this;
+		}
+		_FORCE_INLINE_ Iterator &operator--() {
+			if (E) {
+				E = E->prev;
+			}
+			return *this;
 		}
 
-		return nullptr;
-	}
+		_FORCE_INLINE_ bool operator==(const Iterator &b) const { return E == b.E; }
+		_FORCE_INLINE_ bool operator!=(const Iterator &b) const { return E != b.E; }
 
-	/**
-	 * Erase an item, return true if erasing was successful
-	 */
+		_FORCE_INLINE_ operator bool() const {
+			return E != nullptr;
+		}
 
-	bool erase(const TKey &p_key) {
-		if (unlikely(!hash_table)) {
-			return false;
+		_FORCE_INLINE_ Iterator(HashMapElement<TKey, TValue> *p_E) { E = p_E; }
+		_FORCE_INLINE_ Iterator() {}
+		_FORCE_INLINE_ Iterator(const Iterator &p_it) { E = p_it.E; }
+		_FORCE_INLINE_ void operator=(const Iterator &p_it) {
+			E = p_it.E;
 		}
 
-		uint32_t hash = Hasher::hash(p_key);
-		uint32_t index = hash & ((1 << hash_table_power) - 1);
-
-		Element *e = hash_table[index];
-		Element *p = nullptr;
-		while (e) {
-			/* checking hash first avoids comparing key, which may take longer */
-			if (e->hash == hash && Comparator::compare(e->pair.key, p_key)) {
-				if (p) {
-					p->next = e->next;
-				} else {
-					//begin of list
-					hash_table[index] = e->next;
-				}
-
-				memdelete(e);
-				elements--;
-
-				if (elements == 0) {
-					erase_hash_table();
-				} else {
-					check_hash_table();
-				}
-				return true;
+	private:
+		HashMapElement<TKey, TValue> *E = nullptr;
+	};
+
+	struct ConstIterator {
+		_FORCE_INLINE_ const KeyValue<TKey, TValue> &operator*() const {
+			return E->data;
+		}
+		_FORCE_INLINE_ const KeyValue<TKey, TValue> *operator->() const { return &E->data; }
+		_FORCE_INLINE_ ConstIterator &operator++() {
+			if (E) {
+				E = E->next;
+			}
+			return *this;
+		}
+		_FORCE_INLINE_ ConstIterator &operator--() {
+			if (E) {
+				E = E->prev;
 			}
+			return *this;
+		}
+
+		_FORCE_INLINE_ bool operator==(const ConstIterator &b) const { return E == b.E; }
+		_FORCE_INLINE_ bool operator!=(const ConstIterator &b) const { return E != b.E; }
 
-			p = e;
-			e = e->next;
+		_FORCE_INLINE_ operator bool() const {
+			return E != nullptr;
 		}
 
-		return false;
-	}
+		_FORCE_INLINE_ ConstIterator(const HashMapElement<TKey, TValue> *p_E) { E = p_E; }
+		_FORCE_INLINE_ ConstIterator() {}
+		_FORCE_INLINE_ ConstIterator(const ConstIterator &p_it) { E = p_it.E; }
+		_FORCE_INLINE_ void operator=(const ConstIterator &p_it) {
+			E = p_it.E;
+		}
 
-	inline const TData &operator[](const TKey &p_key) const { //constref
+	private:
+		const HashMapElement<TKey, TValue> *E = nullptr;
+	};
 
-		return get(p_key);
+	_FORCE_INLINE_ Iterator begin() {
+		return Iterator(head_element);
+	}
+	_FORCE_INLINE_ Iterator end() {
+		return Iterator(nullptr);
+	}
+	_FORCE_INLINE_ Iterator last() {
+		return Iterator(tail_element);
 	}
-	inline TData &operator[](const TKey &p_key) { //assignment
 
-		Element *e = nullptr;
-		if (!hash_table) {
-			make_hash_table(); // if no table, make one
-		} else {
-			e = const_cast<Element *>(get_element(p_key));
+	_FORCE_INLINE_ Iterator find(const TKey &p_key) {
+		uint32_t pos = 0;
+		bool exists = _lookup_pos(p_key, pos);
+		if (!exists) {
+			return end();
 		}
+		return Iterator(elements[pos]);
+	}
 
-		/* if we made it up to here, the pair doesn't exist, create */
-		if (!e) {
-			e = create_element(p_key);
-			CRASH_COND(!e);
-			check_hash_table(); // perform mantenience routine
+	_FORCE_INLINE_ void remove(const Iterator &p_iter) {
+		if (p_iter) {
+			erase(p_iter->key);
 		}
+	}
 
-		return e->pair.data;
+	_FORCE_INLINE_ ConstIterator begin() const {
+		return ConstIterator(head_element);
+	}
+	_FORCE_INLINE_ ConstIterator end() const {
+		return ConstIterator(nullptr);
+	}
+	_FORCE_INLINE_ ConstIterator last() const {
+		return ConstIterator(tail_element);
 	}
 
-	/**
-	 * Get the next key to p_key, and the first key if p_key is null.
-	 * Returns a pointer to the next key if found, nullptr otherwise.
-	 * Adding/Removing elements while iterating will, of course, have unexpected results, don't do it.
-	 *
-	 * Example:
-	 *
-	 * 	const TKey *k=nullptr;
-	 *
-	 * 	while( (k=table.next(k)) ) {
-	 *
-	 * 		print( *k );
-	 * 	}
-	 *
-	 */
-	const TKey *next(const TKey *p_key) const {
-		if (unlikely(!hash_table)) {
-			return nullptr;
+	_FORCE_INLINE_ ConstIterator find(const TKey &p_key) const {
+		uint32_t pos = 0;
+		bool exists = _lookup_pos(p_key, pos);
+		if (!exists) {
+			return end();
 		}
+		return ConstIterator(elements[pos]);
+	}
 
-		if (!p_key) { /* get the first key */
-
-			for (int i = 0; i < (1 << hash_table_power); i++) {
-				if (hash_table[i]) {
-					return &hash_table[i]->pair.key;
-				}
-			}
-
-		} else { /* get the next key */
+	/* Indexing */
 
-			const Element *e = get_element(*p_key);
-			ERR_FAIL_COND_V_MSG(!e, nullptr, "Invalid key supplied.");
-			if (e->next) {
-				/* if there is a "next" in the list, return that */
-				return &e->next->pair.key;
-			} else {
-				/* go to next elements */
-				uint32_t index = e->hash & ((1 << hash_table_power) - 1);
-				index++;
-				for (int i = index; i < (1 << hash_table_power); i++) {
-					if (hash_table[i]) {
-						return &hash_table[i]->pair.key;
-					}
-				}
-			}
+	const TValue &operator[](const TKey &p_key) const {
+		uint32_t pos = 0;
+		bool exists = _lookup_pos(p_key, pos);
+		CRASH_COND(!exists);
+		return elements[pos]->data.value;
+	}
 
-			/* nothing found, was at end */
+	TValue &operator[](const TKey &p_key) {
+		uint32_t pos = 0;
+		bool exists = _lookup_pos(p_key, pos);
+		if (!exists) {
+			return _insert(p_key, TValue())->data.value;
+		} else {
+			return elements[pos]->data.value;
 		}
-
-		return nullptr; /* nothing found */
 	}
 
-	inline unsigned int size() const {
-		return elements;
-	}
+	/* Insert */
 
-	inline bool is_empty() const {
-		return elements == 0;
+	Iterator insert(const TKey &p_key, const TValue &p_value, bool p_front_insert = false) {
+		return Iterator(_insert(p_key, p_value, p_front_insert));
 	}
 
-	void clear() {
-		/* clean up */
-		if (hash_table) {
-			for (int i = 0; i < (1 << hash_table_power); i++) {
-				while (hash_table[i]) {
-					Element *e = hash_table[i];
-					hash_table[i] = e->next;
-					memdelete(e);
-				}
-			}
+	/* Constructors */
 
-			memdelete_arr(hash_table);
+	HashMap(const HashMap &p_other) {
+		reserve(hash_table_size_primes[p_other.capacity_index]);
+
+		if (p_other.num_elements == 0) {
+			return;
 		}
 
-		hash_table = nullptr;
-		hash_table_power = 0;
-		elements = 0;
+		for (const KeyValue<TKey, TValue> &E : p_other) {
+			insert(E.key, E.value);
+		}
 	}
 
-	void operator=(const HashMap &p_table) {
-		copy_from(p_table);
-	}
+	void operator=(const HashMap &p_other) {
+		if (this == &p_other) {
+			return; // Ignore self assignment.
+		}
+		if (num_elements != 0) {
+			clear();
+		}
 
-	void get_key_list(List<TKey> *r_keys) const {
-		if (unlikely(!hash_table)) {
-			return;
+		reserve(hash_table_size_primes[p_other.capacity_index]);
+
+		if (p_other.elements == nullptr) {
+			return; // Nothing to copy.
 		}
-		for (int i = 0; i < (1 << hash_table_power); i++) {
-			Element *e = hash_table[i];
-			while (e) {
-				r_keys->push_back(e->pair.key);
-				e = e->next;
-			}
+
+		for (const KeyValue<TKey, TValue> &E : p_other) {
+			insert(E.key, E.value);
 		}
 	}
 
-	HashMap() {}
+	HashMap(uint32_t p_initial_capacity) {
+		// Capacity can't be 0.
+		capacity_index = 0;
+		reserve(p_initial_capacity);
+	}
+	HashMap() {
+		capacity_index = MIN_CAPACITY_INDEX;
+	}
 
-	HashMap(const HashMap &p_table) {
-		copy_from(p_table);
+	uint32_t debug_get_hash(uint32_t p_index) {
+		if (num_elements == 0) {
+			return 0;
+		}
+		ERR_FAIL_INDEX_V(p_index, get_capacity(), 0);
+		return hashes[p_index];
+	}
+	Iterator debug_get_element(uint32_t p_index) {
+		if (num_elements == 0) {
+			return Iterator();
+		}
+		ERR_FAIL_INDEX_V(p_index, get_capacity(), Iterator());
+		return Iterator(elements[p_index]);
 	}
 
 	~HashMap() {
 		clear();
+
+		if (elements != nullptr) {
+			Memory::free_static(elements);
+			Memory::free_static(hashes);
+		}
 	}
 };
 
diff --git a/core/templates/hashfuncs.h b/core/templates/hashfuncs.h
index 2a129f97d5..eb73ff4ede 100644
--- a/core/templates/hashfuncs.h
+++ b/core/templates/hashfuncs.h
@@ -31,14 +31,22 @@
 #ifndef HASHFUNCS_H
 #define HASHFUNCS_H
 
+#include "core/math/aabb.h"
 #include "core/math/math_defs.h"
 #include "core/math/math_funcs.h"
+#include "core/math/rect2.h"
+#include "core/math/rect2i.h"
+#include "core/math/vector2.h"
+#include "core/math/vector2i.h"
+#include "core/math/vector3.h"
+#include "core/math/vector3i.h"
 #include "core/object/object_id.h"
 #include "core/string/node_path.h"
 #include "core/string/string_name.h"
 #include "core/string/ustring.h"
 #include "core/templates/rid.h"
 #include "core/typedefs.h"
+
 /**
  * Hashing functions
  */
@@ -178,6 +186,49 @@ struct HashMapHasherDefault {
 	static _FORCE_INLINE_ uint32_t hash(const StringName &p_string_name) { return p_string_name.hash(); }
 	static _FORCE_INLINE_ uint32_t hash(const NodePath &p_path) { return p_path.hash(); }
 
+	static _FORCE_INLINE_ uint32_t hash(const Vector2i &p_vec) {
+		uint32_t h = hash_djb2_one_32(p_vec.x);
+		return hash_djb2_one_32(p_vec.y, h);
+	}
+	static _FORCE_INLINE_ uint32_t hash(const Vector3i &p_vec) {
+		uint32_t h = hash_djb2_one_32(p_vec.x);
+		h = hash_djb2_one_32(p_vec.y, h);
+		return hash_djb2_one_32(p_vec.z, h);
+	}
+
+	static _FORCE_INLINE_ uint32_t hash(const Vector2 &p_vec) {
+		uint32_t h = hash_djb2_one_float(p_vec.x);
+		return hash_djb2_one_float(p_vec.y, h);
+	}
+	static _FORCE_INLINE_ uint32_t hash(const Vector3 &p_vec) {
+		uint32_t h = hash_djb2_one_float(p_vec.x);
+		h = hash_djb2_one_float(p_vec.y, h);
+		return hash_djb2_one_float(p_vec.z, h);
+	}
+
+	static _FORCE_INLINE_ uint32_t hash(const Rect2i &p_rect) {
+		uint32_t h = hash_djb2_one_32(p_rect.position.x);
+		h = hash_djb2_one_32(p_rect.position.y, h);
+		h = hash_djb2_one_32(p_rect.size.x, h);
+		return hash_djb2_one_32(p_rect.size.y, h);
+	}
+
+	static _FORCE_INLINE_ uint32_t hash(const Rect2 &p_rect) {
+		uint32_t h = hash_djb2_one_float(p_rect.position.x);
+		h = hash_djb2_one_float(p_rect.position.y, h);
+		h = hash_djb2_one_float(p_rect.size.x, h);
+		return hash_djb2_one_float(p_rect.size.y, h);
+	}
+
+	static _FORCE_INLINE_ uint32_t hash(const AABB &p_aabb) {
+		uint32_t h = hash_djb2_one_float(p_aabb.position.x);
+		h = hash_djb2_one_float(p_aabb.position.y, h);
+		h = hash_djb2_one_float(p_aabb.position.z, h);
+		h = hash_djb2_one_float(p_aabb.size.x, h);
+		h = hash_djb2_one_float(p_aabb.size.y, h);
+		return hash_djb2_one_float(p_aabb.size.z, h);
+	}
+
 	//static _FORCE_INLINE_ uint32_t hash(const void* p_ptr)  { return uint32_t(uint64_t(p_ptr))*(0x9e3779b1L); }
 };
 
@@ -196,4 +247,38 @@ struct HashMapComparatorDefault {
 	}
 };
 
+constexpr uint32_t HASH_TABLE_SIZE_MAX = 29;
+
+const uint32_t hash_table_size_primes[HASH_TABLE_SIZE_MAX] = {
+	5,
+	13,
+	23,
+	47,
+	97,
+	193,
+	389,
+	769,
+	1543,
+	3079,
+	6151,
+	12289,
+	24593,
+	49157,
+	98317,
+	196613,
+	393241,
+	786433,
+	1572869,
+	3145739,
+	6291469,
+	12582917,
+	25165843,
+	50331653,
+	100663319,
+	201326611,
+	402653189,
+	805306457,
+	1610612741,
+};
+
 #endif // HASHFUNCS_H
diff --git a/core/templates/ordered_hash_map.h b/core/templates/ordered_hash_map.h
deleted file mode 100644
index 3d1f3a08ec..0000000000
--- a/core/templates/ordered_hash_map.h
+++ /dev/null
@@ -1,301 +0,0 @@
-/*************************************************************************/
-/*  ordered_hash_map.h                                                   */
-/*************************************************************************/
-/*                       This file is part of:                           */
-/*                           GODOT ENGINE                                */
-/*                      https://godotengine.org                          */
-/*************************************************************************/
-/* Copyright (c) 2007-2022 Juan Linietsky, Ariel Manzur.                 */
-/* Copyright (c) 2014-2022 Godot Engine contributors (cf. AUTHORS.md).   */
-/*                                                                       */
-/* Permission is hereby granted, free of charge, to any person obtaining */
-/* a copy of this software and associated documentation files (the       */
-/* "Software"), to deal in the Software without restriction, including   */
-/* without limitation the rights to use, copy, modify, merge, publish,   */
-/* distribute, sublicense, and/or sell copies of the Software, and to    */
-/* permit persons to whom the Software is furnished to do so, subject to */
-/* the following conditions:                                             */
-/*                                                                       */
-/* The above copyright notice and this permission notice shall be        */
-/* included in all copies or substantial portions of the Software.       */
-/*                                                                       */
-/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,       */
-/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF    */
-/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/
-/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY  */
-/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,  */
-/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE     */
-/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.                */
-/*************************************************************************/
-
-#ifndef ORDERED_HASH_MAP_H
-#define ORDERED_HASH_MAP_H
-
-#include "core/templates/hash_map.h"
-#include "core/templates/list.h"
-#include "core/templates/pair.h"
-
-/**
- * A hash map which allows to iterate elements in insertion order.
- * Insertion, lookup, deletion have O(1) complexity.
- * The API aims to be consistent with Map rather than HashMap, because the
- * former is more frequently used and is more coherent with the rest of the
- * codebase.
- * Deletion during iteration is safe and will preserve the order.
- */
-template <class K, class V, class Hasher = HashMapHasherDefault, class Comparator = HashMapComparatorDefault<K>, uint8_t MIN_HASH_TABLE_POWER = 3, uint8_t RELATIONSHIP = 8>
-class OrderedHashMap {
-	typedef List<Pair<const K *, V>> InternalList;
-	typedef HashMap<K, typename InternalList::Element *, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP> InternalMap;
-
-	InternalList list;
-	InternalMap map;
-
-public:
-	class Element {
-		friend class OrderedHashMap<K, V, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP>;
-
-		typename InternalList::Element *list_element = nullptr;
-		typename InternalList::Element *prev_element = nullptr;
-		typename InternalList::Element *next_element = nullptr;
-
-		Element(typename InternalList::Element *p_element) {
-			list_element = p_element;
-
-			if (list_element) {
-				next_element = list_element->next();
-				prev_element = list_element->prev();
-			}
-		}
-
-	public:
-		_FORCE_INLINE_ Element() {}
-
-		Element next() const {
-			return Element(next_element);
-		}
-
-		Element prev() const {
-			return Element(prev_element);
-		}
-
-		Element(const Element &other) :
-				list_element(other.list_element),
-				prev_element(other.prev_element),
-				next_element(other.next_element) {
-		}
-
-		void operator=(const Element &other) {
-			list_element = other.list_element;
-			next_element = other.next_element;
-			prev_element = other.prev_element;
-		}
-
-		_FORCE_INLINE_ bool operator==(const Element &p_other) const {
-			return this->list_element == p_other.list_element;
-		}
-		_FORCE_INLINE_ bool operator!=(const Element &p_other) const {
-			return this->list_element != p_other.list_element;
-		}
-
-		operator bool() const {
-			return (list_element != nullptr);
-		}
-
-		const K &key() const {
-			CRASH_COND(!list_element);
-			return *(list_element->get().first);
-		}
-
-		V &value() {
-			CRASH_COND(!list_element);
-			return list_element->get().second;
-		}
-
-		const V &value() const {
-			CRASH_COND(!list_element);
-			return list_element->get().second;
-		}
-
-		V &get() {
-			CRASH_COND(!list_element);
-			return list_element->get().second;
-		}
-
-		const V &get() const {
-			CRASH_COND(!list_element);
-			return list_element->get().second;
-		}
-	};
-
-	class ConstElement {
-		friend class OrderedHashMap<K, V, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP>;
-
-		const typename InternalList::Element *list_element = nullptr;
-
-		ConstElement(const typename InternalList::Element *p_element) :
-				list_element(p_element) {
-		}
-
-	public:
-		_FORCE_INLINE_ ConstElement() {}
-
-		ConstElement(const ConstElement &other) :
-				list_element(other.list_element) {
-		}
-
-		void operator=(const ConstElement &other) {
-			list_element = other.list_element;
-		}
-
-		ConstElement next() const {
-			return ConstElement(list_element ? list_element->next() : nullptr);
-		}
-
-		ConstElement prev() const {
-			return ConstElement(list_element ? list_element->prev() : nullptr);
-		}
-
-		_FORCE_INLINE_ bool operator==(const ConstElement &p_other) const {
-			return this->list_element == p_other.list_element;
-		}
-		_FORCE_INLINE_ bool operator!=(const ConstElement &p_other) const {
-			return this->list_element != p_other.list_element;
-		}
-
-		operator bool() const {
-			return (list_element != nullptr);
-		}
-
-		const K &key() const {
-			CRASH_COND(!list_element);
-			return *(list_element->get().first);
-		}
-
-		const V &value() const {
-			CRASH_COND(!list_element);
-			return list_element->get().second;
-		}
-
-		const V &get() const {
-			CRASH_COND(!list_element);
-			return list_element->get().second;
-		}
-	};
-
-	ConstElement find(const K &p_key) const {
-		typename InternalList::Element *const *list_element = map.getptr(p_key);
-		if (list_element) {
-			return ConstElement(*list_element);
-		}
-		return ConstElement(nullptr);
-	}
-
-	Element find(const K &p_key) {
-		typename InternalList::Element **list_element = map.getptr(p_key);
-		if (list_element) {
-			return Element(*list_element);
-		}
-		return Element(nullptr);
-	}
-
-	Element insert(const K &p_key, const V &p_value) {
-		typename InternalList::Element **list_element = map.getptr(p_key);
-		if (list_element) {
-			(*list_element)->get().second = p_value;
-			return Element(*list_element);
-		}
-		// Incorrectly set the first value of the pair with a value that will
-		// be invalid as soon as we leave this function...
-		typename InternalList::Element *new_element = list.push_back(Pair<const K *, V>(&p_key, p_value));
-		// ...this is needed here in case the hashmap recursively reference itself...
-		typename InternalMap::Element *e = map.set(p_key, new_element);
-		// ...now we can set the right value !
-		new_element->get().first = &e->key();
-
-		return Element(new_element);
-	}
-
-	void erase(Element &p_element) {
-		map.erase(p_element.key());
-		list.erase(p_element.list_element);
-		p_element.list_element = nullptr;
-	}
-
-	bool erase(const K &p_key) {
-		typename InternalList::Element **list_element = map.getptr(p_key);
-		if (list_element) {
-			list.erase(*list_element);
-			map.erase(p_key);
-			return true;
-		}
-		return false;
-	}
-
-	inline bool has(const K &p_key) const {
-		return map.has(p_key);
-	}
-
-	const V &operator[](const K &p_key) const {
-		ConstElement e = find(p_key);
-		CRASH_COND(!e);
-		return e.value();
-	}
-
-	V &operator[](const K &p_key) {
-		Element e = find(p_key);
-		if (!e) {
-			// consistent with Map behaviour
-			e = insert(p_key, V());
-		}
-		return e.value();
-	}
-
-	inline Element front() {
-		return Element(list.front());
-	}
-
-	inline Element back() {
-		return Element(list.back());
-	}
-
-	inline ConstElement front() const {
-		return ConstElement(list.front());
-	}
-
-	inline ConstElement back() const {
-		return ConstElement(list.back());
-	}
-
-	inline bool is_empty() const { return list.is_empty(); }
-	inline int size() const { return list.size(); }
-
-	const void *id() const {
-		return list.id();
-	}
-
-	void clear() {
-		map.clear();
-		list.clear();
-	}
-
-private:
-	void _copy_from(const OrderedHashMap &p_map) {
-		for (ConstElement E = p_map.front(); E; E = E.next()) {
-			insert(E.key(), E.value());
-		}
-	}
-
-public:
-	void operator=(const OrderedHashMap &p_map) {
-		_copy_from(p_map);
-	}
-
-	OrderedHashMap(const OrderedHashMap &p_map) {
-		_copy_from(p_map);
-	}
-
-	_FORCE_INLINE_ OrderedHashMap() {}
-};
-
-#endif // ORDERED_HASH_MAP_H
diff --git a/core/templates/paged_allocator.h b/core/templates/paged_allocator.h
index b9067e2edd..cf5911a847 100644
--- a/core/templates/paged_allocator.h
+++ b/core/templates/paged_allocator.h
@@ -50,6 +50,10 @@ class PagedAllocator {
 	SpinLock spin_lock;
 
 public:
+	enum {
+		DEFAULT_PAGE_SIZE = 4096
+	};
+
 	template <class... Args>
 	T *alloc(const Args &&...p_args) {
 		if (thread_safe) {
@@ -121,7 +125,9 @@ public:
 		page_shift = get_shift_from_power_of_2(page_size);
 	}
 
-	PagedAllocator(uint32_t p_page_size = 4096) { // power of 2 recommended because of alignment with OS page sizes. Even if element is bigger, its still a multiple and get rounded amount of pages
+	// Power of 2 recommended because of alignment with OS page sizes.
+	// Even if element is bigger, it's still a multiple and gets rounded to amount of pages.
+	PagedAllocator(uint32_t p_page_size = DEFAULT_PAGE_SIZE) {
 		configure(p_page_size);
 	}