Replace most uses of Map by HashMap

* Map is unnecessary and inefficient in almost every case.
* Replaced by the new HashMap.
* Renamed Map to RBMap and Set to RBSet for cases that still make sense
  (order matters) but use is discouraged.

There were very few cases where replacing by HashMap was undesired because
keeping the key order was intended.
I tried to keep those (as RBMap) as much as possible, but might have missed
some. Review appreciated!

7 files changed, 43 insertions, 21 deletions

diff --git a/scene/animation/animation_blend_tree.h b/scene/animation/animation_blend_tree.h
index 2acacd7396..73bde633cb 100644
--- a/scene/animation/animation_blend_tree.h
+++ b/scene/animation/animation_blend_tree.h
@@ -354,7 +354,7 @@ class AnimationNodeBlendTree : public AnimationRootNode {
 		Vector<StringName> connections;
 	};
 
-	Map<StringName, Node> nodes;
+	HashMap<StringName, Node> nodes;
 
 	Vector2 graph_offset;
 
diff --git a/scene/animation/animation_node_state_machine.cpp b/scene/animation/animation_node_state_machine.cpp
index b3cae4f5b5..81df12791c 100644
--- a/scene/animation/animation_node_state_machine.cpp
+++ b/scene/animation/animation_node_state_machine.cpp
@@ -188,7 +188,7 @@ bool AnimationNodeStateMachinePlayback::_travel(AnimationNodeStateMachine *p_sta
 	Vector2 current_pos = p_state_machine->states[current].position;
 	Vector2 target_pos = p_state_machine->states[p_travel].position;
 
-	Map<StringName, AStarCost> cost_map;
+	HashMap<StringName, AStarCost> cost_map;
 
 	List<int> open_list;
 
diff --git a/scene/animation/animation_node_state_machine.h b/scene/animation/animation_node_state_machine.h
index 39a84358fb..07d0579533 100644
--- a/scene/animation/animation_node_state_machine.h
+++ b/scene/animation/animation_node_state_machine.h
@@ -152,7 +152,7 @@ private:
 		Vector2 position;
 	};
 
