在 PHP 中有 JavaHashMap 等价物吗？

Arrays in PHP can have Key Value structure.

$fruits = array (
"fruits"  => array("a" => "Orange", "b" => "Banana", "c" => "Apple"),
"numbers" => array(1, 2, 3, 4, 5, 6),
"holes"   => array("first", 5 => "second", "third")
);


echo $fruits["fruits"]["b"]

outputs 'Banana'

taken from http://in2.php.net/manual/en/function.array.php

Create a Java like HashMap in PHP with O(1) read complexity.

Open a phpsh terminal:

php> $myhashmap = array();
php> $myhashmap['mykey1'] = 'myvalue1';
php> $myhashmap['mykey2'] = 'myvalue2';
php> echo $myhashmap['mykey2'];
myvalue2

The complexity of the $myhashmap['mykey2'] in this case appears to be constant time O(1), meaning that as the size of $myhasmap approaches infinity, the amount of time it takes to retrieve a value given a key stays the same.

Evidence the php array read is constant time:

Run this through the PHP interpreter:

php> for($x = 0; $x < 1000000000; $x++){
... $myhashmap[$x] = $x . " derp";
... }

The loop adds 1 billion key/values, it takes about 2 minutes to add them all to the hashmap which may exhaust your memory.

Then see how long it takes to do a lookup:

php> system('date +%N');echo "  " . $myhashmap[10333] . "  ";system('date +%N');
786946389  10333 derp  789008364

So how fast is the PHP array map lookup?

The 10333 is the key we looked up. 1 million nanoseconds == 1 millisecond. The amount of time it takes to get a value from a key is 2.06 million nanoseconds or about 2 milliseconds. About the same amount of time if the array were empty. This looks like constant time to me.

HashMap that also works with keys other than strings and integers with O(1) read complexity (depending on quality of your own hash-function).

You can make a simple hashMap yourself. What a hashMap does is storing items in a array using the hash as index/key. Hash-functions give collisions once in a while (not often, but they may do), so you have to store multiple items for an entry in the hashMap. That simple is a hashMap:

class IEqualityComparer {
public function equals($x, $y) {
throw new Exception("Not implemented!");
}
public function getHashCode($obj) {
throw new Exception("Not implemented!");
}
}


class HashMap {
private $map = array();
private $comparer;


public function __construct(IEqualityComparer $keyComparer) {
$this->comparer = $keyComparer;
}


public function has($key) {
$hash = $this->comparer->getHashCode($key);


if (!isset($this->map[$hash])) {
return false;
}


foreach ($this->map[$hash] as $item) {
if ($this->comparer->equals($item['key'], $key)) {
return true;
}
}


return false;
}


public function get($key) {
$hash = $this->comparer->getHashCode($key);


if (!isset($this->map[$hash])) {
return false;
}


foreach ($this->map[$hash] as $item) {
if ($this->comparer->equals($item['key'], $key)) {
return $item['value'];
}
}


return false;
}


public function del($key) {
$hash = $this->comparer->getHashCode($key);


if (!isset($this->map[$hash])) {
return false;
}


foreach ($this->map[$hash] as $index => $item) {
if ($this->comparer->equals($item['key'], $key)) {
unset($this->map[$hash][$index]);
if (count($this->map[$hash]) == 0)
unset($this->map[$hash]);


return true;
}
}


return false;
}


public function put($key, $value) {
$hash = $this->comparer->getHashCode($key);


if (!isset($this->map[$hash])) {
$this->map[$hash] = array();
}


$newItem = array('key' => $key, 'value' => $value);


foreach ($this->map[$hash] as $index => $item) {
if ($this->comparer->equals($item['key'], $key)) {
$this->map[$hash][$index] = $newItem;
return;
}
}


$this->map[$hash][] = $newItem;
}
}

For it to function you also need a hash-function for your key and a comparer for equality (if you only have a few items or for another reason don't need speed you can let the hash-function return 0; all items will be put in same bucket and you will get O(N) complexity)

Here is an example:

class IntArrayComparer extends IEqualityComparer {
public function equals($x, $y) {
if (count($x) !== count($y))
return false;


foreach ($x as $key => $value) {
if (!isset($y[$key]) || $y[$key] !== $value)
return false;
}


return true;
}


public function getHashCode($obj) {
$hash = 0;
foreach ($obj as $key => $value)
$hash ^= $key ^ $value;


return $hash;
}
}


$hashmap = new HashMap(new IntArrayComparer());


for ($i = 0; $i < 10; $i++) {
for ($j = 0; $j < 10; $j++) {
$hashmap->put(array($i, $j), $i * 10 + $j);
}
}


echo $hashmap->get(array(3, 7)) . "<br/>";
echo $hashmap->get(array(5, 1)) . "<br/>";


echo ($hashmap->has(array(8, 4))? 'true': 'false') . "<br/>";
echo ($hashmap->has(array(-1, 9))? 'true': 'false') . "<br/>";
echo ($hashmap->has(array(6))? 'true': 'false') . "<br/>";
echo ($hashmap->has(array(1, 2, 3))? 'true': 'false') . "<br/>";


$hashmap->del(array(8, 4));
echo ($hashmap->has(array(8, 4))? 'true': 'false') . "<br/>";

Which gives as output:

37
51
true
false
false
false
false

Depending on what you want you might be interested in the SPL Object Storage class.

http://php.net/manual/en/class.splobjectstorage.php

It lets you use objects as keys, has an interface to count, get the hash and other goodies.

$s = new SplObjectStorage;
$o1 = new stdClass;
$o2 = new stdClass;
$o2->foo = 'bar';


$s[$o1] = 'baz';
$s[$o2] = 'bingo';


echo $s[$o1]; // 'baz'
echo $s[$o2]; // 'bingo'

You could create a custom HashMap class for that in php. example as shown below containing the basic HashMap attributes such as get and set.

class HashMap{


public $arr;


function init() {


function populate() {
return null;
}
            

// change to 999 for efficiency
$this->arr = array_map('populate', range(0, 9));


return $this->arr;


}
        

function get_hash($key) {
$hash = 0;


for ($i=0; $i < strlen($key) ; $i++) {
$hash += ord($key[$i]);
}
            

// arr index starts from 0
$hash_idx = $hash % (count($this->arr) - 1);
return $hash_idx;
            

}


function add($key, $value) {
$idx = $this->get_hash($key);
            

if ($this->arr[$idx] == null) {
$this->arr[$idx] = [$value];
} else{


$found = false;


$content = $this->arr[$idx];
                

$content_idx = 0;
foreach ($content as $item) {


// checking if they have same number of streams
if ($item == $value) {


$content[$content_idx] = [$value];
$found = true;
break;


}
                    

$content_idx++;
}


if (!$found) {
// $value is already an array
array_push($content, $value);


// updating the array
$this->arr[$idx] = $content;
}


}


return $this->arr;


}


function get($key) {


$idx = $this->get_hash($key);
$content = $this->arr[$idx];


foreach ($content as $item) {
if ($item[1] == $key) {
return $item;
break;
}
}
                

}


}

Hope this was useful