Pen Settings

HTML

CSS

CSS Base

Vendor Prefixing

Add External Stylesheets/Pens

Any URL's added here will be added as <link>s in order, and before the CSS in the editor. If you link to another Pen, it will include the CSS from that Pen. If the preprocessor matches, it will attempt to combine them before processing.

+ add another resource

JavaScript

Babel includes JSX processing.

Add External Scripts/Pens

Any URL's added here will be added as <script>s in order, and run before the JavaScript in the editor. You can use the URL of any other Pen and it will include the JavaScript from that Pen.

+ add another resource

Packages

Add Packages

Search for and use JavaScript packages from npm here. By selecting a package, an import statement will be added to the top of the JavaScript editor for this package.

Behavior

Save Automatically?

If active, Pens will autosave every 30 seconds after being saved once.

Auto-Updating Preview

If enabled, the preview panel updates automatically as you code. If disabled, use the "Run" button to update.

Format on Save

If enabled, your code will be formatted when you actively save your Pen. Note: your code becomes un-folded during formatting.

Editor Settings

Code Indentation

Want to change your Syntax Highlighting theme, Fonts and more?

Visit your global Editor Settings.

HTML

              
                <div id="mocha"></div>
              
            
!

CSS

              
                
              
            
!

JS

              
                /*
HASH TABLE
Collection of key-value pairs.
Map keys to values for efficient lookup.
Use an array as the underlying data structure.
Hash table should have a size - this will be used by the hashing function to determine what index to map the key to.
A hashing function is used to map the key to an integer, which is the index that the value is to be stored at.
Since our hashing function might map multiple keys to the same integer, we have to deal with collisions by creating buckets at each index of the storage array. These buckets can be arrays or linked lists.
*** Note:
ES6 includes a Map data structure. It differs from the JavaScript object because the keys can be any value (not just strings like for objects), there is a size property, and there is a guaranteed order (the insertion order).
Hash tables are also referred to as hash mapse or dictionaries.
*** Operations:
myMap.set(key, value)
=> myMap object
Store the key-value pair in the storage array.
If the key already exists, replace stored value with new value.
Use the hashing function to map the key to an integer and store the value at the corresponding index.
Account for the possibility of collisions.
myMap.get(key)
=> value associated with key, or undefined if none
myMap.has(key)
=> true/false depending on if a value has been associated with the key
myMap.delete(key)
=> true if a value was associated with the key
=> false if a value was never associated with the key
Remove any value associated to the key
myMap.count()
=> integer number of key/value pairs in hash table
myMap.forEach(callbackFn)
=> no returned value
Invokes callback function once for each key-value pair in the hash table
*** Additional Exercises:
Resize the hash table:
- if the count becomes greater than 75% of the table size, double the table size and redistribute the key/value pairs
- if the count becomes less than 25% of the table size, cut the table size in half and redistribute the key/value pairs
*/

// Simple hashing function to use in your implementation
function simpleHash(str, tableSize) {
  var hash = 0;
  for (var i = 0; i < str.length; i++) {
    hash += str.charCodeAt(i) * (i + 1);
  }
  return hash % tableSize;
}
// source: http://pmav.eu/stuff/javascript-hashing-functions/source.html

function HashTable(tableSize) {
  this._size = tableSize;
  this._storage = [];
  this._count = 0;
}

// This is a helper method that you may want to implement to help keep your code DRY
// You can implement the hash table methods without it.
// I recommend skipping it and coming back if you find that it will be useful
HashTable.prototype.find = function(key) {
  var hash = simpleHash(key, this._size);
  this._storage[hash] = this._storage[hash] || [];
  var bucket = this._storage[hash];

  var match;
  var matchIndex;
  bucket.forEach(function(item, index) {
    if (item.hasOwnProperty(key)) {
      match = item;
      matchIndex = index;
    }
  });

  return {
    match: match,
    bucket: bucket,
    matchIndex: matchIndex
  };
};

HashTable.prototype.resize = function(newSize) {
  var oldStorage = this._storage;
  this._size = newSize;
  this._count = 0;
  this._storage = [];
  var that = this;
  oldStorage.forEach(function(bucket) {
    bucket.forEach(function(item) {
      var key = Object.keys(item)[0];
      that.set(key, item[key]);
    });
  });
};

HashTable.prototype.set = function(key, value) {
  var tmp = this.find(key);
  var match = tmp.match;
  var bucket = tmp.bucket;

  if (match) {
    match[key] = value;
  } else {
    var newItem = [];
    newItem[key] = value;
    this._count++;
    bucket.push(newItem);
    if (this._count > 0.75 * this._size) {
      this.resize(2 * this._size);
    }
  }
  return this;
};
// Time complexity: O(1);

HashTable.prototype.get = function(key) {
  var match = this.find(key).match;
  return match && match[key];
};
// Time complexity: O(1);

HashTable.prototype.has = function(key) {
  return !!this.find(key).match;
};
// Time complexity: O(1);

HashTable.prototype.delete = function(key) {
  var match = this.find(key)
  if (match.match) {
    var bucket = match.bucket;
    var matchIndex = match.matchIndex;
    bucket.splice(matchIndex, 1);
    this._count--;
    if (this._count < 0.25 * this._size) {
      this.resize(0.5 * this._size);
    }
  }
  return !!match.match;
};
// Time complexity: O(1);

HashTable.prototype.count = function() {
  return this._count;
};
// Time complexity: O(1);

HashTable.prototype.forEach = function(callback) {
  this._storage.forEach(function(bucket) {
    bucket = bucket || [];
    bucket.forEach(function(item) {
      callback(item);
    });
  });
};
// Time complexity: O(1);

/*
*** Exercises:
1. Implement a hash table with a binary search tree.
2. Given two arrays with values, return the values that are present in both. Do this in linear time.
3. Implement a hash table using linked lists for collision-handling. Why might this be preferable to using arrays.
*/

var simpleHashFunction = function(input) {
  var output = 0;
  for (var i = 0; i < input.length; i++) {
    output += input.charCodeAt(i);
  }
  return output;
};

var complexHashFunction = function(input) {
  var output = 0,
    i = 0,
    code;
  for (i; i < input.length; i++) {
    code = input.charCodeAt(i);
    output += Math.floor((code * 257) / 13);
  }
  return output.toString(16);
};

/*===== TEST =====*/
mocha.setup('bdd');
var expect = chai.expect;
describe("Hashes", function() {
  describe("Hash functions", function() {
    it('simple hash a string', function() {
      expect(simpleHashFunction('a')).to.equal(97);
    });
    it('more complex hash', function() {
      expect(complexHashFunction('a')).to.equal('77d');
    });
  })
  describe('Hash Table', function() {
    var myMap = new HashTable(10);
    it('should be an object', function() {
      expect(myMap).to.be.an('object');
    });
    it('add to table', function() {
      expect(myMap.set('key','value')).to.be.ok;
    });
    it('can get value back out', function() {
      expect(myMap.get('key')).to.equal('value');
    });
    it('can determine if item is in the table', function() {
      expect(myMap.has('key')).to.be.ok;
      expect(myMap.has('foo')).to.be.not.ok;
    });
    it('can delete values', function() {
      expect(myMap.delete('key')).to.be.ok;
      expect(myMap.delete('foo')).to.be.not.ok;
      expect(myMap._storage).to.be.deep.equal([,,[]]);
    });
    it('can count the number of items it has', function() {
      expect(myMap._count).to.equal(0);
    })
  })
});
mocha.run();
              
            
!
999px

Console