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.0.2 to 2.1.0

README.md

2

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

@@ -5,0 +5,0 @@ "main": "public/HashTable.js",

149

public/HashTable.js

@@ -147,3 +147,43 @@ 'use strict';

;
var i;
var length = key.length - 3;
var t0 = 0;
var t1 = 0;
var v0 = 0x9dc5;
var v1 = 0x811c;
for (i = 0; i < length; i++) {
v0 ^= key.toString().charCodeAt();
t0 = v0 * 403;
t1 = v1 * 403;
t1 += v0 << 8;
v1 = (t1 + (t0 >>> 16)) & 65535;
v0 = t0 & 65535;
}
;
while (i < length + 3) {
v0 ^= key.toString().charCodeAt(i++);
t0 = v0 * 403;
t1 = v1 * 403;
t1 += v0 << 8;
v1 = (t1 + (t0 >>> 16)) & 65535;
v0 = t0 & 65535;
}
;
return (((v1 << 16) >>> 0) + v0) % this._size;
};
;
HashTable.prototype.doubleHash = function (key) {
// Helper function used to check if a number is Prime
var isPrime = function (num) {
for (var i = 2, s = Math.sqrt(num); i <= s; i++)
if (num % i === 0)
return false;
return num > 1;
};
var PRIME = this._size - 1;
var hash = 0;
while (!isPrime(PRIME)) {
PRIME--;
}
;
for (var i = 0; i < key.length; i++) {

@@ -156,5 +196,3 @@ // hash << 5 transalets to: hash * (2 ** 5)

;
// Keeps the output number positive and does not allow it to be any larger then the size
// of the hash table
return Math.abs(hash % this._size);
return PRIME - Math.abs(hash % PRIME);
};

@@ -178,12 +216,20 @@ ;

;
var index = this.hash(key);
// If the bucket is empty at this index
if (!this._buckets[index]) {
var i = 0;
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));
}
;
// If the bucket is empty at this hashedIndex
if (!this._buckets[hashedIndex]) {
// Create a bucket
this._buckets[index] = new Map();
this._buckets[hashedIndex] = new Map();
this._numOfBuckets++;
}
;
// Increase the length only if it is a new insertion
if (!this._buckets[index].has(key)) {
// 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 (!this._buckets[hashedIndex].has(key)) {
this.length++;

@@ -193,3 +239,3 @@ }

// Add key value pair to the bucket
this._buckets[index].set(key, value);
this._buckets[hashedIndex].set(key, value);
// Resize the buckets array if the buckets array is 70% full

@@ -200,3 +246,3 @@ if (this._numOfBuckets > ~~(this._size * 0.70)) {

;
return index;
return hashedIndex;
};

@@ -212,3 +258,3 @@ ;

* @param {any} key
* @return {any}
* @return {boolean}
*/

@@ -221,15 +267,16 @@ HashTable.prototype.get = function (key) {

;
var index = this.hash(key);
// If there is no bucket
if (!this._buckets[index]) {
// Return null
return null;
var i = 0;
var hashedIndex = this.hash(key) + (i * this.doubleHash(key));
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);
}
;
}
;
}
;
// If the key happens to hash to a valid index but the key does not exist in the Map
if (this._buckets[index].get(key) === undefined) {
return null;
}
// Otherwise return the value at the given key
return this._buckets[index].get(key);
return false;
};

@@ -252,31 +299,34 @@ ;

