An associative array uses a string index instead of an integer, with a hash function converting the string to an integer index. Collision can occur, which can be solved through chaining or linear probing.
An associative array, also called a hash table or hash map, is similar to a standard array except that the index of the array can be a string rather than an integer. In many database applications and other programs that deal with large amounts of data, an associative array is a vital element to help sort and access information efficiently. At the heart of an associative array is a standard array indexed with integers, as would normally be the case. A special algorithm called a hash function converts the string index to an integer index to find the value. This is a consistent conversion, so the actual integer index never needs to be stored, but is instead computed from the string whenever needed.
The terminology used when referring to an associative array may be slightly different from that used when referring to a regular array. What you would normally call an index – the numerical position of an element within an array – is called a key. The data associated with the key is called the value. This means that, within an associative array, a key is associated with a value, which is related to an index referencing an element in a standard array in the data structure.
At the heart of any associative array is the hash function. This is an algorithm used to determine the numerical index of a value based on the key. There are several types of hash functions, some designed to operate on keys that are integers and some designed to operate on keys that are strings. In the case of an integer key, a popular method is to divide the key value by the size of the array and use the remainder of the division to hopefully obtain a unique index value.
The hash function can be much more complex for keys that are strings. Some methods include adding the numeric value of each character in the string and then dividing it by a number, or using only the first few characters of the string to get a unique number. There are many ways to derive a number from a string of characters.
When dealing with a large amount of key-value pairs in an associative array, a problem that can arise is called a collision. The collision occurs when the integer index derived from one key is identical to the integer index of another key. These two keys then effectively point to the same index in the array of values. There are various solutions to the collision, mainly because it has a high probability of occurring in most practical applications.
One solution to the collision is to make each value index effectively a linked list so that when more than one key resolves to that index position, the position can contain more than one value. This is called chaining and is an easy way to handle a collision, although it can also slow down the time it takes to retrieve the information. Another method of dealing with a collision is called a linear probing. When a collision occurs, linear detection works by moving through the array of values until an unused index is found. This solution can help keep the data evenly distributed across the associative array, but it can also increase the amount of time it takes to look up a value.
Protect your devices with Threat Protection by NordVPN
