the difference is how the elements are searched. Let's take an easy example (not necessary a reflection of the real world) in order to compare the two.
Scenario You have a memory, which has a certain size. For this example, it has enough space to store 10 pieces of information (whatever you want to put into your hashmap or array).
Hashmap The Hashmap is a key-value store. It will take your key and calculate a memory position for the value. Since it always uses the same algorithm to get the correct location, it will always take the same amount of time to return the value. Let's say, you use an integer as a key, then a very simple algorithm could just be a calculation of key mod memory_size , so the pair (13, "Hello") would be stored at memory location 3 (if the first location has the index 1). Of course, there is more logic in place to make sure that no data is overwritten! One would note the access time as O(1)
Array How an array looks up its data highly depends on the implementation. However, the simplest approach would be to use a linked list (for example C/C++ uses that kind of implementation for arrays and std strings). That means that your data is stored together with a pointer to the next element. An array then only stores the pointer to the first element. If you want the element at position 8, the algorithm will have to hop from the first element to the second, to the third, ..., to the 8th in order to fetch the stored data. While there are ways to improve the time (via sorted trees, additional pointers, location and sequence of the data in memory), it should be clear from the description why data access via an array can be slower. We would note the access time as O(n) .
One thing to keep in mind is, that we do not know how much time one unit is (it's very theoretical). For example, given one element, an array might be faster, since the Hashmap has to do a calculation, but the array just has to read the memory location. That's why it is very important to do benchmarks for your specific use-case in order to choose the best option (if speed is what you need).
Also, for real-time applications, arrays are a no-go, because you don't know when they finish with a data look-up.
Marco Alka
Software Engineer, Technical Consultant & Mentor
the difference is how the elements are searched. Let's take an easy example (not necessary a reflection of the real world) in order to compare the two.
Scenario You have a memory, which has a certain size. For this example, it has enough space to store 10 pieces of information (whatever you want to put into your hashmap or array).
Hashmap The Hashmap is a key-value store. It will take your key and calculate a memory position for the value. Since it always uses the same algorithm to get the correct location, it will always take the same amount of time to return the value. Let's say, you use an integer as a key, then a very simple algorithm could just be a calculation of
key mod memory_size, so the pair(13, "Hello")would be stored at memory location 3 (if the first location has the index 1). Of course, there is more logic in place to make sure that no data is overwritten! One would note the access time asO(1)Array How an array looks up its data highly depends on the implementation. However, the simplest approach would be to use a linked list (for example C/C++ uses that kind of implementation for arrays and std strings). That means that your data is stored together with a pointer to the next element. An array then only stores the pointer to the first element. If you want the element at position 8, the algorithm will have to hop from the first element to the second, to the third, ..., to the 8th in order to fetch the stored data. While there are ways to improve the time (via sorted trees, additional pointers, location and sequence of the data in memory), it should be clear from the description why data access via an array can be slower. We would note the access time as
O(n).One thing to keep in mind is, that we do not know how much time one unit is (it's very theoretical). For example, given one element, an array might be faster, since the Hashmap has to do a calculation, but the array just has to read the memory location. That's why it is very important to do benchmarks for your specific use-case in order to choose the best option (if speed is what you need).
Also, for real-time applications, arrays are a no-go, because you don't know when they finish with a data look-up.