-	Map<StringName, State> states;
+	HashMap<StringName, State> states;
 
 	struct Transition {
 		StringName from;
diff --git a/scene/animation/animation_player.cpp b/scene/animation/animation_player.cpp
index 081e6e809a..9ace6db505 100644
--- a/scene/animation/animation_player.cpp
+++ b/scene/animation/animation_player.cpp
@@ -163,7 +163,7 @@ bool AnimationPlayer::_get(const StringName &p_name, Variant &r_ret) const {
 		for (int i = 0; i < keys.size(); i++) {
 			array.push_back(keys[i].from);
 			array.push_back(keys[i].to);
-			array.push_back(blend_times[keys[i]]);
+			array.push_back(blend_times.get(keys[i]));
 		}
 
 		r_ret = array;
@@ -588,10 +588,10 @@ void AnimationPlayer::_animation_process_animation(AnimationData *p_anim, double
 
 				//StringName property=a->track_get_path(i).get_property();
 
-				Map<StringName, TrackNodeCache::PropertyAnim>::Element *E = nc->property_anim.find(a->track_get_path(i).get_concatenated_subnames());
+				HashMap<StringName, TrackNodeCache::PropertyAnim>::Iterator E = nc->property_anim.find(a->track_get_path(i).get_concatenated_subnames());
 				ERR_CONTINUE(!E); //should it continue, or create a new one?
 
-				TrackNodeCache::PropertyAnim *pa = &E->get();
+				TrackNodeCache::PropertyAnim *pa = &E->value;
 
 				Animation::UpdateMode update_mode = a->value_track_get_update_mode(i);
 
@@ -738,10 +738,10 @@ void AnimationPlayer::_animation_process_animation(AnimationData *p_anim, double
 					continue;
 				}
 
-				Map<StringName, TrackNodeCache::BezierAnim>::Element *E = nc->bezier_anim.find(a->track_get_path(i).get_concatenated_subnames());
+				HashMap<StringName, TrackNodeCache::BezierAnim>::Iterator E = nc->bezier_anim.find(a->track_get_path(i).get_concatenated_subnames());
 				ERR_CONTINUE(!E); //should it continue, or create a new one?
 
-				TrackNodeCache::BezierAnim *ba = &E->get();
+				TrackNodeCache::BezierAnim *ba = &E->value;
 
 				real_t bezier = a->bezier_track_interpolate(i, p_time);
 				if (ba->accum_pass != accum_pass) {
@@ -1272,7 +1272,7 @@ void AnimationPlayer::_animation_removed(const StringName &p_name, const StringN
 void AnimationPlayer::_rename_animation(const StringName &p_from_name, const StringName &p_to_name) {
 	// Rename autoplay or blends if needed.
 	List<BlendKey> to_erase;
-	Map<BlendKey, float> to_insert;
+	HashMap<BlendKey, float, BlendKey> to_insert;
 	for (const KeyValue<BlendKey, float> &E : blend_times) {
 		BlendKey bk = E.key;
 		BlendKey new_bk = bk;
@@ -1298,8 +1298,8 @@ void AnimationPlayer::_rename_animation(const StringName &p_from_name, const Str
 	}
 
 	while (to_insert.size()) {
-		blend_times[to_insert.front()->key()] = to_insert.front()->get();
-		to_insert.erase(to_insert.front());
+		blend_times[to_insert.begin()->key] = to_insert.begin()->value;
+		to_insert.remove(to_insert.begin());
 	}
 
 	if (autoplay == p_from_name) {
@@ -1766,7 +1766,7 @@ void AnimationPlayer::_animation_changed() {
 }
 
 void AnimationPlayer::_stop_playing_caches() {
-	for (Set<TrackNodeCache *>::Element *E = playing_caches.front(); E; E = E->next()) {
+	for (RBSet<TrackNodeCache *>::Element *E = playing_caches.front(); E; E = E->next()) {
 		if (E->get()->node && E->get()->audio_playing) {
 			E->get()->node->call(SNAME("stop"));
 		}
diff --git a/scene/animation/animation_player.h b/scene/animation/animation_player.h
index 8c2f0e390b..3ef87dba28 100644
--- a/scene/animation/animation_player.h
+++ b/scene/animation/animation_player.h
@@ -132,7 +132,7 @@ private:
 			Variant capture;
 		};
 
-		Map<StringName, PropertyAnim> property_anim;
+		HashMap<StringName, PropertyAnim> property_anim;
 
 		struct BezierAnim {
 			Vector<StringName> bezier_property;
@@ -142,7 +142,7 @@ private:
 			uint64_t accum_pass = 0;
 		};
 
-		Map<StringName, BezierAnim> bezier_anim;
+		HashMap<StringName, BezierAnim> bezier_anim;
 
 		uint32_t last_setup_pass = 0;
 		TrackNodeCache() {}
@@ -153,6 +153,16 @@ private:
 		int bone_idx = -1;
 		int blend_shape_idx = -1;
 
+		static uint32_t hash(const TrackNodeCacheKey &p_key) {
+			uint32_t h = hash_one_uint64(p_key.id);
+			h = hash_djb2_one_32(p_key.bone_idx, h);
+			return hash_djb2_one_32(p_key.blend_shape_idx, h);
+		}
+
+		inline bool operator==(const TrackNodeCacheKey &p_right) const {
+			return id == p_right.id && bone_idx == p_right.bone_idx && blend_shape_idx == p_right.blend_shape_idx;
+		}
+
 		inline bool operator<(const TrackNodeCacheKey &p_right) const {
 			if (id == p_right.id) {
 				if (blend_shape_idx == p_right.blend_shape_idx) {
@@ -166,7 +176,7 @@ private:
 		}
 	};
 
-	Map<TrackNodeCacheKey, TrackNodeCache> node_cache_map;
+	HashMap<TrackNodeCacheKey, TrackNodeCache, TrackNodeCacheKey> node_cache_map;
 
 	TrackNodeCache *cache_update[NODE_CACHE_UPDATE_MAX];
 	int cache_update_size = 0;
@@ -174,7 +184,7 @@ private:
 	int cache_update_prop_size = 0;
 	TrackNodeCache::BezierAnim *cache_update_bezier[NODE_CACHE_UPDATE_MAX];
 	int cache_update_bezier_size = 0;
-	Set<TrackNodeCache *> playing_caches;
+	RBSet<TrackNodeCache *> playing_caches;
 
 	uint64_t accum_pass = 1;
 	float speed_scale = 1.0;
@@ -189,7 +199,7 @@ private:
 		uint64_t last_update = 0;
 	};
 
-	Map<StringName, AnimationData> animation_set;
+	HashMap<StringName, AnimationData> animation_set;
 
 	struct AnimationLibraryData {
 		StringName name;
@@ -202,10 +212,22 @@ private:
 	struct BlendKey {
 		StringName from;
 		StringName to;
-		bool operator<(const BlendKey &bk) const { return from == bk.from ? String(to) < String(bk.to) : String(from) < String(bk.from); }
+		static uint32_t hash(const BlendKey &p_key) {
+			return hash_one_uint64((uint64_t(p_key.from.hash()) << 32) | uint32_t(p_key.to.hash()));
+		}
+		bool operator==(const BlendKey &bk) const {
+			return from == bk.from && to == bk.to;
+		}
+		bool operator<(const BlendKey &bk) const {
+			if (from == bk.from) {
+				return to < bk.to;
+			} else {
+				return from < bk.from;
+			}
+		}
 	};
 
-	Map<BlendKey, float> blend_times;
+	HashMap<BlendKey, float, BlendKey> blend_times;
 
 	struct PlaybackData {
 		AnimationData *from = nullptr;
diff --git a/scene/animation/animation_tree.cpp b/scene/animation/animation_tree.cpp
index d957c7f2de..92af15d5d3 100644
--- a/scene/animation/animation_tree.cpp
+++ b/scene/animation/animation_tree.cpp
@@ -486,7 +486,7 @@ void AnimationTree::set_active(bool p_active) {
 	}
 
 	if (!active && is_inside_tree()) {
-		for (Set<TrackCache *>::Element *E = playing_caches.front(); E; E = E->next()) {
+		for (RBSet<TrackCache *>::Element *E = playing_caches.front(); E; E = E->next()) {
 			if (ObjectDB::get_instance(E->get()->object_id)) {
 				E->get()->object->call(SNAME("stop"));
 			}
diff --git a/scene/animation/animation_tree.h b/scene/animation/animation_tree.h
index 3f09bf7f4b..d40d4ccbbd 100644
--- a/scene/animation/animation_tree.h
+++ b/scene/animation/animation_tree.h
@@ -266,7 +266,7 @@ private:
 	};
 
 	HashMap<NodePath, TrackCache *> track_cache;
-	Set<TrackCache *> playing_caches;
+	RBSet<TrackCache *> playing_caches;
 
 	Ref<AnimationNode> root;