I need PHP object similar to HashMap in Java, but I didn't find when I googled, so if someone knows how I can mimic HashMaps in PHP, help would be appreciated.
6 Answers
Arrays in PHP can have Key Value structure.
13 Comments
Felix Kling
@Gabi: If it walks like a duck, swims like a duck and quacks like a duck... PHP manual says: An array in PHP is actually an ordered map.
Gabi Purcaru
@Felix Kling AFAIK PHP arrays don't have O(1) lookup/insertion/deletion, so they don't quack like hashmaps
jensgram
@Gabi Purcaru Related: Time/Space complexity of PHP Array.
KingCrunch
@Gabi: The internal implementation of arrays in PHP are hash maps.
knub
This is still not a HashMap, because I can't use objects as keys :(.
|
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.
3 Comments
Daniel Valland
Not constant time... Assuming that the underlying implementation is an array-based hashmap, then due to the need to handle collisions, the best you could do is O(log n) in the case where collisions are stored as self-balanced-trees (such as the Java implementation of hashmap), but might even be stored in a linked-list (chaining), which gives a worst-case of O(n). This is true for both insertion and lookup, but average case will be close to O(1)...
Eric Leschinski
For data set size that consume the whole memory of one computer (say 8 GB), lookup time is a handful of milliseconds. So it's "so close to constant time it's basically constant time", but if you want to be mathematically correct carrying things out to 10 billion boxes carried out to infinity, it's O(n log n). I can nitpick too. :) I use constant time here means "This won't be your bottleneck bro, don't even trip dog".
Daniel Valland
I agree, it probably will not be a bottleneck, as O(log n) for all operations are still very fast. Point is just that the only way to get constant time hashing is if the hashfunction is perfect, and no colission can exist. If not perfect, the best you get is O(log n). However, according to: phpinternalsbook.com/hashtables/basic_structure.html php uses chaining, which has a worst-case of O(N). I don't know is that is the case, as I would expect a solution achieving log n to be used, such as self-balanced-tree, but if that is the case, the distinction between O(N) and O(1) is not trivial.
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'
2 Comments
carlosvini
SplObjectStorage has some downsides: When you use foreach, the keys are integers. And you can't retrieve a list of keys and values from it. In my case i decided to use a custom class implementing ArrayAccess, Iterator and Countable.
Olim Saidov
@carlosvini actually you can php.net/manual/en/class.splobjectstorage.php#114059
$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'
2 Comments
diegoaguilar
What if I want to declare an empty array and do the assigns like:
"fruits" => array("a" => "Orange", "b" => "Banana", "c" => "Apple") after?
zamnuts
@Diego
$fruits = array(); $fruits['fruits'] = array('a' => 'Orange',...); ...actually, you could even just do this right off the bat: $fruits['fruits']['a'] = 'Orange'; $fruits['holes']['first'] = 5; $fruits['numbers'][] = 1; you don't even need to necessarily create any of the arrays with array().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
1 Comment
vp_arth
IEqualityComparer should be an interface hereYou 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
$keys = array_keys($array);(and also see sushils answer below)array_keys. You could write a wrapper class if you want to.