;
var index = this.hash(key);
// If there is no bucket at the given key
if (!this._buckets[index]) {
// Return null
return null;
}
;
// If the key/value pair in the bucket was successfully deleted
if (this._buckets[index].delete(key)) {
// Decrease the length since an key/value pair was removed
this.length--;
// If the Map is now empty
if (this._buckets[index].size === 0) {
// Delete the map, this does not alter the buckets array length
delete this._buckets[index];
// Decrease the number of buckets
this._numOfBuckets--;
var i = 0;
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));
if (this._buckets[hashedIndex]) {
// If the key/value pair in the bucket was successfully deleted
if (this._buckets[hashedIndex].delete(key)) {
// Decrease the length since an key/value pair was removed
this.length--;
// If the Map is now empty
if (this._buckets[hashedIndex].size === 0) {
// Delete the map, this does not alter the buckets array length
delete this._buckets[hashedIndex];
// Decrease the number of buckets
this._numOfBuckets--;
}
;
// If the number of buckets is less than 40%
if (this._numOfBuckets < ~~(this._size * 0.40)) {
this.resize('decrease');
}
;
// Return true indicating that the key/value pair was removed
return true;
}
;
}
;
// If the number of buckets is less than 20%
if (this._numOfBuckets < ~~(this._size * 0.20)) {
this.resize('decrease');
}
;
// Return true indicating that the key/value pair was removed
return true;
}
;
// Return false if there was no key/value pair to remove
return false;

@@ -303,3 +353,3 @@ };

// If the buckets array is less than 70% or greater than 20% full
if (this._numOfBuckets < ~~(this._size * 0.70) && this._numOfBuckets > ~~(this._size * 0.20)) {
if (this._numOfBuckets < ~~(this._size * 0.70) && this._numOfBuckets > ~~(this._size * 0.40)) {
throw ('Cannot resize the Hash Table');

@@ -368,2 +418,3 @@ }

;
oldBucketsArray = [];
};

@@ -370,0 +421,0 @@ ;

161

src/HashTable.ts

@@ -60,5 +60,46 @@ 'use strict';

let hash = 0;
let i: number;
let length: number = key.length - 3;
let t0: number = 0;
let t1: number = 0;
let v0: number = 0x9dc5;
let v1: number = 0x811c;
for (let i = 0; i < key.length; i++) {
for (i = 0; i < length; i++) {
v0 ^= key.toString().charCodeAt();
t0 = v0 * 403;
t1 = v1 * 403;
t1 += v0 << 8;
v1 = (t1 + (t0 >>> 16)) & 65535;
v0 = t0 & 65535;
};
while (i < length + 3) {
v0 ^= key.toString().charCodeAt(i++);
t0 = v0 * 403;
t1 = v1 * 403;
t1 += v0 << 8;
v1 = (t1 + (t0 >>> 16)) & 65535;
v0 = t0 & 65535
};
return (((v1 << 16) >>> 0) + v0) % this._size
};
doubleHash(key: any): number {
// Helper function used to check if a number is Prime
const isPrime = (num: number): boolean => {
for (let i = 2, s = Math.sqrt(num); i <= s; i++)
if (num % i === 0) return false;
return num > 1;
};
let PRIME: number = this._size - 1;
let hash: number = 0;
while (!isPrime(PRIME)) {
PRIME--;
};
for (let i: number = 0; i < key.length; i++) {
// hash << 5 transalets to: hash * (2 ** 5)

@@ -70,5 +111,3 @@ hash = (hash << 5) - hash + key.toString().charCodeAt(i);

// Keeps the output number positive and does not allow it to be any larger then the size
// of the hash table
return Math.abs(hash % this._size)
return PRIME - Math.abs(hash % PRIME);
};

@@ -92,13 +131,21 @@

let index = this.hash(key);
let i: number = 0;
let hashedIndex: number = this.hash(key) + (i * this.doubleHash(key));
// If the bucket is empty at this index
if (!this._buckets[index]) {
// 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));
};
// If the bucket is empty at this hashedIndex
if (!this._buckets[hashedIndex]) {
// Create a bucket
this._buckets[index] = new Map();
this._buckets[hashedIndex] = new Map();
this._numOfBuckets++;
};
// Increase the length only if it is a new insertion
if (!this._buckets[index].has(key)) {
// 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 (!this._buckets[hashedIndex].has(key)) {
this.length++;

@@ -108,3 +155,3 @@ };

// Add key value pair to the bucket
this._buckets[index].set(key, value);
this._buckets[hashedIndex].set(key, value);

@@ -116,3 +163,3 @@ // Resize the buckets array if the buckets array is 70% full

return index
return hashedIndex
};

