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

23 files changed, 718 insertions, 939 deletions

diff --git a/core/config/project_settings.cpp b/core/config/project_settings.cpp
index 79fa6a0895..2aedbdf45f 100644
--- a/core/config/project_settings.cpp
+++ b/core/config/project_settings.cpp
@@ -1091,7 +1091,7 @@ bool ProjectSettings::has_custom_feature(const String &p_feature) const {
 	return custom_features.has(p_feature);
 }
 
-OrderedHashMap<StringName, ProjectSettings::AutoloadInfo> ProjectSettings::get_autoload_list() const {
+const HashMap<StringName, ProjectSettings::AutoloadInfo> &ProjectSettings::get_autoload_list() const {
 	return autoloads;
 }
 
@@ -1135,13 +1135,13 @@ void ProjectSettings::_bind_methods() {
 
 void ProjectSettings::_add_builtin_input_map() {
 	if (InputMap::get_singleton()) {
-		OrderedHashMap<String, List<Ref<InputEvent>>> builtins = InputMap::get_singleton()->get_builtins();
+		HashMap<String, List<Ref<InputEvent>>> builtins = InputMap::get_singleton()->get_builtins();
 
-		for (OrderedHashMap<String, List<Ref<InputEvent>>>::Element E = builtins.front(); E; E = E.next()) {
+		for (KeyValue<String, List<Ref<InputEvent>>> &E : builtins) {
 			Array events;
 
 			// Convert list of input events into array
-			for (List<Ref<InputEvent>>::Element *I = E.get().front(); I; I = I->next()) {
+			for (List<Ref<InputEvent>>::Element *I = E.value.front(); I; I = I->next()) {
 				events.push_back(I->get());
 			}
 
@@ -1149,7 +1149,7 @@ void ProjectSettings::_add_builtin_input_map() {
 			action["deadzone"] = Variant(0.5f);
 			action["events"] = events;
 
-			String action_name = "input/" + E.key();
+			String action_name = "input/" + E.key;
 			GLOBAL_DEF(action_name, action);
 			input_presets.push_back(action_name);
 		}
diff --git a/core/config/project_settings.h b/core/config/project_settings.h
index 614a11f726..8655526edd 100644
--- a/core/config/project_settings.h
+++ b/core/config/project_settings.h
@@ -33,7 +33,7 @@
 
 #include "core/object/class_db.h"
 #include "core/os/thread_safe.h"
-#include "core/templates/ordered_hash_map.h"
+#include "core/templates/hash_map.h"
 #include "core/templates/set.h"
 
 class ProjectSettings : public Object {
@@ -94,7 +94,7 @@ protected:
 	Set<String> custom_features;
 	Map<StringName, StringName> feature_overrides;
 
-	OrderedHashMap<StringName, AutoloadInfo> autoloads;
+	HashMap<StringName, AutoloadInfo> autoloads;
 
 	String project_data_dir_name;
 
@@ -181,7 +181,7 @@ public:
 
 	bool has_custom_feature(const String &p_feature) const;
 
-	OrderedHashMap<StringName, AutoloadInfo> get_autoload_list() const;
+	const HashMap<StringName, AutoloadInfo> &get_autoload_list() const;
 	void add_autoload(const AutoloadInfo &p_autoload);
 	void remove_autoload(const StringName &p_autoload);
 	bool has_autoload(const StringName &p_autoload) const;
diff --git a/core/input/input.cpp b/core/input/input.cpp
index 40cea2cd80..3a2e50a674 100644
--- a/core/input/input.cpp
+++ b/core/input/input.cpp
@@ -636,21 +636,21 @@ void Input::_parse_input_event_impl(const Ref<InputEvent> &p_event, bool p_is_em
 		}
 	}
 
-	for (OrderedHashMap<StringName, InputMap::Action>::ConstElement E = InputMap::get_singleton()->get_action_map().front(); E; E = E.next()) {
-		if (InputMap::get_singleton()->event_is_action(p_event, E.key())) {
+	for (const KeyValue<StringName, InputMap::Action> &E : InputMap::get_singleton()->get_action_map()) {
+		if (InputMap::get_singleton()->event_is_action(p_event, E.key)) {
 			// If not echo and action pressed state has changed
-			if (!p_event->is_echo() && is_action_pressed(E.key(), false) != p_event->is_action_pressed(E.key())) {
+			if (!p_event->is_echo() && is_action_pressed(E.key, false) != p_event->is_action_pressed(E.key)) {
 				Action action;
 				action.physics_frame = Engine::get_singleton()->get_physics_frames();
 				action.process_frame = Engine::get_singleton()->get_process_frames();
-				action.pressed = p_event->is_action_pressed(E.key());
+				action.pressed = p_event->is_action_pressed(E.key);
 				action.strength = 0.0f;
 				action.raw_strength = 0.0f;
-				action.exact = InputMap::get_singleton()->event_is_action(p_event, E.key(), true);
-				action_state[E.key()] = action;
+				action.exact = InputMap::get_singleton()->event_is_action(p_event, E.key, true);
+				action_state[E.key] = action;
 			}
-			action_state[E.key()].strength = p_event->get_action_strength(E.key());
-			action_state[E.key()].raw_strength = p_event->get_action_raw_strength(E.key());
+			action_state[E.key].strength = p_event->get_action_strength(E.key);
+			action_state[E.key].raw_strength = p_event->get_action_raw_strength(E.key);
 		}
 	}
 
diff --git a/core/input/input_map.cpp b/core/input/input_map.cpp
index ab94c00999..51c1cf9608 100644
--- a/core/input/input_map.cpp
+++ b/core/input/input_map.cpp
@@ -119,8 +119,8 @@ List<StringName> InputMap::get_actions() const {
 		return actions;
 	}
 
-	for (OrderedHashMap<StringName, Action>::Element E = input_map.front(); E; E = E.next()) {
-		actions.push_back(E.key());
+	for (const KeyValue<StringName, Action> &E : input_map) {
+		actions.push_back(E.key);
 	}
 
 	return actions;
@@ -203,12 +203,12 @@ Array InputMap::_action_get_events(const StringName &p_action) {
 }
 
 const List<Ref<InputEvent>> *InputMap::action_get_events(const StringName &p_action) {
-	const OrderedHashMap<StringName, Action>::Element E = input_map.find(p_action);
+	HashMap<StringName, Action>::Iterator E = input_map.find(p_action);
 	if (!E) {
 		return nullptr;
 	}
 
-	return &E.get().inputs;
+	return &E->value.inputs;
 }
 
 bool InputMap::event_is_action(const Ref<InputEvent> &p_event, const StringName &p_action, bool p_exact_match) const {
@@ -216,7 +216,7 @@ bool InputMap::event_is_action(const Ref<InputEvent> &p_event, const StringName
 }
 
 bool InputMap::event_get_action_status(const Ref<InputEvent> &p_event, const StringName &p_action, bool p_exact_match, bool *r_pressed, float *r_strength, float *r_raw_strength) const {
-	OrderedHashMap<StringName, Action>::Element E = input_map.find(p_action);
+	HashMap<StringName, Action>::Iterator E = input_map.find(p_action);
 	ERR_FAIL_COND_V_MSG(!E, false, suggest_actions(p_action));
 
 	Ref<InputEventAction> input_event_action = p_event;
@@ -235,11 +235,11 @@ bool InputMap::event_get_action_status(const Ref<InputEvent> &p_event, const Str
 		return input_event_action->get_action() == p_action;
 	}
 
-	List<Ref<InputEvent>>::Element *event = _find_event(E.get(), p_event, p_exact_match, r_pressed, r_strength, r_raw_strength);
+	List<Ref<InputEvent>>::Element *event = _find_event(E->value, p_event, p_exact_match, r_pressed, r_strength, r_raw_strength);
 	return event != nullptr;
 }
 
-const OrderedHashMap<StringName, InputMap::Action> &InputMap::get_action_map() const {
+const HashMap<StringName, InputMap::Action> &InputMap::get_action_map() const {
 	return input_map;
 }
 
@@ -360,7 +360,7 @@ String InputMap::get_builtin_display_name(const String &p_name) const {
 	return p_name;
 }
 
-const OrderedHashMap<String, List<Ref<InputEvent>>> &InputMap::get_builtins() {
+const HashMap<String, List<Ref<InputEvent>>> &InputMap::get_builtins() {
 	// Return cache if it has already been built.
 	if (default_builtin_cache.size()) {
 		return default_builtin_cache;
@@ -686,19 +686,19 @@ const OrderedHashMap<String, List<Ref<InputEvent>>> &InputMap::get_builtins() {
 	return default_builtin_cache;
 }
 
-const OrderedHashMap<String, List<Ref<InputEvent>>> &InputMap::get_builtins_with_feature_overrides_applied() {
+const HashMap<String, List<Ref<InputEvent>>> &InputMap::get_builtins_with_feature_overrides_applied() {
 	if (default_builtin_with_overrides_cache.size() > 0) {
 		return default_builtin_with_overrides_cache;
 	}
 
-	OrderedHashMap<String, List<Ref<InputEvent>>> builtins = get_builtins();
+	HashMap<String, List<Ref<InputEvent>>> builtins = get_builtins();
 
 	// Get a list of all built in inputs which are valid overrides for the OS
 	// Key = builtin name (e.g. ui_accept)
 	// Value = override/feature names (e.g. macos, if it was defined as "ui_accept.macos" and the platform supports that feature)
 	Map<String, Vector<String>> builtins_with_overrides;
-	for (OrderedHashMap<String, List<Ref<InputEvent>>>::Element E = builtins.front(); E; E = E.next()) {
-		String fullname = E.key();
+	for (const KeyValue<String, List<Ref<InputEvent>>> &E : builtins) {
+		String fullname = E.key;
 
 		Vector<String> split = fullname.split(".");
 		String name = split[0];
@@ -709,8 +709,8 @@ const OrderedHashMap<String, List<Ref<InputEvent>>> &InputMap::get_builtins_with
 		}
 	}
 
-	for (OrderedHashMap<String, List<Ref<InputEvent>>>::Element E = builtins.front(); E; E = E.next()) {
-		String fullname = E.key();
+	for (const KeyValue<String, List<Ref<InputEvent>>> &E : builtins) {
+		String fullname = E.key;
 
 		Vector<String> split = fullname.split(".");
 		String name = split[0];
@@ -726,22 +726,22 @@ const OrderedHashMap<String, List<Ref<InputEvent>>> &InputMap::get_builtins_with
 			continue;
 		}
 
-		default_builtin_with_overrides_cache.insert(name, E.value());
+		default_builtin_with_overrides_cache.insert(name, E.value);
 	}
 
 	return default_builtin_with_overrides_cache;
 }
 
 void InputMap::load_default() {
-	OrderedHashMap<String, List<Ref<InputEvent>>> builtins = get_builtins_with_feature_overrides_applied();
+	HashMap<String, List<Ref<InputEvent>>> builtins = get_builtins_with_feature_overrides_applied();
 
-	for (OrderedHashMap<String, List<Ref<InputEvent>>>::Element E = builtins.front(); E; E = E.next()) {
-		String name = E.key();
+	for (const KeyValue<String, List<Ref<InputEvent>>> &E : builtins) {
+		String name = E.key;
 
 		add_action(name);
 
-		List<Ref<InputEvent>> inputs = E.get();
-		for (List<Ref<InputEvent>>::Element *I = inputs.front(); I; I = I->next()) {
+		const List<Ref<InputEvent>> &inputs = E.value;
+		for (const List<Ref<InputEvent>>::Element *I = inputs.front(); I; I = I->next()) {
 			Ref<InputEventKey> iek = I->get();
 
 			// For the editor, only add keyboard actions.
diff --git a/core/input/input_map.h b/core/input/input_map.h
index 79b4d1038f..2400a4a3f7 100644
--- a/core/input/input_map.h
+++ b/core/input/input_map.h
@@ -34,7 +34,7 @@
 #include "core/input/input_event.h"
 #include "core/object/class_db.h"
 #include "core/object/object.h"
-#include "core/templates/ordered_hash_map.h"
+#include "core/templates/hash_map.h"
 
 class InputMap : public Object {
 	GDCLASS(InputMap, Object);
@@ -54,9 +54,9 @@ public:
 private:
 	static InputMap *singleton;
 
-	mutable OrderedHashMap<StringName, Action> input_map;
-	OrderedHashMap<String, List<Ref<InputEvent>>> default_builtin_cache;
-	OrderedHashMap<String, List<Ref<InputEvent>>> default_builtin_with_overrides_cache;
+	mutable HashMap<StringName, Action> input_map;
+	HashMap<String, List<Ref<InputEvent>>> default_builtin_cache;
+	HashMap<String, List<Ref<InputEvent>>> default_builtin_with_overrides_cache;
 
 	List<Ref<InputEvent>>::Element *_find_event(Action &p_action, const Ref<InputEvent> &p_event, bool p_exact_match = false, bool *r_pressed = nullptr, float *r_strength = nullptr, float *r_raw_strength = nullptr) const;
 
@@ -85,7 +85,7 @@ public:
 	bool event_is_action(const Ref<InputEvent> &p_event, const StringName &p_action, bool p_exact_match = false) const;
 	bool event_get_action_status(const Ref<InputEvent> &p_event, const StringName &p_action, bool p_exact_match = false, bool *r_pressed = nullptr, float *r_strength = nullptr, float *r_raw_strength = nullptr) const;
 
-	const OrderedHashMap<StringName, Action> &get_action_map() const;
+	const HashMap<StringName, Action> &get_action_map() const;
 	void load_from_project_settings();
 	void load_default();
 
@@ -93,8 +93,8 @@ public:
 
 	String get_builtin_display_name(const String &p_name) const;
 	// Use an Ordered Map so insertion order is preserved. We want the elements to be 'grouped' somewhat.
-	const OrderedHashMap<String, List<Ref<InputEvent>>> &get_builtins();
-	const OrderedHashMap<String, List<Ref<InputEvent>>> &get_builtins_with_feature_overrides_applied();
+	const HashMap<String, List<Ref<InputEvent>>> &get_builtins();
+	const HashMap<String, List<Ref<InputEvent>>> &get_builtins_with_feature_overrides_applied();
 
 	InputMap();
 	~InputMap();
diff --git a/core/io/config_file.cpp b/core/io/config_file.cpp
index bc24cac955..dd0191f43f 100644
--- a/core/io/config_file.cpp
+++ b/core/io/config_file.cpp
@@ -73,7 +73,7 @@ void ConfigFile::set_value(const String &p_section, const String &p_key, const V
 
 	} else {
 		if (!values.has(p_section)) {
-			values[p_section] = OrderedHashMap<String, Variant>();
+			values[p_section] = HashMap<String, Variant>();
 		}
 
 		values[p_section][p_key] = p_value;
@@ -102,16 +102,16 @@ bool ConfigFile::has_section_key(const String &p_section, const String &p_key) c
 }
 
 void ConfigFile::get_sections(List<String> *r_sections) const {
-	for (OrderedHashMap<String, OrderedHashMap<String, Variant>>::ConstElement E = values.front(); E; E = E.next()) {
-		r_sections->push_back(E.key());
+	for (const KeyValue<String, HashMap<String, Variant>> &E : values) {
+		r_sections->push_back(E.key);
 	}
 }
 
 void ConfigFile::get_section_keys(const String &p_section, List<String> *r_keys) const {
 	ERR_FAIL_COND_MSG(!values.has(p_section), vformat("Cannot get keys from nonexistent section \"%s\".", p_section));
 
-	for (OrderedHashMap<String, Variant>::ConstElement E = values[p_section].front(); E; E = E.next()) {
-		r_keys->push_back(E.key());
+	for (const KeyValue<String, Variant> &E : values[p_section]) {
+		r_keys->push_back(E.key);
 	}
 }
 
@@ -174,18 +174,21 @@ Error ConfigFile::save_encrypted_pass(const String &p_path, const String &p_pass
 }
 
 Error ConfigFile::_internal_save(Ref<FileAccess> file) {
-	for (OrderedHashMap<String, OrderedHashMap<String, Variant>>::Element E = values.front(); E; E = E.next()) {
-		if (E != values.front()) {
+	bool first = true;
+	for (const KeyValue<String, HashMap<String, Variant>> &E : values) {
+		if (first) {
+			first = false;
+		} else {
 			file->store_string("\n");
 		}
-		if (!E.key().is_empty()) {
-			file->store_string("[" + E.key() + "]\n\n");
+		if (!E.key.is_empty()) {
+			file->store_string("[" + E.key + "]\n\n");
 		}
 
-		for (OrderedHashMap<String, Variant>::Element F = E.get().front(); F; F = F.next()) {
+		for (const KeyValue<String, Variant> &F : E.value) {
 			String vstr;
-			VariantWriter::write_to_string(F.get(), vstr);
-			file->store_string(F.key().property_name_encode() + "=" + vstr + "\n");
+			VariantWriter::write_to_string(F.value, vstr);
+			file->store_string(F.key.property_name_encode() + "=" + vstr + "\n");
 		}
 	}
 
diff --git a/core/io/config_file.h b/core/io/config_file.h
index 7a52b0e16a..3b07ec52f5 100644
--- a/core/io/config_file.h
+++ b/core/io/config_file.h
@@ -33,13 +33,13 @@
 
 #include "core/io/file_access.h"
 #include "core/object/ref_counted.h"
-#include "core/templates/ordered_hash_map.h"
+#include "core/templates/hash_map.h"
 #include "core/variant/variant_parser.h"
 
 class ConfigFile : public RefCounted {
 	GDCLASS(ConfigFile, RefCounted);
 
-	OrderedHashMap<String, OrderedHashMap<String, Variant>> values;
+	HashMap<String, HashMap<String, Variant>> values;
 
 	PackedStringArray _get_sections() const;
 	PackedStringArray _get_section_keys(const String &p_section) const;
diff --git a/core/io/missing_resource.cpp b/core/io/missing_resource.cpp
index 7aae6c6f0a..29814cdeb3 100644
--- a/core/io/missing_resource.cpp
+++ b/core/io/missing_resource.cpp
@@ -53,8 +53,8 @@ bool MissingResource::_get(const StringName &p_name, Variant &r_ret) const {
 }
 
 void MissingResource::_get_property_list(List<PropertyInfo> *p_list) const {
-	for (OrderedHashMap<StringName, Variant>::ConstElement E = properties.front(); E; E = E.next()) {
-		p_list->push_back(PropertyInfo(E.value().get_type(), E.key()));
+	for (const KeyValue<StringName, Variant> &E : properties) {
+		p_list->push_back(PropertyInfo(E.value.get_type(), E.key));
 	}
 }
 
diff --git a/core/io/missing_resource.h b/core/io/missing_resource.h
index e87efe1a98..6536a4119b 100644
--- a/core/io/missing_resource.h
+++ b/core/io/missing_resource.h
@@ -38,7 +38,7 @@
 
 class MissingResource : public Resource {
 	GDCLASS(MissingResource, Resource)
-	OrderedHashMap<StringName, Variant> properties;
+	HashMap<StringName, Variant> properties;
 
 	String original_class;
 	bool recording_properties = false;
diff --git a/core/io/resource.cpp b/core/io/resource.cpp
index e6535c67a4..e81382b72e 100644
--- a/core/io/resource.cpp
+++ b/core/io/resource.cpp
@@ -478,10 +478,8 @@ void ResourceCache::clear() {
 	if (resources.size()) {
 		ERR_PRINT("Resources still in use at exit (run with --verbose for details).");
 		if (OS::get_singleton()->is_stdout_verbose()) {
-			const String *K = nullptr;
-			while ((K = resources.next(K))) {
-				Resource *r = resources[*K];
-				print_line(vformat("Resource still in use: %s (%s)", *K, r->get_class()));
+			for (const KeyValue<String, Resource *> &E : resources) {
+				print_line(vformat("Resource still in use: %s (%s)", E.key, E.value->get_class()));
 			}
 		}
 	}
@@ -516,10 +514,8 @@ Resource *ResourceCache::get(const String &p_path) {
 
 void ResourceCache::get_cached_resources(List<Ref<Resource>> *p_resources) {
 	lock.read_lock();
-	const String *K = nullptr;
-	while ((K = resources.next(K))) {
-		Resource *r = resources[*K];
-		p_resources->push_back(Ref<Resource>(r));
+	for (KeyValue<String, Resource *> &E : resources) {
+		p_resources->push_back(Ref<Resource>(E.value));
 	}
 	lock.read_unlock();
 }
@@ -544,9 +540,8 @@ void ResourceCache::dump(const char *p_file, bool p_short) {
 		ERR_FAIL_COND_MSG(f.is_null(), "Cannot create file at path '" + String::utf8(p_file) + "'.");
 	}
 
-	const String *K = nullptr;
-	while ((K = resources.next(K))) {
-		Resource *r = resources[*K];
+	for (KeyValue<String, Resource *> &E : resources) {
+		Resource *r = E.value;
 
 		if (!type_count.has(r->get_class())) {
 			type_count[r->get_class()] = 0;
diff --git a/core/io/resource_uid.cpp b/core/io/resource_uid.cpp
index 515b7c710e..fc324a26da 100644
--- a/core/io/resource_uid.cpp
+++ b/core/io/resource_uid.cpp
@@ -149,12 +149,12 @@ Error ResourceUID::save_to_cache() {
 
 	cache_entries = 0;
 
-	for (OrderedHashMap<ID, Cache>::Element E = unique_ids.front(); E; E = E.next()) {
-		f->store_64(E.key());
-		uint32_t s = E.get().cs.length();
+	for (KeyValue<ID, Cache> &E : unique_ids) {
+		f->store_64(E.key);
+		uint32_t s = E.value.cs.length();
 		f->store_32(s);
-		f->store_buffer((const uint8_t *)E.get().cs.ptr(), s);
-		E.get().saved_to_cache = true;
+		f->store_buffer((const uint8_t *)E.value.cs.ptr(), s);
+		E.value.saved_to_cache = true;
 		cache_entries++;
 	}
 
@@ -202,8 +202,8 @@ Error ResourceUID::update_cache() {
 	MutexLock l(mutex);
 
 	Ref<FileAccess> f;
-	for (OrderedHashMap<ID, Cache>::Element E = unique_ids.front(); E; E = E.next()) {
-		if (!E.get().saved_to_cache) {
+	for (KeyValue<ID, Cache> &E : unique_ids) {
+		if (!E.value.saved_to_cache) {
 			if (f.is_null()) {
 				f = FileAccess::open(get_cache_file(), FileAccess::READ_WRITE); //append
 				if (f.is_null()) {
@@ -211,11 +211,11 @@ Error ResourceUID::update_cache() {
 				}
 				f->seek_end();
 			}
-			f->store_64(E.key());
-			uint32_t s = E.get().cs.length();
+			f->store_64(E.key);
+			uint32_t s = E.value.cs.length();
 			f->store_32(s);
-			f->store_buffer((const uint8_t *)E.get().cs.ptr(), s);
-			E.get().saved_to_cache = true;
+			f->store_buffer((const uint8_t *)E.value.cs.ptr(), s);
+			E.value.saved_to_cache = true;
 			cache_entries++;
 		}
 	}
diff --git a/core/io/resource_uid.h b/core/io/resource_uid.h
index 0b7ffdf6d0..da42553cf5 100644
--- a/core/io/resource_uid.h
+++ b/core/io/resource_uid.h
@@ -33,7 +33,7 @@
 
 #include "core/object/ref_counted.h"
 #include "core/string/string_name.h"
-#include "core/templates/ordered_hash_map.h"
+#include "core/templates/hash_map.h"
 
 class ResourceUID : public Object {
 	GDCLASS(ResourceUID, Object)
@@ -53,7 +53,7 @@ private:
 		bool saved_to_cache = false;
 	};
 
-	OrderedHashMap<ID, Cache> unique_ids; //unique IDs and utf8 paths (less memory used)
+	HashMap<ID, Cache> unique_ids; //unique IDs and utf8 paths (less memory used)
 	static ResourceUID *singleton;
 
 	uint32_t cache_entries = 0;
diff --git a/core/object/class_db.cpp b/core/object/class_db.cpp
index 593f27b7cf..d0fcde832b 100644
--- a/core/object/class_db.cpp
+++ b/core/object/class_db.cpp
@@ -90,10 +90,8 @@ bool ClassDB::is_parent_class(const StringName &p_class, const StringName &p_inh
 void ClassDB::get_class_list(List<StringName> *p_classes) {
 	OBJTYPE_RLOCK;
 
-	const StringName *k = nullptr;
-
-	while ((k = classes.next(k))) {
-		p_classes->push_back(*k);
+	for (const KeyValue<StringName, ClassInfo> &E : classes) {
+		p_classes->push_back(E.key);
 	}
 
 	p_classes->sort();
@@ -102,11 +100,9 @@ void ClassDB::get_class_list(List<StringName> *p_classes) {
 void ClassDB::get_inheriters_from_class(const StringName &p_class, List<StringName> *p_classes) {
 	OBJTYPE_RLOCK;
 
-	const StringName *k = nullptr;
-
-	while ((k = classes.next(k))) {
-		if (*k != p_class && _is_parent_class(*k, p_class)) {
-			p_classes->push_back(*k);
+	for (const KeyValue<StringName, ClassInfo> &E : classes) {
+		if (E.key != p_class && _is_parent_class(E.key, p_class)) {
+			p_classes->push_back(E.key);
 		}
 	}
 }
@@ -114,11 +110,9 @@ void ClassDB::get_inheriters_from_class(const StringName &p_class, List<StringNa
 void ClassDB::get_direct_inheriters_from_class(const StringName &p_class, List<StringName> *p_classes) {
 	OBJTYPE_RLOCK;
 
-	const StringName *k = nullptr;
-
-	while ((k = classes.next(k))) {
-		if (*k != p_class && _get_parent_class(*k) == p_class) {
-			p_classes->push_back(*k);
+	for (const KeyValue<StringName, ClassInfo> &E : classes) {
+		if (E.key != p_class && _get_parent_class(E.key) == p_class) {
+			p_classes->push_back(E.key);
 		}
 	}
 }
@@ -172,17 +166,12 @@ uint64_t ClassDB::get_api_hash(APIType p_api) {
 
 	uint64_t hash = hash_djb2_one_64(HashMapHasherDefault::hash(VERSION_FULL_CONFIG));
 
-	List<StringName> names;
-
-	const StringName *k = nullptr;
+	List<StringName> class_list;
+	ClassDB::get_class_list(&class_list);
+	// Must be alphabetically sorted for hash to compute.
+	class_list.sort_custom<StringName::AlphCompare>();
 
-	while ((k = classes.next(k))) {
-		names.push_back(*k);
-	}
-	//must be alphabetically sorted for hash to compute
-	names.sort_custom<StringName::AlphCompare>();
-
-	for (const StringName &E : names) {
+	for (const StringName &E : class_list) {
 		ClassInfo *t = classes.getptr(E);
 		ERR_FAIL_COND_V_MSG(!t, 0, "Cannot get class '" + String(E) + "'.");
 		if (t->api != p_api || !t->exposed) {
@@ -195,10 +184,8 @@ uint64_t ClassDB::get_api_hash(APIType p_api) {
 
 			List<StringName> snames;
 
-			k = nullptr;
-
-			while ((k = t->method_map.next(k))) {
-				String name = k->operator String();
+			for (const KeyValue<StringName, MethodBind *> &F : t->method_map) {
+				String name = F.key.operator String();
 
 				ERR_CONTINUE(name.is_empty());
 
@@ -206,7 +193,7 @@ uint64_t ClassDB::get_api_hash(APIType p_api) {
 					continue; // Ignore non-virtual methods that start with an underscore
 				}
 
-				snames.push_back(*k);
+				snames.push_back(F.key);
 			}
 
 			snames.sort_custom<StringName::AlphCompare>();
@@ -241,10 +228,8 @@ uint64_t ClassDB::get_api_hash(APIType p_api) {
 
 			List<StringName> snames;
 
-			k = nullptr;
-
-			while ((k = t->constant_map.next(k))) {
-				snames.push_back(*k);
+			for (const KeyValue<StringName, int> &F : t->constant_map) {
+				snames.push_back(F.key);
 			}
 
 			snames.sort_custom<StringName::AlphCompare>();
@@ -259,10 +244,8 @@ uint64_t ClassDB::get_api_hash(APIType p_api) {
 
 			List<StringName> snames;
 
-			k = nullptr;
-
-			while ((k = t->signal_map.next(k))) {
-				snames.push_back(*k);
+			for (const KeyValue<StringName, MethodInfo> &F : t->signal_map) {
+				snames.push_back(F.key);
 			}
 
 			snames.sort_custom<StringName::AlphCompare>();
@@ -280,10 +263,8 @@ uint64_t ClassDB::get_api_hash(APIType p_api) {
 
 			List<StringName> snames;
 
-			k = nullptr;
-
-			while ((k = t->property_setget.next(k))) {
-				snames.push_back(*k);
+			for (const KeyValue<StringName, PropertySetGet> &F : t->property_setget) {
+				snames.push_back(F.key);
 			}
 
 			snames.sort_custom<StringName::AlphCompare>();
@@ -474,10 +455,8 @@ void ClassDB::get_method_list(const StringName &p_class, List<MethodInfo> *p_met
 
 #else
 
-		const StringName *K = nullptr;
-
-		while ((K = type->method_map.next(K))) {
-			MethodBind *m = type->method_map[*K];
+		for (KeyValue<StringName, MethodBind *> &E : type->method_map) {
+			MethodBind *m = E.value;
 			MethodInfo minfo = info_from_bind(m);
 			p_methods->push_back(minfo);
 		}
@@ -603,10 +582,9 @@ void ClassDB::get_integer_constant_list(const StringName &p_class, List<String>
 			p_constants->push_back(E);
 		}
 #else
-		const StringName *K = nullptr;
 
-		while ((K = type->constant_map.next(K))) {
-			p_constants->push_back(*K);
+		for (const KeyValue<StringName, int> &E : type->constant_map) {
+			p_constants->push_back(E.key);
 		}
 
 #endif
@@ -667,12 +645,11 @@ StringName ClassDB::get_integer_constant_enum(const StringName &p_class, const S
 	ClassInfo *type = classes.getptr(p_class);
 
 	while (type) {
-		const StringName *k = nullptr;
-		while ((k = type->enum_map.next(k))) {
-			List<StringName> &constants_list = type->enum_map.get(*k);
+		for (KeyValue<StringName, List<StringName>> &E : type->enum_map) {
+			List<StringName> &constants_list = E.value;
 			const List<StringName>::Element *found = constants_list.find(p_name);
 			if (found) {
-				return *k;
+				return E.key;
 			}
 		}
 
@@ -692,9 +669,8 @@ void ClassDB::get_enum_list(const StringName &p_class, List<StringName> *p_enums
 	ClassInfo *type = classes.getptr(p_class);
 
 	while (type) {
-		const StringName *k = nullptr;
-		while ((k = type->enum_map.next(k))) {
-			p_enums->push_back(*k);
+		for (KeyValue<StringName, List<StringName>> &E : type->enum_map) {
+			p_enums->push_back(E.key);
 		}
 
 		if (p_no_inheritance) {
@@ -800,9 +776,8 @@ void ClassDB::get_signal_list(const StringName &p_class, List<MethodInfo> *p_sig
 	ClassInfo *check = type;
 
 	while (check) {
-		const StringName *S = nullptr;
-		while ((S = check->signal_map.next(S))) {
-			p_signals->push_back(check->signal_map[*S]);
+		for (KeyValue<StringName, MethodInfo> &E : check->signal_map) {
+			p_signals->push_back(E.value);
 		}
 
 		if (p_no_inheritance) {
@@ -1397,10 +1372,8 @@ void ClassDB::add_resource_base_extension(const StringName &p_extension, const S
 }
 
 void ClassDB::get_resource_base_extensions(List<String> *p_extensions) {
-	const StringName *K = nullptr;
-
-	while ((K = resource_base_extensions.next(K))) {
-		p_extensions->push_back(*K);
+	for (const KeyValue<StringName, StringName> &E : resource_base_extensions) {
+		p_extensions->push_back(E.key);
 	}
 }
 
@@ -1409,12 +1382,9 @@ bool ClassDB::is_resource_extension(const StringName &p_extension) {
 }
 
 void ClassDB::get_extensions_for_type(const StringName &p_class, List<String> *p_extensions) {
-	const StringName *K = nullptr;
-
-	while ((K = resource_base_extensions.next(K))) {
-		StringName cmp = resource_base_extensions[*K];
-		if (is_parent_class(p_class, cmp) || is_parent_class(cmp, p_class)) {
-			p_extensions->push_back(*K);
+	for (const KeyValue<StringName, StringName> &E : resource_base_extensions) {
+		if (is_parent_class(p_class, E.value) || is_parent_class(E.value, p_class)) {
+			p_extensions->push_back(E.key);
 		}
 	}
 }
@@ -1556,14 +1526,11 @@ void ClassDB::cleanup_defaults() {
 void ClassDB::cleanup() {
 	//OBJTYPE_LOCK; hah not here
 
-	const StringName *k = nullptr;
-
-	while ((k = classes.next(k))) {
-		ClassInfo &ti = classes[*k];
+	for (KeyValue<StringName, ClassInfo> &E : classes) {
+		ClassInfo &ti = E.value;
 
-		const StringName *m = nullptr;
-		while ((m = ti.method_map.next(m))) {
-			memdelete(ti.method_map[*m]);
+		for (KeyValue<StringName, MethodBind *> &F : ti.method_map) {
+			memdelete(F.value);
 		}
 	}
 	classes.clear();
diff --git a/core/object/object.cpp b/core/object/object.cpp
index 2b62041533..797eecd312 100644
--- a/core/object/object.cpp
+++ b/core/object/object.cpp
@@ -417,9 +417,9 @@ void Object::set(const StringName &p_name, const Variant &p_value, bool *r_valid
 		return;
 
 	} else {
-		OrderedHashMap<StringName, Variant>::Element *E = metadata_properties.getptr(p_name);
-		if (E) {
-			E->get() = p_value;
+		Variant **V = metadata_properties.getptr(p_name);
+		if (V) {
+			**V = p_value;
 			if (r_valid) {
 				*r_valid = true;
 			}
@@ -508,10 +508,10 @@ Variant Object::get(const StringName &p_name, bool *r_valid) const {
 		return ret;
 	}
 
-	const OrderedHashMap<StringName, Variant>::Element *E = metadata_properties.getptr(p_name);
+	const Variant *const *V = metadata_properties.getptr(p_name);
 
-	if (E) {
-		ret = E->get();
+	if (V) {
+		ret = **V;
 		if (r_valid) {
 			*r_valid = true;
 		}
@@ -666,9 +666,9 @@ void Object::get_property_list(List<PropertyInfo> *p_list, bool p_reversed) cons
 		script_instance->get_property_list(p_list);
 	}
 
-	for (OrderedHashMap<StringName, Variant>::ConstElement K = metadata.front(); K; K = K.next()) {
-		PropertyInfo pi = PropertyInfo(K.value().get_type(), "metadata/" + K.key().operator String());
-		if (K.value().get_type() == Variant::OBJECT) {
+	for (const KeyValue<StringName, Variant> &K : metadata) {
+		PropertyInfo pi = PropertyInfo(K.value.get_type(), "metadata/" + K.key.operator String());
+		if (K.value.get_type() == Variant::OBJECT) {
 			pi.hint = PROPERTY_HINT_RESOURCE_TYPE;
 			pi.hint_string = "Resource";
 		}
@@ -944,13 +944,13 @@ void Object::set_meta(const StringName &p_name, const Variant &p_value) {
 		return;
 	}
 
-	OrderedHashMap<StringName, Variant>::Element E = metadata.find(p_name);
+	HashMap<StringName, Variant>::Iterator E = metadata.find(p_name);
 	if (E) {
-		E.value() = p_value;
+		E->value = p_value;
 	} else {
 		ERR_FAIL_COND(!p_name.operator String().is_valid_identifier());
-		E = metadata.insert(p_name, p_value);
-		metadata_properties["metadata/" + p_name.operator String()] = E;
+		Variant *V = &metadata.insert(p_name, p_value)->value;
+		metadata_properties["metadata/" + p_name.operator String()] = V;
 		notify_property_list_changed();
 	}
 }
@@ -993,16 +993,16 @@ Array Object::_get_method_list_bind() const {
 Vector<StringName> Object::_get_meta_list_bind() const {
 	Vector<StringName> _metaret;
 
-	for (OrderedHashMap<StringName, Variant>::ConstElement K = metadata.front(); K; K = K.next()) {
-		_metaret.push_back(K.key());
+	for (const KeyValue<StringName, Variant> &K : metadata) {
+		_metaret.push_back(K.key);
 	}
 
 	return _metaret;
 }
 
 void Object::get_meta_list(List<StringName> *p_list) const {
-	for (OrderedHashMap<StringName, Variant>::ConstElement K = metadata.front(); K; K = K.next()) {
-		p_list->push_back(K.key());
+	for (const KeyValue<StringName, Variant> &K : metadata) {
+		p_list->push_back(K.key);
 	}
 }
 
@@ -1250,21 +1250,18 @@ void Object::get_signal_list(List<MethodInfo> *p_signals) const {
 
 	ClassDB::get_signal_list(get_class_name(), p_signals);
 	//find maybe usersignals?
-	const StringName *S = nullptr;
 
-	while ((S = signal_map.next(S))) {
-		if (!signal_map[*S].user.name.is_empty()) {
+	for (const KeyValue<StringName, SignalData> &E : signal_map) {
+		if (!E.value.user.name.is_empty()) {
 			//user signal
-			p_signals->push_back(signal_map[*S].user);
+			p_signals->push_back(E.value.user);
 		}
 	}
 }
 
 void Object::get_all_signal_connections(List<Connection> *p_connections) const {
-	const StringName *S = nullptr;
-
-	while ((S = signal_map.next(S))) {
-		const SignalData *s = &signal_map[*S];
+	for (const KeyValue<StringName, SignalData> &E : signal_map) {
+		const SignalData *s = &E.value;
 
 		for (int i = 0; i < s->slot_map.size(); i++) {
 			p_connections->push_back(s->slot_map.getv(i).conn);
@@ -1285,10 +1282,9 @@ void Object::get_signal_connection_list(const StringName &p_signal, List<Connect
 
 int Object::get_persistent_signal_connection_count() const {
 	int count = 0;
-	const StringName *S = nullptr;
 
-	while ((S = signal_map.next(S))) {
-		const SignalData *s = &signal_map[*S];
+	for (const KeyValue<StringName, SignalData> &E : signal_map) {
+		const SignalData *s = &E.value;
 
 		for (int i = 0; i < s->slot_map.size(); i++) {
 			if (s->slot_map.getv(i).conn.flags & CONNECT_PERSIST) {
@@ -1866,15 +1862,15 @@ Object::~Object() {
 		_extension_instance = nullptr;
 	}
 
-	const StringName *S = nullptr;
-
 	if (_emitting) {
 		//@todo this may need to actually reach the debugger prioritarily somehow because it may crash before
 		ERR_PRINT("Object " + to_string() + " was freed or unreferenced while a signal is being emitted from it. Try connecting to the signal using 'CONNECT_DEFERRED' flag, or use queue_free() to free the object (if this object is a Node) to avoid this error and potential crashes.");
 	}
 
-	while ((S = signal_map.next(nullptr))) {
-		SignalData *s = &signal_map[*S];
+	while (signal_map.size()) {
+		// Avoid regular iteration so erasing is safe.
+		KeyValue<StringName, SignalData> &E = *signal_map.begin();
+		SignalData *s = &E.value;
 
 		//brute force disconnect for performance
 		int slot_count = s->slot_map.size();
@@ -1884,7 +1880,7 @@ Object::~Object() {
 			slot_list[i].value.conn.callable.get_object()->connections.erase(slot_list[i].value.cE);
 		}
 
-		signal_map.erase(*S);
+		signal_map.erase(E.key);
 	}
 
 	//signals from nodes that connect to this node
diff --git a/core/object/object.h b/core/object/object.h
index c3e3c68b59..00cb73593b 100644
--- a/core/object/object.h
+++ b/core/object/object.h
@@ -39,7 +39,6 @@
 #include "core/templates/hash_map.h"
 #include "core/templates/list.h"
 #include "core/templates/map.h"
-#include "core/templates/ordered_hash_map.h"
 #include "core/templates/safe_refcount.h"
 #include "core/templates/set.h"
 #include "core/templates/vmap.h"
@@ -515,8 +514,8 @@ private:
 #endif
 	ScriptInstance *script_instance = nullptr;
 	Variant script; // Reference does not exist yet, store it in a Variant.
-	OrderedHashMap<StringName, Variant> metadata;
-	HashMap<StringName, OrderedHashMap<StringName, Variant>::Element> metadata_properties;
+	HashMap<StringName, Variant> metadata;
+	HashMap<StringName, Variant *> metadata_properties;
 	mutable StringName _class_name;
 	mutable const StringName *_class_ptr = nullptr;
 
diff --git a/core/object/script_language.cpp b/core/object/script_language.cpp
index a5d25bf533..c1036e3413 100644
--- a/core/object/script_language.cpp
+++ b/core/object/script_language.cpp
@@ -253,10 +253,9 @@ StringName ScriptServer::get_global_class_native_base(const String &p_class) {
 }
 
 void ScriptServer::get_global_class_list(List<StringName> *r_global_classes) {
-	const StringName *K = nullptr;
 	List<StringName> classes;
-	while ((K = global_classes.next(K))) {
-		classes.push_back(*K);
+	for (const KeyValue<StringName, GlobalScriptClass> &E : global_classes) {
+		classes.push_back(E.key);
 	}
 	classes.sort_custom<StringName::AlphCompare>();
 	for (const StringName &E : classes) {
diff --git a/core/os/memory.h b/core/os/memory.h
index baa96ef3e9..42ba9634e2 100644
--- a/core/os/memory.h
+++ b/core/os/memory.h
@@ -197,4 +197,12 @@ struct _GlobalNilClass {
 	static _GlobalNil _nil;
 };
 
+template <class T>
+class DefaultTypedAllocator {
+public:
+	template <class... Args>
+	_FORCE_INLINE_ T *new_allocation(const Args &&...p_args) { return memnew(T(p_args...)); }
+	_FORCE_INLINE_ void delete_allocation(T *p_allocation) { memdelete(p_allocation); }
+};
+
 #endif // MEMORY_H
diff --git a/core/string/translation_po.cpp b/core/string/translation_po.cpp
index 3f94e064ec..fa656b634d 100644
--- a/core/string/translation_po.cpp
+++ b/core/string/translation_po.cpp
@@ -70,21 +70,14 @@ Dictionary TranslationPO::_get_messages() const {
 
 	Dictionary d;
 
-	List<StringName> context_l;
-	translation_map.get_key_list(&context_l);
-	for (const StringName &ctx : context_l) {
-		const HashMap<StringName, Vector<StringName>> &id_str_map = translation_map[ctx];
-
+	for (const KeyValue<StringName, HashMap<StringName, Vector<StringName>>> &E : translation_map) {
 		Dictionary d2;
-		List<StringName> id_l;
-		id_str_map.get_key_list(&id_l);
-		// Save list of id and strs associated with a context in a temporary dictionary.
-		for (List<StringName>::Element *E2 = id_l.front(); E2; E2 = E2->next()) {
-			StringName id = E2->get();
-			d2[id] = id_str_map[id];
+
+		for (const KeyValue<StringName, Vector<StringName>> &E2 : E.value) {
+			d2[E2.key] = E2.value;
 		}
 
-		d[ctx] = d2;
+		d[E.key] = d2;
 	}
 
 	return d;
@@ -274,31 +267,24 @@ void TranslationPO::get_message_list(List<StringName> *r_messages) const {
 	// OptimizedTranslation uses this function to get the list of msgid.
 	// Return all the keys of translation_map under "" context.
 
-	List<StringName> context_l;
-	translation_map.get_key_list(&context_l);
-
-	for (const StringName &E : context_l) {
-		if (String(E) != "") {
+	for (const KeyValue<StringName, HashMap<StringName, Vector<StringName>>> &E : translation_map) {
+		if (E.key != StringName()) {
 			continue;
 		}
 
-		List<StringName> msgid_l;
-		translation_map[E].get_key_list(&msgid_l);
-
-		for (List<StringName>::Element *E2 = msgid_l.front(); E2; E2 = E2->next()) {
-			r_messages->push_back(E2->get());
+		for (const KeyValue<StringName, Vector<StringName>> &E2 : E.value) {
+			r_messages->push_back(E2.key);
 		}
 	}
 }
 
 int TranslationPO::get_message_count() const {
-	List<StringName> context_l;
-	translation_map.get_key_list(&context_l);
-
 	int count = 0;
-	for (const StringName &E : context_l) {
-		count += translation_map[E].size();
+
+	for (const KeyValue<StringName, HashMap<StringName, Vector<StringName>>> &E : translation_map) {
+		count += E.value.size();
 	}
+
 	return count;
 }
 
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);
 	}
 
diff --git a/core/variant/dictionary.cpp b/core/variant/dictionary.cpp
index 0f2f8fc8ed..46543da2c2 100644
--- a/core/variant/dictionary.cpp
+++ b/core/variant/dictionary.cpp
@@ -30,7 +30,7 @@
 
 #include "dictionary.h"
 
-#include "core/templates/ordered_hash_map.h"
+#include "core/templates/hash_map.h"
 #include "core/templates/safe_refcount.h"
 #include "core/variant/variant.h"
 // required in this order by VariantInternal, do not remove this comment.
@@ -41,7 +41,7 @@
 
 struct DictionaryPrivate {
 	SafeRefCount refcount;
-	OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator> variant_map;
+	HashMap<Variant, Variant, VariantHasher, VariantComparator> variant_map;
 };
 
 void Dictionary::get_key_list(List<Variant> *p_keys) const {
@@ -49,16 +49,16 @@ void Dictionary::get_key_list(List<Variant> *p_keys) const {
 		return;
 	}
 
-	for (OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator>::Element E = _p->variant_map.front(); E; E = E.next()) {
-		p_keys->push_back(E.key());
+	for (const KeyValue<Variant, Variant> &E : _p->variant_map) {
+		p_keys->push_back(E.key);
 	}
 }
 
 Variant Dictionary::get_key_at_index(int p_index) const {
 	int index = 0;
-	for (OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator>::Element E = _p->variant_map.front(); E; E = E.next()) {
+	for (const KeyValue<Variant, Variant> &E : _p->variant_map) {
 		if (index == p_index) {
-			return E.key();
+			return E.key;
 		}
 		index++;
 	}
@@ -68,9 +68,9 @@ Variant Dictionary::get_key_at_index(int p_index) const {
 
 Variant Dictionary::get_value_at_index(int p_index) const {
 	int index = 0;
-	for (OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator>::Element E = _p->variant_map.front(); E; E = E.next()) {
+	for (const KeyValue<Variant, Variant> &E : _p->variant_map) {
 		if (index == p_index) {
-			return E.value();
+			return E.value;
 		}
 		index++;
 	}
@@ -97,50 +97,50 @@ const Variant &Dictionary::operator[](const Variant &p_key) const {
 }
 
 const Variant *Dictionary::getptr(const Variant &p_key) const {
-	OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator>::ConstElement E;
+	HashMap<Variant, Variant, VariantHasher, VariantComparator>::ConstIterator E;
 
 	if (p_key.get_type() == Variant::STRING_NAME) {
 		const StringName *sn = VariantInternal::get_string_name(&p_key);
-		E = ((const OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator> *)&_p->variant_map)->find(sn->operator String());
+		E = ((const HashMap<Variant, Variant, VariantHasher, VariantComparator> *)&_p->variant_map)->find(sn->operator String());
 	} else {
-		E = ((const OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator> *)&_p->variant_map)->find(p_key);
+		E = ((const HashMap<Variant, Variant, VariantHasher, VariantComparator> *)&_p->variant_map)->find(p_key);
 	}
 
 	if (!E) {
 		return nullptr;
 	}
-	return &E.get();
+	return &E->value;
 }
 
 Variant *Dictionary::getptr(const Variant &p_key) {
-	OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator>::Element E;
+	HashMap<Variant, Variant, VariantHasher, VariantComparator>::Iterator E;
 
 	if (p_key.get_type() == Variant::STRING_NAME) {
 		const StringName *sn = VariantInternal::get_string_name(&p_key);
-		E = ((OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator> *)&_p->variant_map)->find(sn->operator String());
+		E = ((HashMap<Variant, Variant, VariantHasher, VariantComparator> *)&_p->variant_map)->find(sn->operator String());
 	} else {
-		E = ((OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator> *)&_p->variant_map)->find(p_key);
+		E = ((HashMap<Variant, Variant, VariantHasher, VariantComparator> *)&_p->variant_map)->find(p_key);
 	}
 	if (!E) {
 		return nullptr;
 	}
-	return &E.get();
+	return &E->value;
 }
 
 Variant Dictionary::get_valid(const Variant &p_key) const {
-	OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator>::ConstElement E;
+	HashMap<Variant, Variant, VariantHasher, VariantComparator>::ConstIterator E;
 
 	if (p_key.get_type() == Variant::STRING_NAME) {
 		const StringName *sn = VariantInternal::get_string_name(&p_key);
-		E = ((const OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator> *)&_p->variant_map)->find(sn->operator String());
+		E = ((const HashMap<Variant, Variant, VariantHasher, VariantComparator> *)&_p->variant_map)->find(sn->operator String());
 	} else {
-		E = ((const OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator> *)&_p->variant_map)->find(p_key);
+		E = ((const HashMap<Variant, Variant, VariantHasher, VariantComparator> *)&_p->variant_map)->find(p_key);
 	}
 
 	if (!E) {
 		return Variant();
 	}
-	return E.get();
+	return E->value;
 }
 
 Variant Dictionary::get(const Variant &p_key, const Variant &p_default) const {
@@ -210,9 +210,9 @@ bool Dictionary::recursive_equal(const Dictionary &p_dictionary, int recursion_c
 		return true;
 	}
 	recursion_count++;
-	for (OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator>::ConstElement this_E = ((const OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator> *)&_p->variant_map)->front(); this_E; this_E = this_E.next()) {
-		OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator>::ConstElement other_E = ((const OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator> *)&p_dictionary._p->variant_map)->find(this_E.key());
-		if (!other_E || !this_E.value().hash_compare(other_E.value(), recursion_count)) {
+	for (const KeyValue<Variant, Variant> &this_E : _p->variant_map) {
+		HashMap<Variant, Variant, VariantHasher, VariantComparator>::ConstIterator other_E = ((const HashMap<Variant, Variant, VariantHasher, VariantComparator> *)&p_dictionary._p->variant_map)->find(this_E.key);
+		if (!other_E || !this_E.value.hash_compare(other_E->value, recursion_count)) {
 			return false;
 		}
 	}
@@ -261,9 +261,9 @@ uint32_t Dictionary::recursive_hash(int recursion_count) const {
 	uint32_t h = hash_djb2_one_32(Variant::DICTIONARY);
 
 	recursion_count++;
-	for (OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator>::Element E = _p->variant_map.front(); E; E = E.next()) {
-		h = hash_djb2_one_32(E.key().recursive_hash(recursion_count), h);
-		h = hash_djb2_one_32(E.value().recursive_hash(recursion_count), h);
+	for (const KeyValue<Variant, Variant> &E : _p->variant_map) {
+		h = hash_djb2_one_32(E.key.recursive_hash(recursion_count), h);
+		h = hash_djb2_one_32(E.value.recursive_hash(recursion_count), h);
 	}
 
 	return h;
@@ -278,8 +278,8 @@ Array Dictionary::keys() const {
 	varr.resize(size());
 
 	int i = 0;
-	for (OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator>::Element E = _p->variant_map.front(); E; E = E.next()) {
-		varr[i] = E.key();
+	for (const KeyValue<Variant, Variant> &E : _p->variant_map) {
+		varr[i] = E.key;
 		i++;
 	}
 
@@ -295,8 +295,8 @@ Array Dictionary::values() const {
 	varr.resize(size());
 
 	int i = 0;
-	for (OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator>::Element E = _p->variant_map.front(); E; E = E.next()) {
-		varr[i] = E.get();
+	for (const KeyValue<Variant, Variant> &E : _p->variant_map) {
+		varr[i] = E.value;
 		i++;
 	}
 
@@ -306,16 +306,23 @@ Array Dictionary::values() const {
 const Variant *Dictionary::next(const Variant *p_key) const {
 	if (p_key == nullptr) {
 		// caller wants to get the first element
-		if (_p->variant_map.front()) {
-			return &_p->variant_map.front().key();
+		if (_p->variant_map.begin()) {
+			return &_p->variant_map.begin()->key;
 		}
 		return nullptr;
 	}
-	OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator>::Element E = _p->variant_map.find(*p_key);
+	HashMap<Variant, Variant, VariantHasher, VariantComparator>::Iterator E = _p->variant_map.find(*p_key);
 
-	if (E && E.next()) {
-		return &E.next().key();
+	if (!E) {
+		return nullptr;
+	}
+
+	++E;
+
+	if (E) {
+		return &E->key;
 	}
+
 	return nullptr;
 }
 
@@ -333,12 +340,12 @@ Dictionary Dictionary::recursive_duplicate(bool p_deep, int recursion_count) con
 
 	if (p_deep) {
 		recursion_count++;
-		for (OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator>::Element E = _p->variant_map.front(); E; E = E.next()) {
-			n[E.key().recursive_duplicate(true, recursion_count)] = E.value().recursive_duplicate(true, recursion_count);
+		for (const KeyValue<Variant, Variant> &E : _p->variant_map) {
+			n[E.key.recursive_duplicate(true, recursion_count)] = E.value.recursive_duplicate(true, recursion_count);
 		}
 	} else {
-		for (OrderedHashMap<Variant, Variant, VariantHasher, VariantComparator>::Element E = _p->variant_map.front(); E; E = E.next()) {
-			n[E.key()] = E.value();
+		for (const KeyValue<Variant, Variant> &E : _p->variant_map) {
+			n[E.key] = E.value;
 		}
 	}