Implement simple Linked HashMap using PHP

morcossameh — Tue, 20 Dec 2022 09:28:14 +0000

Linked HashMap is a HashMap that stores the order of its items. Each item have a pointer to the previous inserted item and a pointer to the next Item.

To handle the collision, we will use separate chaining technique for simplicity. For more information, you can refer to this link.

Linked HashMap Item

First, let's create a class for the Linked HashMap item:

class LinkedHashMapItem {
    public $key;
    public $value;
    public $next;
    public $before;
    public $after;
}

next: is used to handle the collision, if an item have the same hash code as another one, it will be stored in its this attribute.
before: the item that is stored before the current item.
after: the item that is store after the current item.

Now, let's create the Linked HashMap class:

Linked HashMap Class

class LinkedHashMap {
    protected $capacity;
    protected $array;
    protected $head;
    protected $tail;

    function __construct($capacity) {
        $this->capacity = $capacity;
        $this->array = array_fill(0, $capacity, null);
    }

    function getHead() {
        return is_null($this->head) ? null : $this->head->value;
    }

    function getTail() {
        return is_null($this->tail) ? null : $this->tail->value;
    }
}

The capacity is used to store the length, the data is stored in array, head stores the first item and tail stores the last one.

let's make a simple hash function that calculates the hash code based on the modulo result of the key and the capacity. Here it is:

private function calculateHash($value) {
    if(is_string($value)) {
        return ord($value[0]) % $this->capacity;
    } elseif(is_numeric($value)) {
        return $value % $this->capacity;
    }
    return 0;
}

We need to make the put function that is responsible for adding new elements to our Linked HashMap.

The put function

In order to insert a new item, we need first to calculate the hash code:

$hash = $this->calculateHash($key);

Next, we need to build the new item object, change assignment of the tail and the head if needed:

$newItem = new LinkedHashMapItem();
$newItem->key = $key;
$newItem->value = $value;

$lastAddedItem = $this->tail;
$newItem->before = $lastAddedItem;

if(!is_null($this->head)) {
    $lastAddedItem->after = $newItem;
}

if(is_null($this->head)) {
    $this->head = $newItem;
}
$this->tail = $newItem;

Now, let's check if a collision exists or not. If there is a collision, we will handle it by getting the last element inserted in this particular position and append the new element to it.

$lastItem = $this->array[$hash];
while(!is_null($lastItem->next)) {
    $lastItem = $lastItem->next;
}
$lastItem->next = $newItem;

If no collision exists, we will just add the new element:

$this->array[$hash] = $newItem;

That's all for the put function, let's move to the get function.

The get function

This one is simple and straightforward. First, we need to calculate the hash code. Next, we will loop the position until we match the keys. If the key is not found, just return -1.

function get($key) {
    $hash = $this->calculateHash($key);

    $item = $this->array[$hash];
    do {
        if($item->key === $key) {
            return $item->value;
        }
        $item = $item->next;
    } while(!is_null($item));

    return -1;
}

Final Result

After combining the previous snippets, the final LinkedHashMap class should be something like: