使用PHP实现简单的链接hashmap-DEV365 开发者社区

链接的hashmap是一个存储其项目顺序的哈希图。每个项目都有指向先前插入项目的指针和一个指向下一个项目的指针。

要处理碰撞，我们将使用单独的链式技术来简单。有关更多信息，您可以参考此link。

链接的hashmap项目

首先，让我们为链接的hashmap项目创建一个类：

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

下一步：用于处理碰撞，如果项目具有与另一个相同的哈希代码，则将存储在其此属性中。
之前：当前项目之前存储的项目。
之后：当前物品之后存储的项目。

现在，让我们创建链接的hashmap类：

链接的hashmap类

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;
    }
}

capacity用于存储长度，数据存储在array中，head存储了第一个项目，而tail存储了最后一个。

让我们制作一个简单的哈希函数，根据密钥和容量的模型结果来计算哈希代码。在这里是：

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

我们需要使put函数负责在我们的链接hashmap中添加新元素。

PUT功能

为了插入一个新项目，我们首先需要计算哈希代码：

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

接下来，我们需要构建新项目对象，如果需要，请更改尾巴和头部的分配：

$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;

现在，让我们检查是否存在碰撞。如果有碰撞，我们将通过将最后一个元素插入此特定位置并将新元素附加到它来处理。

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

如果不存在碰撞，我们将添加新元素：

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

这就是put函数的全部，让我们移动到get函数。

获取功能

这个简单明了。首先，我们需要计算哈希代码。接下来，我们将旋转位置，直到匹配钥匙。如果找不到键，只需返回-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;
}

最后结果

结合了先前的摘要后，最终的LinkedHashmap类应该是：

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;
    }

    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;
    }

    function put($key, $value) {
        $hash = $this->calculateHash($key);
        $newItem = $this->buildNewItem($key, $value);
        if(is_null($this->array[$hash])) {
            $this->array[$hash] = $newItem;
        } else {
            $lastItemInHash = $this->getLastItemInHash($hash);
            $lastItemInHash->next = $newItem;
        }
    }

    private function buildNewItem($key, $value) {
        $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;

        return $newItem;
    }

    private function getLastItemInHash($hash) {
        $lastItem = $this->array[$hash];
        while(!is_null($lastItem->next)) {
            $lastItem = $lastItem->next;
        }
        return $lastItem;
    }

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