Est-il Java HashMap équivalent en PHP?

Tableaux en PHP peut avoir Valeur de la Clé de la structure.

Créer un Java comme HashMap en PHP avec O(1) lire complexité.

Ouvrir un phpsh terminal:

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

La complexité de la $myhashmap['mykey2'] dans ce cas semble être à temps constant O(1), ce qui signifie que la taille de $myhasmap approche de l'infini, la quantité de temps qu'il faut pour récupérer une valeur d'une clé reste le même.

Preuve le tableau php de lire est la constante de temps:

Exécuter ce par le biais de l'interprète PHP:

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

La boucle ajoute 1 milliard de clés/valeurs, il faut environ 2 minutes pour tous les ajouter dans la table de hachage qui peut épuiser votre mémoire.

Puis voir combien de temps il faut pour faire une recherche:

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

Alors, quelle est la vitesse de tableau PHP carte de recherche?

La 10333 est la clé que nous regardé. 1 million de nanosecondes == 1 milliseconde. La quantité de temps qu'il faut pour obtenir une valeur à partir d'une clé est de 2,06 millions de nanosecondes ou environ 2 millisecondes. Environ la même quantité de temps si le tableau est vide. Cela ressemble à de la constante de temps pour moi.

HashMap qui fonctionne également avec les touches autres que les chaînes et les nombres entiers avec O(1) lecture de la complexité (en fonction de la qualité de votre propre fonction de hachage).

Vous pouvez faire un simple hashMap vous-même. Ce qu'est une table de hachage n'est de stocker des éléments dans un tableau à l'aide de la table de hachage comme index de clé. De hachage fonctions donner des collisions de temps en temps (pas souvent, mais ils peuvent le faire), de sorte que vous avez à stocker plusieurs éléments pour une entrée dans la table de hachage. Que simple, est une table de hachage:

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

Pour qu'il fonctionne il faut aussi une fonction de hachage pour vos clés et un comparateur pour l'égalité (si vous n'avez que quelques articles ou pour une autre raison, n'ont pas besoin de vitesse, vous pouvez laisser la fonction de hachage return 0; tous les articles seront mis dans le même seau et vous obtiendrez O(N) la complexité)

Voici un exemple:

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/>";

Qui donne en sortie:

37
51
true
false
false
false
false