- Notifications
You must be signed in to change notification settings - Fork55
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
vartable=newHashTable(100);//an empty hash table of size 100
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.
vartable=newHashTable(100);table.insert(0,"John");
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.
vartable=newHashTable(100);table.insert(0,"John");table.insert(1,"Jenny");table.insert(0,"John's father");table.deleteKey(0);//only "John" will be removed
m: is the number of keys stored divided by the size of the table.
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.
vartable=newHashTable(100);table.insert(0,"John");table.insert(1,"Jenny");table.insert(0,"John's father");table.deleteAllKey(0);//the table contains only "Jenny"
m: is the number of keys stored divided by the size of the table.
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.
vartable=newHashTable(100);table.insert(0,"John");table.insert(1,"Jenny");table.insert(0,"John's father");table.search(0);//"John"
m: is the number of keys stored divided by the size of the table.
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.
vartable=newHashTable(100);table.insert(0,"John");table.insert(1,"Jenny");table.insert(0,"John's father");table.searchAll(0);//["John", "John's father"]
m: is the number of keys stored divided by the size of the table.
This method empty the table.
vartable=newHashTable(100);table.insert(0,"John");table.clear();//the table is empty
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.
vartable=newHashTable(100);table.insert(0,"John");table.insert(1,"Jenny");table.containsKey(0);//truetable.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.
vartable=newHashTable(100);table.insert(4,"John");table.insert(5,"Jenny");varcallback=function(key){//this function checks if there is a key lower than 5.returnkey<5;};table.contains(null,callback);//true
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.
vartable=newHashTable(100);table.insert(4,"John");table.insert(5,"Jenny");table.insert(varcallback=function(item){//this function append the gender to the itemif(item==="John")returnitem+" is a male";returnitem+" 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.
vartable=newHashTable(100);table.insert(0,"John");table.insert(1,"Jenny");varcallback=function(item){//this function encapsulate each item into an objectif(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"}
This method returns the size of the table.
vartable=newHashTable(100);table.getSize();//100
This method returns the number of keys stored in the table so the number of items stored.
vartable=newHashTable(100);table.getNumberOfKeys();//0table.insert(0,"John");table.insert(1,"Jenny");table.getNumberOfKeys();//2
This method returns the keys stored in the table.
vartable=newHashTable(100);table.getKeys();//[]table.insert(0,"John");table.insert(1,"Jenny");table.getKeys();//[0, 1]
This method returns the items stored in the table.
vartable=newHashTable(100);table.getKeys();//[]table.insert(0,"John");table.insert(1,"Jenny");table.getKeys();//["John", "Jenny"]
This method checks if the table is empty or not.
vartable=newHashTable(100);table.isEmpty()//truetable.insert(0,"John");table.insert(1,"Jenny");table.isEmpty();//false
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.
vartable=newHashTable(100);table.insert(0,"John");table.insert(1,"Jenny");varcallback=function(item){//this function checks if the item's length is at least 5returnitem.length>4;};table.filter(callback);//["Jenny"];
In this example we deal with more complex items.
varitemA={parent:null,item:0};varitemB={parent:itemA,item:1};varitemC={parent:itemB,item:2};varitemD={parent:null,item:3};vartable=newTable(100);table.insert(0,itemA);table.insert(1,itemB);table.insert(2,itemC);table.insert(3,itemD);varcallback=function(item){//this function checks if itemA is in the same hierarchy of the itemwhile(item.parent||item===itemA)item=item.parent;returnitem===itemA;};table.filter(callback);//[itemC, itemB, itemA]
This method returns a clone of the table. The items are cloned only if there's a methodclone() to invoke, otherwise they will be shared with the old table. This problem there is not if items are not object.
vartable=newHashTable(100);table.insert(0,"John");table.insert(1,"Jenny");varclone=table.clone();//clone contains (0, "John"), (1, "Jenny")