Skip to content

Instantly share code, notes, and snippets.

@meetrajesh

meetrajesh/hash_table.php

Created December 14, 2012 05:12
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save meetrajesh/4282835 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save meetrajesh/4282835 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. meetrajesh revised this gist Dec 14, 2012. 1 changed file with 0 additions and 1 deletion.
    1 change: 0 additions & 1 deletion hash_table.php
    View file
    Original file line number Diff line number Diff line change
    @@ -66,7 +66,6 @@ private function _double_table_size() {
    if (!empty($this->_array[$i])) {
    $node = $this->_array[$i];
    $j = $this->_get_index($node->key);

    // check collisions and record them
    if (isset($data[$j]) && $data[$j]->key != $node->key) {
    $collisions[] = $node;
  2. meetrajesh revised this gist Dec 14, 2012. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion hash_table.php
    View file
    Original file line number Diff line number Diff line change
    @@ -2,7 +2,7 @@

    class HashTable {

    private $_array = array();
    private $_array = array();
    private $_size = 10000;

    public function __construct($size=0) {
  3. meetrajesh revised this gist Dec 14, 2012. 1 changed file with 4 additions and 4 deletions.
    8 changes: 4 additions & 4 deletions hash_table.php
    View file
    Original file line number Diff line number Diff line change
    @@ -2,11 +2,11 @@

    class HashTable {

    private $_array = array();
    private $_size = 10000;
    private $_array = array();
    private $_size = 10000;

    public function __construct($size=0) {
    $size = (int)$size;
    public function __construct($size=0) {
    $size = (int)$size;
    if ($size > 0) {
    $this->_size = $size;
    }
  4. meetrajesh revised this gist Dec 14, 2012. 1 changed file with 3 additions and 3 deletions.
    6 changes: 3 additions & 3 deletions hash_table.php
    View file
    Original file line number Diff line number Diff line change
    @@ -3,10 +3,10 @@
    class HashTable {

    private $_array = array();
    private $_size = 10000;
    private $_size = 10000;

    public function __construct($size=0) {
    $size = (int)$size;
    public function __construct($size=0) {
    $size = (int)$size;
    if ($size > 0) {
    $this->_size = $size;
    }
  5. meetrajesh created this gist Dec 14, 2012.
    107 changes: 107 additions & 0 deletions hash_table.php
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,107 @@
    <?php

    class HashTable {

    private $_array = array();
    private $_size = 10000;

    public function __construct($size=0) {
    $size = (int)$size;
    if ($size > 0) {
    $this->_size = $size;
    }
    }

    public function set($key, $val) {
    $i = $orig_i = $this->_get_index($key);
    $node = new HashTableNode($key, $val);

    while (true) {
    if (!isset($this->_array[$i]) || $key == $this->_array[$i]->key) {
    $this->_array[$i] = $node;
    break;
    }
    // increment $i
    $i = (++$i % $this->_size);
    // loop complete
    if ($i == $orig_i) {
    // out of space
    $this->_double_table_size();
    return $this->set($key, $val);
    }
    }
    return $this;
    }

    public function get($key) {
    $i = $orig_i = $this->_get_index($key);
    while (true) {
    if (!isset($this->_array[$i])) {
    return null;
    }
    $node = $this->_array[$i];
    if ($key == $node->key) {
    return $node->val;
    }
    // increment $i
    $i = (++$i % $this->_size);
    // loop complete
    if ($i == $orig_i) {
    return null;
    }
    }
    }

    private function _get_index($key) {
    return crc32($key) % $this->_size;
    }

    private function _double_table_size() {
    $old_size = $this->_size;
    $this->_size *= 2;
    $data = array(); // new array
    $collisions = array(); // to be re-added later

    for ($i=0; $i < $old_size; $i++) {
    if (!empty($this->_array[$i])) {
    $node = $this->_array[$i];
    $j = $this->_get_index($node->key);

    // check collisions and record them
    if (isset($data[$j]) && $data[$j]->key != $node->key) {
    $collisions[] = $node;
    } else {
    $data[$j] = $node;
    }
    }
    }

    $this->_array = $data;

    // manage collisions
    foreach ($collisions as $node) {
    $this->set($node->key, $node->val);
    }
    }

    }

    class HashTableNode {
    public $key;
    public $val;
    public function __construct($key, $val) {
    $this->key = $key;
    $this->val = $val;
    }
    }

    // unit test
    $h = new HashTable(1);
    $h->set('abc', 'def');
    $h->set('ghi', 'test');
    $h->set('def', 'qbc');
    echo $h->get('abc') . "\n";
    echo $h->get('def') . "\n";
    echo $h->get('ghi') . "\n";