@@ -128,5 +175,5 @@

* @param {any} key
* @return {any}
* @return {boolean}
*/
get(key: any): any {
get(key: any): boolean {
// Does not allow keys or values to be undefined or have a length of 0

@@ -137,17 +184,16 @@ if (key === undefined || key.length === 0) {

let index = this.hash(key);
let i: number = 0;
let hashedIndex: number = this.hash(key) + (i * this.doubleHash(key));
// If there is no bucket
if (!this._buckets[index]) {
// Return null
return null
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);
};
};
};
// If the key happens to hash to a valid index but the key does not exist in the Map
if (this._buckets[index].get(key) === undefined) {
return null
}
// Otherwise return the value at the given key
return this._buckets[index].get(key)
return false
};

@@ -170,33 +216,35 @@

let index = this.hash(key);
let i: number = 0;
let hashedIndex: number = this.hash(key) + (i * this.doubleHash(key));
// If there is no bucket at the given key
if (!this._buckets[index]) {
// Return null
return null
};
// 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));
// If the key/value pair in the bucket was successfully deleted
if (this._buckets[index].delete(key)) {
// Decrease the length since an key/value pair was removed
this.length--
if (this._buckets[hashedIndex]) {
// If the key/value pair in the bucket was successfully deleted
if (this._buckets[hashedIndex].delete(key)) {
// Decrease the length since an key/value pair was removed
this.length--
// If the Map is now empty
if (this._buckets[index].size === 0) {
// Delete the map, this does not alter the buckets array length
delete this._buckets[index];
// Decrease the number of buckets
this._numOfBuckets--
};
// If the Map is now empty
if (this._buckets[hashedIndex].size === 0) {
// Delete the map, this does not alter the buckets array length
delete this._buckets[hashedIndex];
// Decrease the number of buckets
this._numOfBuckets--
};
// If the number of buckets is less than 20%
if (this._numOfBuckets < ~~(this._size * 0.20)) {
this.resize('decrease');
// If the number of buckets is less than 40%
if (this._numOfBuckets < ~~(this._size * 0.40)) {
this.resize('decrease');
};
// Return true indicating that the key/value pair was removed
return true
};
};
// Return true indicating that the key/value pair was removed
return true
};
// Return false if there was no key/value pair to remove
return false

@@ -215,3 +263,3 @@ };

// Helper function used to check if a number is Prime
const isPrime = num => {
const isPrime = (num: number): boolean => {
for (let i = 2, s = Math.sqrt(num); i <= s; i++)

@@ -223,3 +271,3 @@ if (num % i === 0) return false;

// If the buckets array is less than 70% or greater than 20% full
if (this._numOfBuckets < ~~(this._size * 0.70) && this._numOfBuckets > ~~(this._size * 0.20)) {
if (this._numOfBuckets < ~~(this._size * 0.70) && this._numOfBuckets > ~~(this._size * 0.40)) {
throw ('Cannot resize the Hash Table');

@@ -233,3 +281,3 @@ };

let newSize = 0;
let newSize: number = 0;

@@ -262,3 +310,3 @@ // If the hashTable needs to increase in size

// Create a copy of the current buckets array
let oldBucketsArray = this._buckets.slice();
let oldBucketsArray: Array<Map<any, any>> = this._buckets.slice();

@@ -271,3 +319,3 @@ // Replace the current buckets array with the new array and reset the length and numOfBuckets

// Loop over the old buckets array
for (let i = 0, len = oldBucketsArray.length; i < len; i++) {
for (let i: number = 0, len = oldBucketsArray.length; i < len; i++) {
// If the bucket exists

@@ -282,2 +330,3 @@ if (oldBucketsArray[i] !== undefined) {

};
oldBucketsArray = [];
};

@@ -284,0 +333,0 @@ };

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