Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
Socket
Sign inDemoInstall
Socket
Sign inDemoInstall

iterable-hash-table

Package Overview
Dependencies
Maintainers
1
Versions
24
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

iterable-hash-table - npm Package Compare versions

Comparing version 2.1.0 to 2.2.0

test/HashTable.test.js

7

package.json
{
"name": "iterable-hash-table",
"version": "2.1.0",
"version": "2.2.0",
"description": "A simple Iterable Hash Table written in TypeScript",

@@ -9,3 +9,3 @@ "main": "public/HashTable.js",

"compile": "tsc",
"test": "echo \"Error: no test specified\" && exit 1"
"test": "jest"
},

@@ -16,3 +16,6 @@ "author": "fluxxfield",

"typescript": "^3.8.2"
},
"devDependencies": {
"jest": "^25.1.0"
}
}

130

public/HashTable.js

@@ -69,2 +69,3 @@ 'use strict';

this._numOfBuckets = 0;
this._originalSize = s;
this._size = s;

@@ -139,6 +140,6 @@ this.length = 0;

*
* @param {any} key
* @return {number}
* @param {any} key The non-hashed value provided by the user, can be any type
* @return {number} The hashed index from running method on the given key
*/
HashTable.prototype.hash = function (key) {
HashTable.prototype._hash = function (key) {
// Does not allow keys or values to be undefined or have a length of 0

@@ -176,3 +177,11 @@ if (key === undefined || key.length === 0) {

;
HashTable.prototype.doubleHash = function (key) {
/**
* doubleHash is a method that is a second simpler hashing function used in tandem with the
* original hash method. This makes it to where, if there is a collision, i is increased and
* doubleHash is used to look for a open bucket.
*
* @param {any} key The non-hashed value provided by the user, can be any type
* @return {number} The hashed index from running method on the given key
*/
HashTable.prototype._doubleHash = function (key) {
// Helper function used to check if a number is Prime

@@ -207,18 +216,31 @@ var isPrime = function (num) {

*
* @param {any} key
* @param {any} value
* @return {number}
* @param {any} key The non-hashed value provided by the user, can be any type
* @param {any} value The value stored at the given key, can be any type
* @return {number} The index of the Hash Table where the key/value pair is stored
*/
HashTable.prototype.set = function (key, value) {
// Does not allow keys or values to be undefined or have a length of 0
if (key === undefined || key.length === 0 || value === undefined || value.length === 0) {
throw ('Insertion of undefined is not possible');
switch (value && key) {
case '':
throw new TypeError('Key or Value cannot be an empty string');
break;
case undefined:
throw new TypeError('Key or Value cannot be undefined');
break;
}
;
var i = 0;
var hashedIndex = this.hash(key) + (i * this.doubleHash(key));
// Because the result of doubleHash is multiplied by i, which starts at zero, the value of
// doubleHash is only used if there is a collision
var hashedIndex = this._hash(key) + (i * this._doubleHash(key));
// While i and the hashedIndex are less than or equal to the size of the Hash Table and while
// the hashedIndex is already an exisiting bucket
while (i <= this._size && hashedIndex <= this._size && this._buckets[hashedIndex]) {
hashedIndex = this.hash(key) + (i++ * this.doubleHash(key));
hashedIndex = this._hash(key) + (i++ * this._doubleHash(key)); //?
// If the hashedIndex in the buckets array is a Map and if the map has the given key
if (this._buckets[hashedIndex] && this._buckets[hashedIndex].has(key)) {
// Break out of the while loop
break;
}
;
}

@@ -233,5 +255,5 @@ ;

;
// Increase the length only if it is a new insertion. We do not want to increase
// the length if we are overriding an already existing value
// If the hashedIndex in the buckets array is a Map and the Map does NOT have the given key
if (!this._buckets[hashedIndex].has(key)) {
// Increase the length because it is a new inserction
this.length++;

@@ -244,3 +266,3 @@ }

if (this._numOfBuckets > ~~(this._size * 0.70)) {
this.resize('increase');
this._resize('increase');
}

@@ -258,20 +280,27 @@ ;

*
* @param {any} key
* @return {boolean}
* @param {any} key The non-hashed value provided by the user, can be any type
* @return {any} The key/value pair at the given key in the Hash Table or false if
* the key does not exist in the Hash Table
*/
HashTable.prototype.get = function (key) {
// Does not allow keys or values to be undefined or have a length of 0
if (key === undefined || key.length === 0) {
throw ('Key cannot be undefined');
// Does not allow keys to be undefined or have a length of 0
switch (key) {
case '':
throw new TypeError('Key or Value cannot be an empty string');
break;
case undefined:
throw new TypeError('Key or Value cannot be undefined');
break;
}
;
var i = 0;
var hashedIndex = this.hash(key) + (i * this.doubleHash(key));
var hashedIndex = this._hash(key) + (i * this._doubleHash(key));
// While i is less then the Hash Tables size and while the hashedIndex is less than the
// Hash Tables size
while (i <= this._size && hashedIndex <= this._size) {
hashedIndex = this.hash(key) + (i++ * this.doubleHash(key));
if (this._buckets[hashedIndex]) {
if (this._buckets[hashedIndex].get(key)) {
return this._buckets[hashedIndex].get(key);
}
;
hashedIndex = this._hash(key) + (i++ * this._doubleHash(key));
// If the hashedIndex in the buckets array is a Map and the Map the given key
if (this._buckets[hashedIndex] && this._buckets[hashedIndex].has(key)) {
// Return the key/value pair at that index
return this._buckets[hashedIndex].get(key);
}

@@ -290,17 +319,24 @@ ;

*
* @param {any} key
* @return {boolean}
* @param {any} key The non-hashed value provided by the user, can be any type
* @return {boolean} A boolean indicating wether or not the key/value pair was successfully
* removed from the Hash Table
*/
HashTable.prototype.delete = function (key) {
// Does not allow keys or values to be undefined or have a length of 0
if (key === undefined || key.length === 0) {
throw ('Key cannot be undefined');
// Does not allow keys to be undefined or have a length of 0
switch (key) {
case '':
throw new TypeError('Key or Value cannot be an empty string');
break;
case undefined:
throw new TypeError('Key or Value cannot be undefined');
break;
}
;
var i = 0;
var hashedIndex = this.hash(key) + (i * this.doubleHash(key));
var hashedIndex = this._hash(key) + (i * this._doubleHash(key));
// While i and the hashedIndex are less than or equal to the size of the Hash Table and while
// the hashedIndex is already an exisiting bucket
while (i <= this._size && hashedIndex <= this._size) {
hashedIndex = this.hash(key) + (i++ * this.doubleHash(key));
hashedIndex = this._hash(key) + (i++ * this._doubleHash(key));
// If the buckets array at the hashedIndex is not undefined
if (this._buckets[hashedIndex]) {

@@ -321,3 +357,3 @@ // If the key/value pair in the bucket was successfully deleted

if (this._numOfBuckets < ~~(this._size * 0.40)) {
this.resize('decrease');
this._resize('decrease');
}

@@ -342,5 +378,6 @@ ;

*
* @param {string} sizeType
* @param {string} sizeType A string indicating wether to increase or decrease the size of
* the Hash Table
*/
HashTable.prototype.resize = function (sizeType) {
HashTable.prototype._resize = function (sizeType) {
var e_2, _a;

@@ -356,3 +393,3 @@ // Helper function used to check if a number is Prime

if (this._numOfBuckets < ~~(this._size * 0.70) && this._numOfBuckets > ~~(this._size * 0.40)) {
throw ('Cannot resize the Hash Table');
throw new Error('Cannot resize the Hash Table when the number of buckets is between 40% and 70%');
}

@@ -362,3 +399,3 @@ ;

if (sizeType !== 'increase' && sizeType !== 'decrease') {
throw ('Invalid resize argument');
throw new Error('Invalid resize argument');
}

@@ -382,4 +419,5 @@ ;

newSize = ~~(this._size / 2);
// Keep decreasing the size untill it is a prime number
while (!isPrime(newSize)) {
// Keep decreasing the size untill it is a prime number and while new size is greater
// than or equal to the original size
while (!isPrime(newSize) && newSize >= this._originalSize) {
newSize--;

@@ -425,5 +463,15 @@ }

;
/**
* Clear is a method that resets the Hash Table back to its initial state
*/
HashTable.prototype.clear = function () {
this._buckets = Array(this._originalSize);
this._size = this._originalSize;
this._numOfBuckets = 0;
this.length = 0;
};
;
return HashTable;
}());
;
export default HashTable;
module.exports = HashTable;

133

src/HashTable.ts

@@ -11,4 +11,5 @@ 'use strict';

class HashTable {
private _buckets: Array<any>
private _buckets: Array<Map<any, any>>
private _numOfBuckets: number
private _originalSize: number
private _size: number

@@ -21,2 +22,3 @@

this._numOfBuckets = 0;
this._originalSize = s;
this._size = s;

@@ -53,6 +55,6 @@ this.length = 0;

*
* @param {any} key
* @return {number}
* @param {any} key The non-hashed value provided by the user, can be any type
* @return {number} The hashed index from running method on the given key
*/
hash(key: any): number {
_hash(key: any): number {
// Does not allow keys or values to be undefined or have a length of 0

@@ -91,3 +93,11 @@ if (key === undefined || key.length === 0) {

doubleHash(key: any): number {
/**
* doubleHash is a method that is a second simpler hashing function used in tandem with the
* original hash method. This makes it to where, if there is a collision, i is increased and
* doubleHash is used to look for a open bucket.
*
* @param {any} key The non-hashed value provided by the user, can be any type
* @return {number} The hashed index from running method on the given key
*/
_doubleHash(key: any): number {
// Helper function used to check if a number is Prime

@@ -123,19 +133,33 @@ const isPrime = (num: number): boolean => {

*
* @param {any} key
* @param {any} value
* @return {number}
* @param {any} key The non-hashed value provided by the user, can be any type
* @param {any} value The value stored at the given key, can be any type
* @return {number} The index of the Hash Table where the key/value pair is stored
*/
set(key: any, value: any): number {
// Does not allow keys or values to be undefined or have a length of 0
if (key === undefined || key.length === 0 || value === undefined || value.length === 0) {
throw ('Insertion of undefined is not possible');
switch (value && key) {
case '':
throw new TypeError('Key or Value cannot be an empty string');
break;
case undefined:
throw new TypeError('Key or Value cannot be undefined');
break;
};
let i: number = 0;
let hashedIndex: number = this.hash(key) + (i * this.doubleHash(key));
// Because the result of doubleHash is multiplied by i, which starts at zero, the value of
// doubleHash is only used if there is a collision
let hashedIndex: number = this._hash(key) + (i * this._doubleHash(key));
// While i and the hashedIndex are less than or equal to the size of the Hash Table and while
// the hashedIndex is already an exisiting bucket
while (i <= this._size && hashedIndex <= this._size && this._buckets[hashedIndex]) {
hashedIndex = this.hash(key) + (i++ * this.doubleHash(key));
hashedIndex = this._hash(key) + (i++ * this._doubleHash(key)); //?
// If the hashedIndex in the buckets array is a Map and if the map has the given key
if (this._buckets[hashedIndex] && this._buckets[hashedIndex].has(key)) {
// Break out of the while loop
break;
};
};

@@ -150,5 +174,5 @@

// Increase the length only if it is a new insertion. We do not want to increase
// the length if we are overriding an already existing value
// If the hashedIndex in the buckets array is a Map and the Map does NOT have the given key
if (!this._buckets[hashedIndex].has(key)) {
// Increase the length because it is a new inserction
this.length++;

@@ -162,3 +186,3 @@ };

if (this._numOfBuckets > ~~(this._size * 0.70)) {
this.resize('increase');
this._resize('increase');
};

@@ -176,21 +200,29 @@

*
* @param {any} key
* @return {boolean}
* @param {any} key The non-hashed value provided by the user, can be any type
* @return {any} The key/value pair at the given key in the Hash Table or false if
* the key does not exist in the Hash Table
*/
get(key: any): boolean {
// Does not allow keys or values to be undefined or have a length of 0
if (key === undefined || key.length === 0) {
throw ('Key cannot be undefined');
// Does not allow keys to be undefined or have a length of 0
switch (key) {
case '':
throw new TypeError('Key or Value cannot be an empty string');
break;
case undefined:
throw new TypeError('Key or Value cannot be undefined');
break;
};
let i: number = 0;
let hashedIndex: number = this.hash(key) + (i * this.doubleHash(key));
let hashedIndex: number = this._hash(key) + (i * this._doubleHash(key));
// While i is less then the Hash Tables size and while the hashedIndex is less than the
// Hash Tables size
while (i <= this._size && hashedIndex <= this._size) {
hashedIndex = this.hash(key) + (i++ * this.doubleHash(key));
hashedIndex = this._hash(key) + (i++ * this._doubleHash(key));
if (this._buckets[hashedIndex]) {
if (this._buckets[hashedIndex].get(key)) {
return this._buckets[hashedIndex].get(key);
};
// If the hashedIndex in the buckets array is a Map and the Map the given key
if (this._buckets[hashedIndex] && this._buckets[hashedIndex].has(key)) {
// Return the key/value pair at that index
return this._buckets[hashedIndex].get(key);
};

@@ -208,13 +240,19 @@ };

*
* @param {any} key
* @return {boolean}
* @param {any} key The non-hashed value provided by the user, can be any type
* @return {boolean} A boolean indicating wether or not the key/value pair was successfully
* removed from the Hash Table
*/
delete(key: any): boolean {
// Does not allow keys or values to be undefined or have a length of 0
if (key === undefined || key.length === 0) {
throw ('Key cannot be undefined');
// Does not allow keys to be undefined or have a length of 0
switch (key) {
case '':
throw new TypeError('Key or Value cannot be an empty string');
break;
case undefined:
throw new TypeError('Key or Value cannot be undefined');
break;
};
let i: number = 0;
let hashedIndex: number = this.hash(key) + (i * this.doubleHash(key));
let hashedIndex: number = this._hash(key) + (i * this._doubleHash(key));

@@ -224,4 +262,5 @@ // While i and the hashedIndex are less than or equal to the size of the Hash Table and while

while (i <= this._size && hashedIndex <= this._size) {
hashedIndex = this.hash(key) + (i++ * this.doubleHash(key));
hashedIndex = this._hash(key) + (i++ * this._doubleHash(key));
// If the buckets array at the hashedIndex is not undefined
if (this._buckets[hashedIndex]) {

@@ -243,3 +282,3 @@ // If the key/value pair in the bucket was successfully deleted

if (this._numOfBuckets < ~~(this._size * 0.40)) {
this.resize('decrease');
this._resize('decrease');
};

@@ -262,5 +301,6 @@

*
* @param {string} sizeType
* @param {string} sizeType A string indicating wether to increase or decrease the size of
* the Hash Table
*/
resize(sizeType: string) {
_resize(sizeType: string) {
// Helper function used to check if a number is Prime

@@ -275,3 +315,3 @@ const isPrime = (num: number): boolean => {

if (this._numOfBuckets < ~~(this._size * 0.70) && this._numOfBuckets > ~~(this._size * 0.40)) {
throw ('Cannot resize the Hash Table');
throw new Error('Cannot resize the Hash Table when the number of buckets is between 40% and 70%');
};

@@ -281,3 +321,3 @@

if (sizeType !== 'increase' && sizeType !== 'decrease') {
throw ('Invalid resize argument');
throw new Error('Invalid resize argument');
};

@@ -303,4 +343,5 @@

// Keep decreasing the size untill it is a prime number
while (!isPrime(newSize)) {
// Keep decreasing the size untill it is a prime number and while new size is greater
// than or equal to the original size
while (!isPrime(newSize) && newSize >= this._originalSize) {
newSize--;

@@ -334,4 +375,14 @@ };

};
/**
* Clear is a method that resets the Hash Table back to its initial state
*/
clear() {
this._buckets = Array(this._originalSize);
this._size = this._originalSize;
this._numOfBuckets = 0;
this.length = 0;
};
};
export default HashTable
module.exports = HashTable;
SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc