Difference between revisions of "HashMap"

From Bohemia Interactive Community
Jump to navigation Jump to search
m (Text replacement - "{{SideTOC}}" to "{{TOC|side}}")
(Improvements across the whole page, finished Scalar Key precision section)
Line 1: Line 1:
 
{{TOC|side}}
 
{{TOC|side}}
{{Feature|arma3|HashMaps were introduced in version 2.01.}}
 
A '''HashMap''' is a container storing Key-Value pairs which is very efficient with many entries that have different keys.<br>
 
Due to keys being stored by their hash, a HashMap provides constant-time lookup for keys, meaning it is very efficient for finding a key. More information on [https://en.wikipedia.org/wiki/Hash_table Wikipedia].<br>
 
As a HashMap is a container, it stores some traits/properties with [[Array|Arrays]]
 
  
== Working with Hash Maps ==
+
{{Feature|arma3|HashMaps were introduced in {{arma3}} version 2.01.}}
  
=== Array properties ===
+
== Overview ==
 +
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>
 +
See [https://en.wikipedia.org/wiki/Hash_table Wikipedia] to learn more about the underlying technology.
  
A HashMap variable is a '''reference''' to the HashMap(see [https://en.wikipedia.org/wiki/Reference_(computer_science) Wikipedia reference page]);
+
While HashMaps and [[Array|Arrays]] share many traits (and [[SQF]] command names), there are important differences and HashMaps must not be considered as some sort of new or improved replacement for the [[Array]].
this means that if the HashMap is edited, all the scripts/functions using a reference to this HashMap will see the edition.
 
  
[[private]] _myMap = [[createHashMapFromArray]] [<nowiki/>["a",1], ["b",2], ["c",3]];
+
<!-- PROPER USE CASES IN A3 ARE IN FACT SO SPARSE THAT I CAN'T THINK OF A GOOD USE CASE EXAMPLE!
[[private]] _myNewMap = _myMap;
+
== When to use HashMaps ==
_myMap [[set]] ["z", 4];
+
In order to understand the circumstances under which HashMaps are useful, it is important to know that HashMaps are primarily designed for (near) constant-time lookup of keys.
_myNewMap [[get]] "z"; {{cc|will be 4}}
 
  
An array set through [[setVariable]] does not need to be assigned again if you modify it by reference:
+
Consider the following example (proper use cases for HashMaps in {{arma3}} are actually quite sparse, so this is somewhat artificial and constructed): Let's say we have a MP mission and we want to store some data associated with every player's [[getPlayerUID|UID]].
[[player]] [[setVariable]] ["myMap", [[createHashMapFromArray]] [<nowiki/>["a",1], ["b",2], ["c",3]]];
+
-->
[[private]] _myMap = [[player]] [[getVariable]] "myMap";
 
_myMap [[set]] ["z", 4];
 
[[player]] [[getVariable]] "myMap"; {{cc|is [<nowiki/>["a",1], ["b",2], ["c",3], ["z",4]]}}
 
  
 +
== Working with HashMaps ==
 
=== Key Types ===
 
=== Key Types ===
 +
Because of the requirement for the keys to be hashable (and constant), not all [[Data Types]] can be used as keys.
  
Due to the keys requirement to be hashable not all variable types are supported to be used as a key in the HashMap.
+
Supported types are limited to:
 
 
Supported types are:
 
 
<div style="columns: 3">
 
<div style="columns: 3">
* [[Scalar]]
+
* [[Array]]
* [[Bool]]
+
* [[Boolean]] ([[Bool]])
* [[String]]
 
 
* [[Code]]
 
* [[Code]]
* [[Side]]
 
 
* [[Config]]
 
* [[Config]]
 
* [[Namespace]]
 
* [[Namespace]]
* [[NaN]]
+
* [[NaN]] <!-- TODO: What's up with this? -->
* [[Array]]
+
* [[Number]] ([[Scalar]])
 +
* [[Side]]
 +
* [[String]]
 
</div>
 
</div>
  
 
{{Important|
 
{{Important|
* The [[Array]] type also can only contain supported types
+
* [[Array]] keys can only contain supported types.
* The virtual type [[HashMapKey]] is a combination of all supported types
+
* [[Array]] keys are deep-copied on insertion and cannot be modified when retrieved via [[keys]] or inside [[forEach]].
* [[Array]] keys are deep-copied on insertion, and cannot be modified when retrieved via [[keys]] or inside [[forEach]]}}
+
* The virtual type [[HashMapKey]] is a combination of all the supported types.}}
  
 
=== Creating a HashMap ===
 
=== Creating a HashMap ===
 
 
  {{cc|Example of an empty HashMap}}
 
  {{cc|Example of an empty HashMap}}
 
  [[private]] _myMap = [[createHashMap]];
 
  [[private]] _myMap = [[createHashMap]];
Line 56: Line 49:
  
 
=== Setting an element ===
 
=== Setting an element ===
 
 
  [[private]] _myMap = [[createHashMap]];
 
  [[private]] _myMap = [[createHashMap]];
 
  _myMap [[set]] [1, "hello there"]; {{cc|_myMap is [<nowiki/>[1, "hello there"]]}}
 
  _myMap [[set]] [1, "hello there"]; {{cc|_myMap is [<nowiki/>[1, "hello there"]]}}
  
Inserting an element with a key that already exists inside the HashMap, will overwrite the existing key.
+
Inserting an element with a key that already exists inside the HashMap will overwrite the existing key.
 
 
 
  [[private]] _myMap = [[createHashMapFromArray]] [<nowiki/>["a",1], ["b",2]];
 
  [[private]] _myMap = [[createHashMapFromArray]] [<nowiki/>["a",1], ["b",2]];
 
  _overwritten = _myMap [[set]] ["a", 1337]; {{cc|_myMap is now [<nowiki/>["a",1337], ["b",2]] and _overwritten is true}}
 
  _overwritten = _myMap [[set]] ["a", 1337]; {{cc|_myMap is now [<nowiki/>["a",1337], ["b",2]] and _overwritten is true}}
  
 
=== Getting an element ===
 
=== Getting an element ===
 
 
Values are retrieved by their key:
 
Values are retrieved by their key:
 
 
  [[private]] _myMap = [[createHashMapFromArray]] [<nowiki/>["a",1], ["b",2]];
 
  [[private]] _myMap = [[createHashMapFromArray]] [<nowiki/>["a",1], ["b",2]];
 
  _myMap [[get]] "a"; {{cc|returns 1}}
 
  _myMap [[get]] "a"; {{cc|returns 1}}
 
  _myMap [[get]] "z"; {{cc|returns [[Nothing]]}}
 
  _myMap [[get]] "z"; {{cc|returns [[Nothing]]}}
 
  _myMap [[getOrDefault]] ["z", "NotFound"]; {{cc|returns "NotFound"}}
 
  _myMap [[getOrDefault]] ["z", "NotFound"]; {{cc|returns "NotFound"}}
 +
 +
=== Removing an element ===
 +
You can remove (delete) elements from the HashMap using [[deleteAt]] with the element's key:
 +
[[private]] _myMap = [[createHashMapFromArray]] [<nowiki/>["a",1], ["b",2]];
 +
_myMap [[deleteAt]] "b"; {{cc|_myMap is [["a",1]]}}
  
 
=== Checking if an element exists ===
 
=== Checking if an element exists ===
 
+
You can check if a key is present in the HashMap using the [[in]] command:
You can check if a key is in the HashMap using the [[in]] command:
 
 
 
 
  [[private]] _myMap = [[createHashMapFromArray]] [<nowiki/>["a",1], ["b",2]];
 
  [[private]] _myMap = [[createHashMapFromArray]] [<nowiki/>["a",1], ["b",2]];
 
  "a" [[in]] _myMap; {{cc|returns true}}
 
  "a" [[in]] _myMap; {{cc|returns true}}
Line 83: Line 75:
  
 
=== Counting elements ===
 
=== Counting elements ===
 
+
The [[count]] command can be used to return the number of key-value pairs stored in the HashMap:
The [[count]] command can be used to return the number of Key-Value Pairs stored in the HashMap:
 
 
 
 
  [[private]] _myMap = [[createHashMapFromArray]] [<nowiki/>["a",1], ["b",2]];
 
  [[private]] _myMap = [[createHashMapFromArray]] [<nowiki/>["a",1], ["b",2]];
 
  [[count]] _myMap ; {{cc|returns 2}}
 
  [[count]] _myMap ; {{cc|returns 2}}
  
=== Retrieving Keys ===
+
=== Retrieving keys ===
 
 
 
You can retrieve an [[Array]] of all keys in the HashMap using the [[keys]] command:
 
You can retrieve an [[Array]] of all keys in the HashMap using the [[keys]] command:
 
 
  [[private]] _myMap = [[createHashMapFromArray]] [<nowiki/>["a",1], ["b",2]];
 
  [[private]] _myMap = [[createHashMapFromArray]] [<nowiki/>["a",1], ["b",2]];
 
  [[keys]] _myMap; {{cc|returns ["a", "b"]}}
 
  [[keys]] _myMap; {{cc|returns ["a", "b"]}}
  
=== HashMap Copy ===
+
=== HashMap variables ===
 +
A HashMap variable is a reference to the HashMap (see [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.
 +
[[private]] _myMap = [[createHashMapFromArray]] [<nowiki/>["a",1], ["b",2], ["c",3]];
 +
[[private]] _myNewMap = _myMap;
 +
_myMap [[set]] ["z", 4];
 +
_myNewMap [[get]] "z"; {{cc|will be 4}}
  
 +
A HashMap set through [[setVariable]] does not need to be assigned again:
 +
[[player]] [[setVariable]] ["myMap", [[createHashMapFromArray]] [<nowiki/>["a",1], ["b",2], ["c",3]]];
 +
[[private]] _myMap = [[player]] [[getVariable]] "myMap";
 +
_myMap [[set]] ["z", 4];
 +
[[player]] [[getVariable]] "myMap"; {{cc|is [<nowiki/>["a",1], ["b",2], ["c",3], ["z",4]]}}
 +
 +
=== Copying a HashMap ===
 
  [[private]] _myMap = [[createHashMapFromArray]] [<nowiki/>["a",1], ["b",2]];
 
  [[private]] _myMap = [[createHashMapFromArray]] [<nowiki/>["a",1], ["b",2]];
 
  [[private]] _myNewMap = _myMap;
 
  [[private]] _myNewMap = _myMap;
Line 104: Line 104:
  
 
In order to avoid this behaviour, '''copy''' the HashMap with [[+|+ (plus)]]:
 
In order to avoid this behaviour, '''copy''' the HashMap with [[+|+ (plus)]]:
 
{{cc|making copy}}
 
 
  [[private]] _myMap = [[createHashMapFromArray]] [<nowiki/>["a",1], ["b",2]];
 
  [[private]] _myMap = [[createHashMapFromArray]] [<nowiki/>["a",1], ["b",2]];
 
  [[private]] _myNewMap = [[+]]_myMap;
 
  [[private]] _myNewMap = [[+]]_myMap;
Line 111: Line 109:
 
  _myNewMap [[get]] "a"; {{cc|still 1}}
 
  _myNewMap [[get]] "a"; {{cc|still 1}}
  
[[Array|Arrays]] stored as Key or value in the HashMap will also be deep-copied.
+
[[Array|Arrays]] stored as key or value in the HashMap will also be deep-copied.
  
=== Removing (deleting) elements ===
 
 
You can remove elements from the HashMap by using [[deleteAt]] with the elements key:
 
 
[[private]] _myMap = [[createHashMapFromArray]] [<nowiki/>["a",1], ["b",2]];
 
_myMap [[deleteAt]] "b"; {{cc|_myMap is [["a",1]]}}
 
 
=== Iterating through the HashMap ===
 
 
The simplest way to iterate through a HashMap is the [[forEach]] command:
 
  
 +
== Advanced usage ==
 +
=== Iterating through a HashMap ===
 +
In general, HashMaps have to be considered unordered. While iterating through them is possible with [[forEach]], it is less efficient than looping through [[Array|Arrays]].
 
  [[private]] _myMap = [[createHashMapFromArray]] [<nowiki/>["a",1], ["b",2]];
 
  [[private]] _myMap = [[createHashMapFromArray]] [<nowiki/>["a",1], ["b",2]];
  { [[systemChat]] [[str]] [ [[_x]], _y ] } [[forEach]] _myMap;
+
  { [[systemChat]] [[str]] <nowiki>[</nowiki>[[_x]], [[_y]]] } [[forEach]] _myMap;
 
 
When iterating through a HashMap with forEach, the _x variable holds the key of the current element, while the _y variable holds its value.
 
 
 
  
== Advanced usage ==
+
When iterating through a HashMap with [[forEach]], <tt>[[_x]]</tt> contains the key of the current element and <tt>[[_y]]</tt> contains the corresponding value.
  
  
 
== Common errors ==
 
== Common errors ==
 
 
=== 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 [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:
 +
{{cc|This will return [[false]]:}}
 +
(0.3 [[+]] 0.4 [[==]] 0.7)
  
{{WIP}}
+
This means that using very large numbers or fractional numbers as HashMap keys has to be done cautiously to avoid accidentally overwriting existing keys.
bla bla when using scalar key bla bla link to wikipedia floating point precision
 
  
  
 
== See Also ==
 
== See Also ==
 
 
* [[:Category:Command Group: HashMap|All HashMap commands]]  
 
* [[:Category:Command Group: HashMap|All HashMap commands]]  
  
  
 
[[Category: Data Types]]
 
[[Category: Data Types]]

Revision as of 12:49, 25 January 2021

Arma 3
HashMaps were introduced in Arma 3 version 2.01.

Overview

A HashMap is a specialized data structure that contains key-value pairs.
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.
See Wikipedia to learn more about the underlying technology.

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


Working with HashMaps

Key Types

Because of the requirement for the keys to be hashable (and constant), not all Data Types can be used as keys.

Supported types are limited to:

Template:Important

Creating a HashMap

// Example of an empty HashMap
private _myMap = createHashMap;
count _myMap;			// returns 0

// Example of a prefilled HashMap
private _myFilledMap = createHashMapFromArray [["a",1], ["b",2], ["c", 3]];
count _myFilledMap;	// returns 3

Setting an element

private _myMap = createHashMap;
_myMap set [1, "hello there"];	// _myMap is [[1, "hello there"]]

Inserting an element with a key that already exists inside the HashMap will overwrite the existing key.

private _myMap = createHashMapFromArray [["a",1], ["b",2]];
_overwritten = _myMap set ["a", 1337];	// _myMap is now [["a",1337], ["b",2]] and _overwritten is true

Getting an element

Values are retrieved by their key:

private _myMap = createHashMapFromArray [["a",1], ["b",2]];
_myMap get "a";	// returns 1
_myMap get "z";	// returns Nothing
_myMap getOrDefault ["z", "NotFound"];	// returns "NotFound"

Removing an element

You can remove (delete) elements from the HashMap using deleteAt with the element's key:

private _myMap = createHashMapFromArray [["a",1], ["b",2]];
_myMap deleteAt "b"; // _myMap is "a",1

Checking if an element exists

You can check if a key is present in the HashMap using the in command:

private _myMap = createHashMapFromArray [["a",1], ["b",2]];
"a" in _myMap;	// returns true
"z" in _myMap;	// returns false

Counting elements

The count command can be used to return the number of key-value pairs stored in the HashMap:

private _myMap = createHashMapFromArray [["a",1], ["b",2]];
count _myMap ; // returns 2

Retrieving keys

You can retrieve an Array of all keys in the HashMap using the keys command:

private _myMap = createHashMapFromArray [["a",1], ["b",2]];
keys _myMap; // returns ["a", "b"]

HashMap variables

A HashMap variable is a reference to the HashMap (see Wikipedia); this means that if the HashMap is edited, all scripts and functions using this HashMap will see the changes.

private _myMap = createHashMapFromArray [["a",1], ["b",2], ["c",3]];
private _myNewMap = _myMap;
_myMap set ["z", 4];
_myNewMap get "z"; // will be 4

A HashMap set through setVariable does not need to be assigned again:

player setVariable ["myMap", createHashMapFromArray [["a",1], ["b",2], ["c",3]]];
private _myMap = player getVariable "myMap";
_myMap set ["z", 4];
player getVariable "myMap"; // is [["a",1], ["b",2], ["c",3], ["z",4]]

Copying a HashMap

private _myMap = createHashMapFromArray [["a",1], ["b",2]];
private _myNewMap = _myMap;
_myMap set ["a", 1337];
_myNewMap get "a"; // will be 1337

In order to avoid this behaviour, copy the HashMap with + (plus):

private _myMap = createHashMapFromArray [["a",1], ["b",2]];
private _myNewMap = +_myMap;
_myMap set ["a", 1337];
_myNewMap get "a"; // still 1

Arrays stored as key or value in the HashMap will also be deep-copied.


Advanced usage

Iterating through a HashMap

In general, HashMaps have to be considered unordered. While iterating through them is possible with forEach, it is less efficient than looping through Arrays.

private _myMap = createHashMapFromArray [["a",1], ["b",2]];
{ systemChat str [_x, _y] } forEach _myMap;

When iterating through a HashMap with forEach, _x contains the key of the current element and _y contains the corresponding value.


Common errors

Scalar Key precision

Numbers in Arma 3 are floating point numbers, and because there are gaps between floating point numbers, rounding is necessary - see also 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 Arma 3 floating point number). Similar problems occur with fractional numbers:

// This will return false:
(0.3 + 0.4 == 0.7)

This means that using very large numbers or fractional numbers as HashMap keys has to be done cautiously to avoid accidentally overwriting existing keys.


See Also