Category Archives: javascript

for of loop

July 2, 2018javascriptadmin

Standard Array

for standard arrays, you can definitely use for of and it would log

const iterable = ['mini', 'mani', 'mo'];

for (const value of iterable) {

console.log(value);

}

output:

mini
mani
mo

iterating function argument object

There’s a argument object that is of object Array. You can iterate through it

function args() {

// arguments is an Array-like object

for (const arg of arguments) {

console.log(arg);

}

args('a', 'b', 'c');

output:

a
b
c

sets

const setIterable = new Set([1, 1, 2, 2, 1]);

for (const value of setIterable) {

console.log(value);

}

<b>

output:

</b>

Map

const mapIterable = new Map([['one', 1], ['two', 2]]);

for (const [key, value] of mapIterable) {

console.log(`Key: ${key} and Value: ${value}`);

}

output:
Key: one and Value: 1
Key: two and Value: 2

arguments object (js)

June 27, 2018javascriptudemyadmin

The Arguments Object

In the Create Phase of the Execution context, we know that variables environment, this, and reference to the outer scope is set up. Additionally, it also sets up the arguments object.

Contains the list of all values that we pass into the function we’re calling.

Arguments just another name for parameters we pass into our functions. Parameters and arguments are interchangeable.

In JS, we are given keyword arguments.
During the creation phase, memory space is set for the function definition. Then it has memory space set for the parameters, and assigned them undefined, just like any other variable names.

JavaScript functions have a built-in object called the arguments object.

The argument object contains an array of the arguments used when the function was called (invoked).

This way you can simply use a function to find (for instance) the highest value in a list of numbers:

// we can insert arguments

x = findMax(1, 123, 500, 115, 44, 88);

// notice no parameter id declared

function findMax() {

var i;

var max = -Infinity;

for (i = 0; i < arguments.length; i++) {

if (arguments[i] > max) {

max = arguments[i];

}

return max;

}

..or create a sum function

// input arguments

x = sumAll(1, 123, 500, 115, 44, 88);

// notice no parameter names

function sumAll() {

var i;

var sum = 0;

for (i = 0; i < arguments.length; i++) {

sum += arguments[i];

}

return sum;

}

Arguments are Passed by Value

The parameters, in a function call, are the function’s arguments.

JavaScript arguments are passed by value: The function only gets to know the values, not the argument’s locations.

If a function changes an argument’s value, it does not change the parameter’s original value.

For primitive values changes to arguments are not visible (reflected) outside the function. We copy them in and manipulate them inside the function. However, the outside values stay the same.

function changeIt(first, second) {

arguments[0] = 20;

second = 88;

}

let a = 10;

let b = 66;

changeIt(a, b);

console.log(`a: ${a}, b : ${b}`);

output:
a: 10, b: 66

However, for objects, it’s different. Objects are being pointed to by references. And when you pass in an object, the parameter name will reference that object. Hence you’ll have the outside var reference obj1 reference your literal object, as well as the parameter ‘objRef’ reference that object.

In // 1, we take the reference that’s pointing to the literal object and access its property ‘name’ and then change it. This will work because we’re directly manipulating a reference that’s pointing to the object.

let obj1 = {

name: "testing 1 2 3"

}

function changeIt2(objRef) {

//objRef.name = "success"; // 1 obj1's object will change

// 2 nothing happens to obj1's object

objRef = {

address: "123 Main Street"

}

changeIt2(obj1);

console.log(obj1);

However, in // 2, you see that we take this parameter reference and point it to ANOTHER literal object with the property address.

When we log the results, you’ll see that obj1 did not change. This is because we didn’t do anything to the original object that obj1 is pointing to. Rather, we just took the parameter reference ‘objRef’ and pointed it somewhere else.

spread operator

June 27, 2018javascriptadmin

ref – https://codeburst.io/javascript-the-spread-operator-a867a71668ca

The spread operator allows an expression to be expanded in places where multiple elements/variables/arguments are expected

Doing things in immutable way:

Say you have an object

const meal = {

id: 1,

description: 'breakfast'

}

You want to update it (add a property). Keep everything immutable.
So you’d create another literal object just like meal and add your property.

const updatedMeal = {

id: 1,

description: 'breakfast',

calories: 680, // add this here

}

But this is a lot of typing and too much work if it has many properties.

In order to remedy this, we’d use the spread operator.

const updatedMeal = {

...meal, // adds all properties to this object

description: 'Brunch', // can over-ride original property

calories: 680

}

Now, let’s say we want to use it.

1 2	const description = updatedMeal.description; const calories = updatedMeal.calories;

This is rather tedious and too wordy.
Let’s use Destructuring to get what we need.

1	const { description, calories } = updatedMeal;

How to remove or delete field. Let’s delete id by using rest syntax.

// rest syntax

const { id, ...mealWithoutId } = updatedMeal;

console.log(mealWithoutId);

Now mealWithoutId will have all properties of updatedMeal, without the id.

const meals = [

{id: 1, description: 'breakfast', calories: 420},

{id: 2, description: 'lunch', calories: 520}

]

const meal = {id: 3, description: 'dinner', calories: 620};

1	const updatedMeals = [...meals, meal];

now updatedMeals will have the third meal.

But say we want to update lunch?

array.map(fn) returns a new new array with the updated changes

function updateDescription(meal) {

// make the update here

if (meal.id === 2) {

return {

...meal,

description: 'Early Lunch',

}

const updatedMealsDescription = updatedMeals.map(updateDescription);

Use Array.filter to remove items from array immutably.

const filteredMeals = updatedMeals.filter(function(meal) {

return meal.id !== 1;

});

Various Usages

given…normally, the middle reference in arr would reference var middle. This makes it so that its an array inside of an array. Its not what we want.

var middle = [3, 4];

var arr = [1, 2, middle, 5, 6];

console.log(arr);

// [1, 2, [3, 4], 5, 6]

What we can do is to expand middle’s elements into arr like so:

var middle = [3, 4];

var arr = [1, 2, ...middle, 5, 6];

console.log(arr);

// [1, 2, 3, 4, 5, 6]

Remember the spread operator definition you just read above? Here’s where it comes into play. As you can see, when we create the arr array and use the spread operator on the middle array, instead of just being inserted, the middle array expands. Each element in the middle array is inserted into the arr array. This means that instead of nested arrays, we are left with a simple array of numbers ranging from 1 to 6.

Copying arrays

Voila! We have a copied array. The array values in arr expanded to become individual letters which were then assigned to arr2. We can now change the arr2 array as much as we’d like with no consequences on the original arr array.

var arr = ['a', 'b', 'c'];

var arr2 = [...arr];

console.log(arr2);

// ['a', 'b', 'c']

Appending Arrays

var arr = ['a', 'b', 'c'];

var arr2 = ['d', 'e', 'f'];

arr = [...arr, ...arr2];

console.log(arr);

// ['a', 'b', 'c', 'd', 'e', 'f']

String to Array

Bonus example: Use the spread operator to simply convert a string to an array of characters

var str = "hello";

var chars = [...str];

console.log(chars);

// ['h', 'e',' l',' l', 'o']

No need to use ‘call’

function doStuff (x, y, z) { }

var args = [0, 1, 2];

// Call the function, passing args

doStuff.apply(null, args);

// With the spread operator we can avoid apply all together and

// simply call the function with the spread operator before the array:

doStuff(...args);

default parameters

June 26, 2018javascriptadmin

ref – https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Functions/Default_parameters

function test(num = 1) {

console.log(typeof num);

}

// undefined and empty are treated the same. the compiler will see it as empty and use the default values

test(); // 'number' (num is set to 1)

test(undefined); // 'number' (num is set to 1 too)

// test with other falsy values, the compiler will see it as defined values. Thus, use them

test(''); // 'string' (num is set to '')

test(null); // 'object' (num is set to null)

Evaluated at runtime

The default argument gets evaluated at call time.

function append(value, array = []) {

array.push(value);

return array;

}

append(1); //[1]

append(2); //[2], not [1, 2]

we can even assign functions to it:

function callSomething(thing = something()) {

return thing;

}

function something() {

return 'sth';

}

callSomething(); //sth

function singularAutoPlural(singular, plural = singular + 's',

rallyingCry = plural + ' ATTACK!!!') {

return [singular, plural, rallyingCry];

}

//["Gecko","Geckos", "Geckos ATTACK!!!"]

singularAutoPlural('Gecko');

//["Fox","Foxes", "Foxes ATTACK!!!"]

singularAutoPlural('Fox', 'Foxes');

//["Deer", "Deer", "Deer ... change."]

singularAutoPlural('Deer', 'Deer', 'Deer peaceably and respectfully \

petition the government for positive change.')

with call, argument list, and default parameters

// declare function for a variable to reference

function go() {

return ':P';

}

then we declare a function with defaults.

The 1st param a references 1st param.
We then have 2nd param b, which defaults to 5.
3rd param c copies over from 2nd param.
d param references go function
e references the ‘this’ object, whatever it is pointing.
f references the default argument list
g references the ‘this’ object, and then access its property ‘value’

function withDefaults(a, b = 5, c = b, d = go(), e = this,

f = arguments, g = this.value) {

console.log(`a is referencing param1: ${a}`);

console.log(`b references ${b}`);

console.log(`c references ${c}`);

console.log(`d references function go(), which returns ${d}`);

console.log(`e = this:`);

console.log(e);

console.log(`f[0] = ${f[0]}`);

console.log(g);

return [a, b, c, d, e, f, g];

}

We call the function like so:

1	let a = withDefaults.call({value: '=^_^='}, 6680);

using call, we provide the first object as the ‘this’ object for withDefaults function. the integer 6680 is the 1st parameter.
thus, just from this knowledge:

a will be 6680
e is the {value: ‘=^_^=’}

We then look at the 2nd param which is b = 5.
third is c = b, which means c is 5.
param 4 is d referencing the returned string of function go().
param 5 e reference the this object, which is supplied by our call function’s 1st parameter.
Hence e references {value: ‘=^_^=’}

f references the basic argument list
finally, g references the this object’s value property.

output:

a is referencing param1: 6680
b references 5
c references 5
d references function go(), which returns 😛
e = this:
{ value: ‘=^_^=’ }
f = [object Arguments]
=^_^=

function f([x, y] = [1, 2], {z: z} = {z: 3}) {

return x + y + z;

}

console.log(f([4,4], {z:8})); // 16

Object as Hash

June 26, 2018javascriptadmin

ref – https://medium.com/front-end-hacking/es6-map-vs-object-what-and-when-b80621932373

Object is the great choice for scenarios when we only need simple structure to store data and knew that all the keys are either strings or integers (or Symbol).

An Object in Javascript is dictionary type of data collection — which means it also follows key-value stored concept.

Construction

var obj = {}; //Empty object

var obj1 = {id: 1, name: "Test object"};

// Or by constructor

var obj = new Object(); //Empty Object

var obj1 = new Object; //same result

In general, like in Array, do not use built-in constructor over literal in creating new object, because:

More typing
Slower performance
Confusion & increasing more chances for mistake

for example:

var obj = new Object(id: 1, name: "test") //Error

var obj1 = {id: 1, name: "test"};

var obj2 = new Object(obj1); //obj1 and obj2 points to the same one

obj2.id = 2;

console.log(obj1.id); //2

Setting key/values

let storage = {

// store key:value here

}

You can initialize it with key/value pairs, or simply assign it via brackets.
Each key in Object — or we normally call it “property” — is also unique and associated with a single value.
In addition, Object in Javascript has built-in prototype. And don’t forget, nearly all objects in Javascript are instances of Object.

let storage = {

123: "testing 1 2 3",

"dob" : 6680

};

storage[0] = "this is a dictionary";

console.log(storage[123]); // testing 1 2 3

console.log(storage["dob"]); // 6680

console.log(storage[0]); // this is a dictionary

Object: keys must be in simple types (int, string, or symbol)

In Object, it follows the rule of normal dictionary. The keys MUST be simple types — either integer or string or symbols. As shown previously, strings and integers are used often. However, we can also use symbols.

const symbol1 = Symbol(645);

const symbol2 = Symbol("hadoken");

let storage = {

123: "testing 1 2 3",

"dob" : 6680

};

storage[symbol1] = "645";

storage[symbol2] = "ken and ryu";

console.log(storage[123]); // testing 1 2 3

console.log(storage["dob"]); // 6680

console.log(storage[symbol2]); // ken and ryu

Looping through the Object keys

// shows all keys

for (key in storage) {

console.log(`--> ${key}, ${storage[key]}`);

}

for (const key of Object.keys(storage)) {

console.log(key);

}

Looping through symbols

const symbol1 = Symbol(645);

const symbol2 = Symbol("hadoken");

const symbol3 = Symbol("hadoken");

let storage = {

123: "testing 1 2 3",

"dob" : 6680

};

storage[symbol1] = "645";

storage[symbol2] = "ken and ryu";

storage[symbol3] = "Akuma and Dan";

let i = Object.getOwnPropertySymbols(storage);

console.log(i);

i.forEach(function(symbol, index) {

console.log(`${index}, ${storage[symbol]}`);

});

Notice Object.keys and Object.getOwnPropertySymbols

ref – https://stackoverflow.com/questions/34449045/what-is-the-difference-between-reflect-ownkeysobj-and-object-keysobj

Object.keys() returns an array of strings, which are the object’s own enumerable properties.

The Object.getOwnPropertyNames() method returns an array of all properties (enumerable or not) found directly upon a given object.

for example:

var testObject = {};

Object.defineProperty(testObject, 'myMethod', {

value: function () {

alert("Non enumerable property");

enumerable: false

});

//does not print myMethod since it is defined to be non-enumerable

console.log(Object.keys(testObject));

//prints myMethod irrespective of it being enumerable or not.

console.log(Reflect.ownKeys(testObject));

try catch performance issues

June 25, 2018javascriptadmin

ref –

http://chineseruleof8.com/code/index.php/2018/06/22/try-catch/
http://chineseruleof8.com/code/index.php/2018/06/25/throw-error/
https://stackoverflow.com/questions/3217294/javascript-try-catch-performance-vs-error-checking-code
https://stackoverflow.com/questions/1722964/when-to-use-try-catch-blocks

Programs must be written for people to read, and only incidentally for machines to execute

Always aim for readable code

The key thing to remember is: Avoid try-catch in performance-critical functions, and loops

Anywhere else they won’t do much harm. Use them wisely, use them sparingly. As a side note if you want to support older browsers they may not have try-catch.

The try-catch block is said to be expensive. However if critical performance is not an issue, using it is not necessarily a concern.

The penalty with try-catch blocks everywhere is:

Readability: plumbing your code with plenty of try-catch is ugly and distracting
inappropriate: it’s a bad idea to insert such block if your code is not subject to exception-crash. Insert it only if you expect a failure in your code.
the try-catch block is synchronous and is not effective when it comes to async programming. During an async request you handle both the error and success events in dedicated callbacks. No need for try-catch.

The basic rule of thumb for catching exceptions is to catch exceptions if and only if you have a meaningful way of handling them.

Don’t catch an exception if you’re only going to log the exception and throw it up the stack. It serves no meaning and clutters code.

Do catch an exception when you are expecting a failure in a specific part of your code, and if you have a fallback for it.

Of course you always have the case of checked exceptions which require you to use try/catch blocks, in which case you have no other choice. Even with a checked exception, make sure you log properly and handle as cleanly as possible.

Assuming undefinedfunction() is undefined, when the browser runs it, no errors will be shown. The syntax for try/catch/finally is a try clause followed by either a catch or finally clause (at least one or both of them). The catch clause if defined traps any errors that has occurred from try, and is indirectly passed the error object that contains additional info about the error. Lets see a slightly more complex example now:

try{

undefinedfunction()

alert('I guess you do exist')

}

catch(e){

alert('An error has occurred: '+e.message)

}

Click on the above button, and notice how only “An Error has occurred” alert pops up, but not “I guess you do exist”. This tells us that when try encounters an error, it immediately skips any remaining code inside it and goes straight to catch. The default error message is obviously suppressed, though you can still retrieve this information by accessing the Error object that gets indirectly passed into catch.

throw error

June 25, 2018javascriptadmin

The throw statement throws a user-defined exception. Execution of the current function will stop (the statements after throw won’t be executed), and control will be passed to the first catch block in the call stack. If no catch block exists among caller functions, the program will terminate.

let width = 35.45;

//let width = "Hadoooken!";

try {

if (isNaN(width)) {

throw `Errrooooorrrr...! you entered --> ${width}`;

} else {

console.log(`you've entered ${width}`);

}

catch(e) {

console.log(e);

}

console.log("...moving on to the next line of code...");

You can keep throwing the same exception. Once its caught, in your catch block, just do another try/catch so you can throw again.

let n = 344;

try {

throw n; // throws an exception with a numeric value

} catch (e) {

if (e <= 50) {

console.log("statements to handle exceptions 1-50");

} else {

try {

console.log("cannot handle this exception, so rethrow");

throw e;

} catch (e1) {

console.log(`2nd catch! ${e1}`);

}

Or you can wrap it inside of a try catch. So that whatever is thrown, the outside will catch it.

function a() {

try {

throw n; // throws an exception with a numeric value

} catch (e) {

if (e <= 50) {

console.log("a() - statements to handle exceptions 1-50");

} else {

throw e;

}

a() // error

You’ll get it an error if you run function a, there is nothing to catch it. What we can do is to put function a inside of another try catch like so:

let n = 344;

function a() {

try {

throw n; // throws an exception with a numeric value

} catch (e) {

if (e <= 50) {

console.log("a() - statements to handle exceptions 1-50");

} else {

throw e;

}

try {

a(); // when the second throw happens, we'll be able to catch it out here

}

catch(e) {

console.log(`caught ${e} globally`)

}

output:

caught 344 globally

Custom Errors

we declare a custom error function like so:

function UserException(message) {

this.message = message;

this.name = 'UserException';

}

We will create an instantiation of this function and throw it in another function called getMonthName.
We basically give it a numeric to indicate a month. It uses that number to get the string of the month. Then we
simply return the string.

However, numerically, a month is only 1-12. If we give it say, 15, then in the array, it would be undefined.
In that case, we throw instantiation of our function like so:

1	throw new UserException('InvalidMonthNo');

As long as the throw is within a try/catch, then it will be valid.

Here is the function that try and catches the block of code. As you can see, once the user puts a erroneous parameter, we can catch it if the array returns undefined.

function getMonthName(mo) {

mo = mo - 1; // Adjust month number for array index (1 = Jan, 12 = Dec)

var months = ['Jan', 'Feb', 'Mar', 'Apr', 'May', 'Jun', 'Jul',

'Aug', 'Sep', 'Oct', 'Nov', 'Dec'];

if (months[mo] !== undefined) {

return months[mo];

} else {

throw new UserException('InvalidMonthNo');

}

The reason why our throw will be caught is because our function is wrapped by a try catch.

try {

// statements to try

var myMonth = 15; // 15 is out of bound to raise the exception

var monthName = getMonthName(myMonth);

} catch (e) {

monthName = 'unknown';

console.log(e.message, e.name); // pass exception object to err handler

}

try catch

June 22, 2018javascriptadmin

ref – https://stackoverflow.com/questions/7148019/when-should-you-use-try-catch-in-javascript

When a single, unconditional catch clause is used, the catch block is entered when any exception is thrown. For example, when the exception occurs in the following code, control transfers to the catch clause.

try {

throw 'myException'; // generates an exception

}

catch (e) {

// statements to handle any exceptions

logMyErrors(e); // pass exception object to error handler

}

The catch block specifies an identifier (e in the example above) that holds the value specified by the throw statement. The catch block is unique in that JavaScript creates this identifier when the catch block is entered and it adds it to the current scope; the identifier lasts only for the duration of the catch block; after the catch block finishes executing, the identifier is no longer available.

finally

openMyFile();

try {

// tie up a resource

writeMyFile(theData);

}

finally {

closeMyFile(); // always close the resource

}

Note that the finally clause executes regardless of whether an exception is thrown. Also, if an exception is thrown, the statements in the finally clause execute even if no catch clause handles the exception.

You can use the finally clause to make your script fail gracefully when an exception occurs; for example, to do general cleanup, you may need to release a resource that your script has tied up.

General situations

try…catch blocks are generally encourages to be used less, and this doesn’t depend on the language you use.

The main reason for this is the cost of catch blocks. Also another reason is that, when you wrap many statements with a single try…catch block, in catch block you can’t be sure what was exactly the main problem.

It’s better to use techniques like validation or if…else blocks to reduce the probability of an exception (error) to happen. For example, when you want to work with a number which is taken from user, instead of using try…catch, you can use:

if (isNaN(numberVariable))

{

alert('you should enter a valid number');

}

deeply nested objects where a null can pop up at any level

1	var something = one.two.three.four.five;

to perform this “get” with 100% safety one would have to write a bit of verbose code:

1 2	if(one && one.two && one.two.three && one.two.three.four) something = one.two.three.four.five;

Now imagine the variable names are realistic and longer and you quickly get a very ugly code if statement.

I tend to use try/catch/finally to simplify this when I don’t care about any “else” scenarios and just want the object or not:

var something;

try { something = one.two.three.four.five; }

catch { something = "default"; }

finally { doSomething(something); }

Hash Table (Linear Probing)

June 20, 2018Computer Science, javascriptadmin

ref – https://github.com/redmacdev1988/LinearProbeHashTable
https://stackoverflow.com/questions/9124331/meaning-of-open-hashing-and-closed-hashing

Linear Probing is an Open Addressing scheme for hash tables.

The “open” in “open addressing” tells us the index (aka. address) at which an object will be stored in the hash table is not completely determined by its hash code. Instead, the index may vary depending on what’s already in the hash table.

The “closed” in “closed hashing” refers to the fact that we never leave the hash table; every object is stored directly at an index in the hash table’s internal array. Note that this is only possible by using some sort of open addressing strategy. This explains why “closed hashing” and “open addressing” are synonyms.

Best case – O(1).
For insertion, it hashes to an empty element. We insert. done.
For search, it hashes to its initial location. We do a check. Keys match. done.
Deletion – Searches for the element with the key. We find it. We remove it. The next element is empty so we’re done.

Worst case – all are O(n), because the worst possible case scenario is that we have to iterate the whole array after the initial collision.

Insertion

Insertion for linear probe deals with 2 steps:

1) hash to a location. If the location is empty, done.
2) If the location is occupied, we probe for an empty space.

Probe involves going step by step down the cells and trying to find an empty cell. Once found, we place the object there.
Note that we do not circle around back to the beginning of the array. If no empty cells are to be found, we return -1. Other alternatives can be to grow the array and try inserting again.

function probeAndInsert(kvPair, startingIndex, lastIndex) {

if (startingIndex >= lastIndex) {return -1;}

for (let i = startingIndex; i < lastIndex; i++) {

if (!_self.array[i]) { _self.array[i] = kvPair; return i; }

}

console.log(`probe - uh oh, cannot find location for ${kvPair}`);

return -1;

}

function insert(kvPair) {

if (kvPair.constructor.name === "KVPair") {

let index = hash(kvPair.key);

kvPair.hash = index;

if (!_self.array[index]) {_self.array[index] = kvPair;}

else {

let indexInserted = probeAndInsert(kvPair, index, _self.array.length);

if (indexInserted !== -1) console.log(`insert - collision happened at ${index}... probed and inserted (${kvPair.key}) at ${indexInserted}`);

else {console.log(`insert - !!! can't find a valid spot for ${kvPair.key}:${kvPair.value}`);return -1;}

}

} // if KVPair

}

Retrieving the object

Searching for a cell with a certain key involves starting at the hashed index:

1) If the keys match, then return the cell. If no match, keep going forward (probe) and looking for a match on our key.
2) If an empty cell is found, the key is not in the table. If the key did exist, it would be placed in the empty cell first, and not have gone any further in the later cells. This is because during insertion, when a value is hashed and there is a collision, it would naturally probe until it finds an empty spot to put its object. Thus, when searching, hitting an empty spot means its the end of the line for a particular item that was hashed to a previous location.

// takes in a key, returns KVPair object

this.retrieveIndex = function(key) {

let index = hash(key);

console.log(`retrieve - initially hashed ${key} to index ${index}`)

// beginning with the cell at index h(x)

for (let i = index; i < this.array.length; i++) {

let item = this.array[i];

// if an empty cell is found, the key cannot be in the table,

// because it would have been placed in that cell in preference

// to any later cell that has not yet been searched.

// In this case, the search returns as its result that the key

// is not present in the dictionary

if (!item) {

console.log(`index ${i} is empty. ${key} not found`);

return null;

}

if (item && (item.key === key)) {

// If a cell containing the key is found,

// the search returns the value from that cell

return i;

}

Deleting an Object

Deleting an item is the same as searching. When we have successfully found the cell it delete, we:

1) remove the cell so the array element references null
2) Here’s the important part. Once the element was is removed in 1), we need to find a replacement down the line. The reason why we need to find a replacement is shown below.

Say we want to insert key “job”. It gets hashed to index 6, then we move it to the next empty space, which is index 9.

The next operation is that we want to remove key “last name”. So last name gets hashed to index 6. We go down the array until we find “last name” at index 8. We remove it.

Now, say we want to search for key “job”. It would get hashed to index 6. Then it would keep going and then it would hit index 8 on an empty cell. It would stop and say key “job” does not exist. However, clearly, job exists down the line at index 9.

Solution on what to do for the empty space after deletion

When deleting, we remove the cell, then:

1) then go down the list to find a replacement for this empty cell
2) The replacement must have a key equal or smaller than the recently deleted item.

This is because all items are inserted on or after its initial hashed index. Thus, we can replace the empty cell with hashed index that is smaller because the search is coming from the left.

But why? take a look at an example:

Sa we want to delete key “last”, which was initially hashed to index 6, and probed to index 7. Now, from the previous example, we know we can’t just let it go like this.

We must go down the line and find a replacement. The notion is that we must find a replacement that has key <= our key. But what if we dont' do this? What will happen? Say we simply get the next available replacement, which in our case, is key "name" (initially indexed to 8). So as you can see, say we bring key "name" over to index 7. Then, we make a search for key "name". Its initial hash index would be 8. And it wouldn't find anything there. If data does get placed there, it wouldn't be key "name" that we're looking for. Let's see what would happen if we iterated the array for a cell that has a key <= to our key. Picking an element with hash <= removed element's hash

So after removing key “last”, we can’t just get any element to replace it. We must find an element with a hash <= our hash. Since we’ve removed “last” with key of 6, we then iterate the array to find that element.

We go down the list, name has hash 8, nope. job has hash 8. nope. age has has 6. Perfect! so we move the element with key “age” and hash 6 to index 7. Don’t forget that we must do this continuously until we hit an empty slot or the end of the array.

Now, when you try to search for “age”, it will hash you to index 6, which you collide with key first. Then you probe. At index 7, we have found the element with key “age”. done!

this.delete = function(toDeleteKey) {

let toDeleteIndex = this.retrieveIndex(toDeleteKey);

if (!this.array[toDeleteIndex]) {

console.log(`Sorry! this element does not exist`);

return false;

}

let toDeleteHash = this.array[toDeleteIndex].hash;

if (this.array[toDeleteIndex]) {

// when a cell i is emptied

this.array[toDeleteIndex] = null;

// it is necessary to search forward through the following cells

for (let i = toDeleteIndex+1; i < this.array.length; i++ ) {

// of the table until finding either another empty cell

// When an empty cell is found, then emptying cell i is

// safe and the deletion process terminate

if (!this.array[i]) {

console.log(`cell ${i} is empty. We done`);

return true;

}

else {

// the cell is valid, so check its hash

// if the hash is <= to toDelete hash, we can switch.

if (this.array[i].hash <= toDeleteHash) {

this.array[toDeleteIndex] = this.array[i];

toDeleteIndex = i;

toDeleteHash = this.array[i].hash;

this.array[i] = null;

}

} // for

console.log("didn't find anything");

}

else

console.log(`Sorry key does not exist`);

}

Problems of Linear probing – Cluster

Due to linear probing, clusters may form. Its when we keep hashing to an index and then linearly adding items down the line. A cluster will start forming at the hash index and future hashes will be unwieldy because every future hash will have to step through that cluster.

To solve this problem, we use Quadratic Probing.

((hash(key) + i)^2) % TABLE_SIZE

How will it prevent from probing?

With linear probing, we increase step by step. But if we step quadratically, our steps will widen, and this spread the insertions out.

However, the problem here is that Quadratic Probing will circle back and it keeps making the same jumps. This ends up with infinite loop.

Double Hashing

Given,
prime is a prime # smaller than TABLE_SIZE.
hashOne(key) = key % TABLE_SIZE,
hashTwo(key) = prime – (key%prime),
i as current index

DoubleHashing(key) = (hashOne(key) + i * hash2(key)) % TABLE_SIZE

Before, we used i for
Linear: i
Quadratic: i^2
now, we use Double: i * hash2

Iterating Array elements

June 12, 2018javascriptadmin

ref – https://stackoverflow.com/questions/5349425/whats-the-fastest-way-to-loop-through-an-array-in-javascript

given array

1	let ArrPerson = ["ricky", "david", "james"];

filter

console.log("---filter---");

ArrPerson.filter(function(item, index) {

console.log(`${item}, ${index}`);

});

forEach

console.log("---forEach---");

ArrPerson.forEach(function(key, value){

console.log(`${key}, ${value}`)

});

map

warning: map is for generating a new array, we manipulate each element, and the function generates a new array with those new changes.
Its purpose is not really for iterating an array. For completeness, it is included.

ArrPerson.map( function(item, index) {

console.log(`item - ${item}, index - ${index}`);

});

for loop

for (let i = 0; i < ArrPerson.length; i++) {

console.log(`${ArrPerson[i]}, ${i}`);

}

while loop

var len = ArrPerson.length;

let j = 0;

while ((len--) > 0) {

console.log(`${ArrPerson[j++]}`)

}