HashMap - Revision history

Lou Montana: Add getOrDefaultCall example

2023-04-24T16:22:14Z

← Older revision		Revision as of 18:22, 24 April 2023
Line 111:		Line 111:
	_myMap get "z"; // returns Nothing		_myMap get "z"; // returns Nothing
	_myMap getOrDefault ["z", "NotFound"]; // returns "NotFound"		_myMap getOrDefault ["z", "NotFound"]; // returns "NotFound"
			// alternatively
			_myMap getOrDefaultCall ["z", { systemChat "key 'z' does not exist, creating it"; "26"; }, true];
	</sqf>		</sqf>

Leopard20 at 17:36, 6 April 2023

2023-04-06T17:36:18Z

← Older revision		Revision as of 19:36, 6 April 2023
Line 205:		Line 205:
	For some unsupported data types, such as [[Object]]s, the following workaround can be used, as long as they're supported by the [[hashValue]] command:		For some unsupported data types, such as [[Object]]s, the following workaround can be used, as long as they're supported by the [[hashValue]] command:
	<sqf>		<sqf>
	~~TAG_fnc_add~~ = {		TAG_fnc_set = {
			params ["_hashmap", "_key", "_value"];
	isNil {		isNil {
	~~params ["_hashmap", "_key", "_value"];~~
	private _hash = hashValue _key;		private _hash = hashValue _key;
	private _keyVals = _hashmap getOrDefault [_hash, [[],[]], true]; // uses an array to resolve any potential hash collision		private _keyVals = _hashmap getOrDefault [_hash, [[],[]], true]; // uses an array to resolve any potential hash collision
Line 221:		Line 221:
	};		};
	TAG_fnc_get = {		TAG_fnc_get = {
	params ["_hashmap", "~~_requestedKey~~", "_defaultValue"];		params ["_hashmap", "_key", "_defaultValue"];
	private _hash = hashValue ~~_requestedKey~~;		private "_return";
	private _keyVals = _hashmap getOrDefault [_hash, [[],[]]];		isNil { // force unscheduled check
			private _hash = hashValue _key;
	_keyVals#1 param [_keyVals#0 find ~~_requestedKey~~, _defaultValue];		private _keyVals = _hashmap getOrDefault [_hash, [[],[]]];
			_return = _keyVals#1 param [_keyVals#0 find _key, _defaultValue];
			};
			_return;
			};
			TAG_fnc_remove = {
			params ["_hashmap", "_key"];
			isNil { // force unscheduled check
			private _hash = hashValue _key;
			private _keyVals = _hashmap getOrDefault [_hash, [[],[]]];
			private _keyIndex = _keyVals#0 find _key;
			if (_keyIndex >= 0) then {
			_keyVals#0 deleteAt _keyIndex;
			_keyVals#1 deleteAt _keyIndex;
			};
			};
	};		};

	// Example: Add the player object to hashmap (assuming player is not null)		// Example: Add the player object to hashmap (assuming player is not null)
	private _tempHashmap = createHashMap;		private _tempHashmap = createHashMap;
	[_tempHashmap, player, 1] call ~~TAG_fnc_add~~; // add the player object as key, and 1 as its value		[_tempHashmap, player, 1] call TAG_fnc_set; // add the player object as key, and 1 as its value
	private _value1 = [_tempHashmap, player, 2] call TAG_fnc_get; // will return 1		private _value1 = [_tempHashmap, player, 2] call TAG_fnc_get; // will return 1
	private _value2 = [_tempHashmap, objNull, 2] call TAG_fnc_get; // will return 2, the default value		private _value2 = [_tempHashmap, objNull, 2] call TAG_fnc_get; // will return 2, the default value
	</sqf>		</sqf>

	The above example can be extended to add support for iterations~~, deletion~~, etc. as well.		The above example can be extended to add support for iterations, etc. as well.

	=== Automagic assignation ===		=== Automagic assignation ===

Leopard20: Improve the Unsupported Key Types sample code

2023-04-06T17:23:56Z

Improve the Unsupported Key Types sample code

← Older revision		Revision as of 19:23, 6 April 2023
Line 205:		Line 205:
	For some unsupported data types, such as [[Object]]s, the following workaround can be used, as long as they're supported by the [[hashValue]] command:		For some unsupported data types, such as [[Object]]s, the following workaround can be used, as long as they're supported by the [[hashValue]] command:
	<sqf>		<sqf>
	~~Leo_fnc_add~~ = {		TAG_fnc_add = {
	params ["_hashmap", "_key", "_value"];		isNil {
	private _hash = hashValue _key;		params ["_hashmap", "_key", "_value"];
	private ~~_array~~ = _hashmap getOrDefault [_hash, [], true]; // uses an array to resolve any potential hash collision		private _hash = hashValue _key;
	~~_array~~ pushBack [~~_key~~, _value]; ~~// note: this line doesn't account for existing (duplicate) keys~~		private _keyVals = _hashmap getOrDefault [_hash, [[],[]], true]; // uses an array to resolve any potential hash collision

			private _keyIndex = _keyVals#0 find _key;
			if (_keyIndex < 0) then {
			_keyVals#0 pushBack _key;
			_keyVals#1 pushBack _value;
			} else {
			_keyVals#1 set [_keyIndex, _value];
			};
			};
	};		};
	~~Leo_fnc_get~~ = {		TAG_fnc_get = {
	params ["_hashmap", "_requestedKey", "_defaultValue"];		params ["_hashmap", "_requestedKey", "_defaultValue"];
	private _hash = hashValue _requestedKey;		private _hash = hashValue _requestedKey;
	private ~~_array~~ = _hashmap getOrDefault [_hash, []];		private _keyVals = _hashmap getOrDefault [_hash, [[],[]]];
	~~private _foundValue = _defaultValue;~~
	{		_keyVals#1 param [_keyVals#0 find _requestedKey, _defaultValue];
	~~_x params~~ [~~"_key"~~, ~~"_value"~~];
	~~if (_key isEqualTo _requestedKey) exitWith {~~
	~~_foundValue = _value;~~
	};
	~~} forEach _array;~~
	~~_foundValue; // return found value, or default if not found~~
	};		};
	// Example: Add the player object to hashmap (assuming player is not null)		// Example: Add the player object to hashmap (assuming player is not null)
	private _tempHashmap = createHashMap;		private _tempHashmap = createHashMap;
	[_tempHashmap, player, 1] call ~~Leo_fnc_add~~; // add the player object as key, and 1 as its value		[_tempHashmap, player, 1] call TAG_fnc_add; // add the player object as key, and 1 as its value
	private _value1 = [_tempHashmap, player, 2] call ~~Leo_fnc_get~~; // will return 1		private _value1 = [_tempHashmap, player, 2] call TAG_fnc_get; // will return 1
	private _value2 = [_tempHashmap, objNull, 2] call ~~Leo_fnc_get~~; // will return 2, the default value		private _value2 = [_tempHashmap, objNull, 2] call TAG_fnc_get; // will return 2, the default value
	</sqf>		</sqf>

Lou Montana: Text replacement - "\{\{ Wikipedia \| ([-()a-zA-Z0-9_#':%\/\\]+) \| ([-()a-zA-Z0-9_#':%\/\\ ]+) \}\}" to "{{Link|https://en.wikipedia.org/wiki/$1|$2}}"

2023-02-23T23:48:35Z

Text replacement - "\{\{ *Wikipedia *\| *([-()a-zA-Z0-9_#':%\/\\]+) *\| *([-()a-zA-Z0-9_#':%\/\\ ]+) *\}\}" to "{{Link|https://en.wikipedia.org/wiki/$1|$2}}"

← Older revision		Revision as of 01:48, 24 February 2023
Line 148:		Line 148:
	=== HashMap variables ===		=== HashMap variables ===

	A HashMap variable is a reference to the HashMap (see {{~~Wikipedia~~\|Reference_(computer_science)\|Wikipedia}}); this means that if the HashMap is edited, all scripts and functions using this HashMap will see the changes.		A HashMap variable is a reference to the HashMap (see {{Link\|https://en.wikipedia.org/wiki/Reference_(computer_science)\|Wikipedia}}); this means that if the HashMap is edited, all scripts and functions using this HashMap will see the changes.
	<sqf>		<sqf>
	private _myMap = createHashMapFromArray [["a",1], ["b",2], ["c",3]];		private _myMap = createHashMapFromArray [["a",1], ["b",2], ["c",3]];

Lou Montana: Text replacement - "\{\{ Wikipedia \| ([-a-zA-Z0-9_#':%\/\\]+) \| ([-a-zA-Z0-9_#':%\/\\ ]+) \}\}" to "{{Link|https://en.wikipedia.org/wiki/$1|$2}}"

2023-02-23T23:47:36Z

Text replacement - "\{\{ *Wikipedia *\| *([-a-zA-Z0-9_#':%\/\\]+) *\| *([-a-zA-Z0-9_#':%\/\\ ]+) *\}\}" to "{{Link|https://en.wikipedia.org/wiki/$1|$2}}"

← Older revision		Revision as of 01:47, 24 February 2023
Line 46:		Line 46:
	Every single one of these comparisons takes some time - not much, but it will add up eventually. This is no problem as long as our Array is relatively small, but it becomes a serious issue when the Array starts growing: If there are 10,000 elements in the Array that means up to 10,000 comparisons might be necessary just to find a single element, if there are 100,000 elements that means up to 100,000 comparisons and so on - the amount of steps and time needed to find an element grows linearly with the Array size.<br>		Every single one of these comparisons takes some time - not much, but it will add up eventually. This is no problem as long as our Array is relatively small, but it becomes a serious issue when the Array starts growing: If there are 10,000 elements in the Array that means up to 10,000 comparisons might be necessary just to find a single element, if there are 100,000 elements that means up to 100,000 comparisons and so on - the amount of steps and time needed to find an element grows linearly with the Array size.<br>

	And this is where HashMaps come in. Simply put: When a key-value pair is inserted into a HashMap, a hash function is applied to the key to determine the position at which the key-value pair is going to be stored. Then, when we want to retrieve the value associated with a specific key, the same hash function ({{arma3}} uses {{~~Wikipedia~~\|Fowler%E2%80%93Noll%E2%80%93Vo_hash_function\|FNV-1a 64-bit}}) is applied to that key and the resulting position tells the HashMap exactly where to find the key-value pair that we are looking for.		And this is where HashMaps come in. Simply put: When a key-value pair is inserted into a HashMap, a hash function is applied to the key to determine the position at which the key-value pair is going to be stored. Then, when we want to retrieve the value associated with a specific key, the same hash function ({{arma3}} uses {{Link\|https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function\|FNV-1a 64-bit}}) is applied to that key and the resulting position tells the HashMap exactly where to find the key-value pair that we are looking for.
	<sqf>private _data = _playerDataHashMap get "Wanted_UID";</sqf>		<sqf>private _data = _playerDataHashMap get "Wanted_UID";</sqf>
	Since the process to find a given key-value pair is always the same (apply hash function, look at the resulting position, return the value that is stored there), it also always takes (more or less) the same amount of time - regardless of the size of the HashMap.		Since the process to find a given key-value pair is always the same (apply hash function, look at the resulting position, return the value that is stored there), it also always takes (more or less) the same amount of time - regardless of the size of the HashMap.
Line 285:		Line 285:
	=== Scalar Key Precision ===		=== Scalar Key Precision ===

	[[Number]]s in {{arma3}} are floating point numbers, and because there are gaps between floating point numbers, rounding is necessary - see also {{~~Wikipedia~~\|Single-precision_floating-point_format\|Wikipedia}}. For example, 87654316, 87654317, 87654318, 87654319, 87654320, 87654321, 87654322, 87654323 and 87654324 will all be rounded to and treated as the same value by the game engine (because the actual value of each of these numbers can not be represented as an {{arma3}} floating point number). Similar problems occur with fractional numbers:		[[Number]]s in {{arma3}} are floating point numbers, and because there are gaps between floating point numbers, rounding is necessary - see also {{Link\|https://en.wikipedia.org/wiki/Single-precision_floating-point_format\|Wikipedia}}. For example, 87654316, 87654317, 87654318, 87654319, 87654320, 87654321, 87654322, 87654323 and 87654324 will all be rounded to and treated as the same value by the game engine (because the actual value of each of these numbers can not be represented as an {{arma3}} floating point number). Similar problems occur with fractional numbers:
	<sqf>		<sqf>
	// this will return false:		// this will return false:

Lou Montana: Text replacement - "Link\|https:\/\/en\.wikipedia\.org\/([^w][^i])" to "Link|https://en.wikipedia.org/wiki/$1"

2023-02-23T21:11:12Z

Text replacement - "Link\|https:\/\/en\.wikipedia\.org\/([^w][^i])" to "Link|https://en.wikipedia.org/wiki/$1"

← Older revision		Revision as of 23:11, 23 February 2023
Line 5:		Line 5:
	A '''HashMap''' is a specialized data structure that contains key-value pairs.<br>		A '''HashMap''' is a specialized data structure that contains key-value pairs.<br>
	HashMaps provide (near) constant-time lookup for keys, making them highly efficient at finding the value associated with a specific key - even if there is a very large amount of keys.<br>		HashMaps provide (near) constant-time lookup for keys, making them highly efficient at finding the value associated with a specific key - even if there is a very large amount of keys.<br>
	See {{Link\|https://en.wikipedia.org/Hash_table\|Wikipedia}} to learn more about the underlying technology.		See {{Link\|https://en.wikipedia.org/wiki/Hash_table\|Wikipedia}} to learn more about the underlying technology.

	While HashMaps and [[Array]]s share many traits (and [[SQF Syntax\|SQF]] command names), there are important differences and HashMaps must not be considered as some sort of new or improved replacement for the Array.		While HashMaps and [[Array]]s share many traits (and [[SQF Syntax\|SQF]] command names), there are important differences and HashMaps must not be considered as some sort of new or improved replacement for the Array.

Lou Montana: Text replacement - "\{\{Wikipedia \| ([a-zA-Z0-9_#]+) \| ([a-zA-Z0-9_ #]+) *\}\}" to "{{Link|https://en.wikipedia.org/$1|$2}}"

2023-02-23T21:02:14Z

Text replacement - "\{\{Wikipedia *\| *([a-zA-Z0-9_#]+) *\| *([a-zA-Z0-9_ #]+) *\}\}" to "{{Link|https://en.wikipedia.org/$1|$2}}"

← Older revision		Revision as of 23:02, 23 February 2023
Line 5:		Line 5:
	A '''HashMap''' is a specialized data structure that contains key-value pairs.<br>		A '''HashMap''' is a specialized data structure that contains key-value pairs.<br>
	HashMaps provide (near) constant-time lookup for keys, making them highly efficient at finding the value associated with a specific key - even if there is a very large amount of keys.<br>		HashMaps provide (near) constant-time lookup for keys, making them highly efficient at finding the value associated with a specific key - even if there is a very large amount of keys.<br>
	See {{~~Wikipedia~~\|Hash_table\|Wikipedia}} to learn more about the underlying technology.		See {{Link\|https://en.wikipedia.org/Hash_table\|Wikipedia}} to learn more about the underlying technology.

	While HashMaps and [[Array]]s share many traits (and [[SQF Syntax\|SQF]] command names), there are important differences and HashMaps must not be considered as some sort of new or improved replacement for the Array.		While HashMaps and [[Array]]s share many traits (and [[SQF Syntax\|SQF]] command names), there are important differences and HashMaps must not be considered as some sort of new or improved replacement for the Array.

Lou Montana: Fix code

2022-12-13T17:38:00Z

Fix code

← Older revision		Revision as of 19:38, 13 December 2022
Line 27:		Line 27:

	Consider the following example to understand what that means: Let's say we have an Array that looks like this:		Consider the following example to understand what that means: Let's say we have an Array that looks like this:
	<sqf>private _playerDataArray = [["Player_A_UID", "Data A-1", "Data A-2", ...], ["Player_B_UID", "Data B-1", "Data B-2", ...], ["Player_C_UID", "Data C-1", "Data C-2", ...], ...];</sqf>		<sqf>private _playerDataArray = [["Player_A_UID", "Data A-1", "Data A-2" /, ... /], ["Player_B_UID", "Data B-1", "Data B-2" /, ... /], ["Player_C_UID", "Data C-1", "Data C-2" /, ... /] /, ... /];</sqf>
	We want to find a specific [[getPlayerUID\|UID]] so that we can retrieve the corresponding data. We can easily achieve that using the [[findIf]] command:		We want to find a specific [[getPlayerUID\|UID]] so that we can retrieve the corresponding data. We can easily achieve that using the [[findIf]] command:
	<sqf>		<sqf>

Lou Montana: Some wiki formatting

2022-07-25T16:06:29Z

Some wiki formatting

← Older revision		Revision as of 18:06, 25 July 2022
Line 42:		Line 42:
	} forEach _playerDataArray;		} forEach _playerDataArray;
	</sqf>		</sqf>
	Now consider how many [[isEqualTo]] comparisons this [[forEach]]-loop has to perform: If the element identified by "Wanted_UID" is stored at or near the end of ~~{{ic\|~~_playerDataArray}}, then our code has to go through (almost) the entire Array to find it - and the same is the case if the element we are looking for does not exist in our Array.		Now consider how many [[isEqualTo]] comparisons this [[forEach]]-loop has to perform: If the element identified by "Wanted_UID" is stored at or near the end of <sqf inline>_playerDataArray</sqf>, then our code has to go through (almost) the entire Array to find it - and the same is the case if the element we are looking for does not exist in our Array.

	Every single one of these comparisons takes some time - not much, but it will add up eventually. This is no problem as long as our Array is relatively small, but it becomes a serious issue when the Array starts growing: If there are 10,000 elements in the Array that means up to 10,000 comparisons might be necessary just to find a single element, if there are 100,000 elements that means up to 100,000 comparisons and so on - the amount of steps and time needed to find an element grows linearly with the Array size.<br>		Every single one of these comparisons takes some time - not much, but it will add up eventually. This is no problem as long as our Array is relatively small, but it becomes a serious issue when the Array starts growing: If there are 10,000 elements in the Array that means up to 10,000 comparisons might be necessary just to find a single element, if there are 100,000 elements that means up to 100,000 comparisons and so on - the amount of steps and time needed to find an element grows linearly with the Array size.<br>

Lou Montana: Text replacement - "Numbers" to "Numbers"

2022-07-12T22:38:20Z

Text replacement - "Numbers" to "Numbers"

← Older revision		Revision as of 00:38, 13 July 2022
Line 285:		Line 285:
	=== Scalar Key Precision ===		=== Scalar Key Precision ===

	[[Number~~\|Numbers~~]] in {{arma3}} are floating point numbers, and because there are gaps between floating point numbers, rounding is necessary - see also {{Wikipedia\|Single-precision_floating-point_format\|Wikipedia}}. For example, 87654316, 87654317, 87654318, 87654319, 87654320, 87654321, 87654322, 87654323 and 87654324 will all be rounded to and treated as the same value by the game engine (because the actual value of each of these numbers can not be represented as an {{arma3}} floating point number). Similar problems occur with fractional numbers:		[[Number]]s in {{arma3}} are floating point numbers, and because there are gaps between floating point numbers, rounding is necessary - see also {{Wikipedia\|Single-precision_floating-point_format\|Wikipedia}}. For example, 87654316, 87654317, 87654318, 87654319, 87654320, 87654321, 87654322, 87654323 and 87654324 will all be rounded to and treated as the same value by the game engine (because the actual value of each of these numbers can not be represented as an {{arma3}} floating point number). Similar problems occur with fractional numbers:
	<sqf>		<sqf>
	// this will return false:		// this will return false: