Hash Table

In computing, a hash table (also hash map) is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the correct value can be found.

Ideally, the hash function will assign each key to a unique bucket, but this situation is rarely achievable in practice (usually some keys will hash to the same bucket). Instead, most hash table designs assume that hash collisions—different keys that are assigned by the hash function to the same bucket—will occur and must be accommodated in some way.

Wikipedia

var table = new HashTable(100); //an empty hash table of size 100

Methods

insert(key, item)

This method insert the item and the key in the hash table. The item could be whatever you want but the key must be a number.

var table = new HashTable(100);
table.insert(0, "John");

Complexity: O(1)

deleteKey(key)

This method remove the key and the relatives item from the table. If there are various items related to the same key, only the first found will be deleted.

var table= new HashTable(100);
table.insert(0, "John");
table.insert(1, "Jenny");
table.insert(0, "John's father");
table.deleteKey(0); //only "John" will be removed

Complexity: O(m)

m: is the number of keys stored divided by the size of the table.

deleteAllKey(key)

This method remove the key and all the relatives items from the table. If there are various items related to the same key, all these found will be deleted.

var table= new HashTable(100);
table.insert(0, "John");
table.insert(1, "Jenny");
table.insert(0, "John's father");
table.deleteAllKey(0); //the table contains only "Jenny"

Complexity: O(m)

m: is the number of keys stored divided by the size of the table.

search(key)

This method returns the item related to the key. If there are various items related to the same key, only the first will be returned.

var table= new HashTable(100);
table.insert(0, "John");
table.insert(1, "Jenny");
table.insert(0, "John's father");
table.search(0); //"John"

Complexity: O(m)

m: is the number of keys stored divided by the size of the table.

searchAll(key)

This method returns all the items related to the key. If there are various items related to the same key, all these will be returned.

var table= new HashTable(100);
table.insert(0, "John");
table.insert(1, "Jenny");
table.insert(0, "John's father");
table.searchAll(0); //["John", "John's father"] 

Complexity: O(m)

m: is the number of keys stored divided by the size of the table.

clear()

This method empty the table.

var table = new HashTable(100);
table.insert(0, "John");
table.clear(); //the table is empty

Complexity: O(1)

containsKey(key, callback)

This method checks if the queue contains a key that satisfy the condition represented by the callback function. The callback could be omitted. In this case the method checks if the key is simply contained in the table.

var table = new HashTable(100);
table.insert(0, "John");
table.insert(1, "Jenny");
table.containsKey(0); //true
table.containsKey(3); //false

If you desire a more complex research of a key you need to pass also the callback parameter. The callback must accept the key the iteration is working on. In that case the key parameter could be omitted because it won't be used to evaluate the condition.

var table = new HashTable(100);
table.insert(4, "John");
table.insert(5, "Jenny");
var callback = function(key) { //this function checks if there is a key lower than 5.
  return key < 5;
};
table.contains(null, callback); //true

Complexity: O(n)

execute(callback)

This method execute the callback function for each item stored in the table. The callback must accept the item the iteration is working on. The callback must also return a value to assign to the item.

var table = new HashTable(100);
table.insert(4, "John");
table.insert(5, "Jenny");
table.insert(
var callback = function(item) { //this function append the gender to the item
  if(item === "John")
    return item + " is a male";
  return item + " is a female";
};
table.execute(callback); //table contains "John is a male", "Jenny is a female"

In this example we deal with more complex items.

var table = new HashTable(100);
table.insert(0, "John");
table.insert(1, "Jenny");
var callback = function(item) { //this function encapsulate each item into an object
  if(item === "John")
    return {name: item, gender: "male"};
  return {name: item, gender: "female"};
};
table.execute(callback); //table contains {name: "Johnny", gender: "male"}, {name: "Jenny", gender: "female"}

Complexity: O(n)

getSize()

This method returns the size of the table.

var table = new HashTable(100);
table.getSize(); //100

Complexity: O(1)

getNumberOfKeys()

This method returns the number of keys stored in the table so the number of items stored.

var table = new HashTable(100);
table.getNumberOfKeys(); //0
table.insert(0, "John");
table.insert(1, "Jenny");
table.getNumberOfKeys(); //2

Complexity: O(1)

getKeys()

This method returns the keys stored in the table.

var table = new HashTable(100);
table.getKeys(); //[]
table.insert(0, "John");
table.insert(1, "Jenny");
table.getKeys(); //[0, 1]

Complexity: O(n)

getItems()

This method returns the items stored in the table.

var table = new HashTable(100);
table.getKeys(); //[]
table.insert(0, "John");
table.insert(1, "Jenny");
table.getKeys(); //["John", "Jenny"]

Complexity: O(1)

isEmpty()

This method checks if the table is empty or not.

var table = new HashTable(100);
table.isEmpty() //true
table.insert(0, "John");
table.insert(1, "Jenny");
table.isEmpty(); //false

Complexity: O(1)

filter(callback)

This method returns all the items that satisfies the condition represented by the callback. The callback must accept the item the iteration is working on. The order in which the items will be return won't be the same.

var table = new HashTable(100);
table.insert(0, "John");
table.insert(1, "Jenny");
var callback = function(item) { //this function checks if the item's length is at least 5
  return item.length > 4;
};
table.filter(callback); //["Jenny"];

In this example we deal with more complex items.

var itemA = {parent: null, item: 0};
var itemB = {parent: itemA, item: 1};
var itemC = {parent: itemB, item: 2};
var itemD = {parent: null, item: 3};
var table = new Table(100);
table.insert(0, itemA);
table.insert(1, itemB);
table.insert(2, itemC);
table.insert(3, itemD);
var callback = function(item) { //this function checks if itemA is in the same hierarchy of the item
  while(item.parent || item === itemA)
    item = item.parent;
  return item === itemA;
};
table.filter(callback); //[itemC, itemB, itemA]

Complexity: O(n)

clone()

This method returns a clone of the table. The items are cloned only if there's a method clone() to invoke, otherwise they will be shared with the old table. This problem there is not if items are not object.

var table = new HashTable(100);
table.insert(0, "John");
table.insert(1, "Jenny");
var clone = table.clone(); //clone contains (0, "John"), (1, "Jenny")

Complexity: O(n)