Gary Bernhardt

@garybernhardt

Don't listen to people who tell you that the core topics in a CS degree are irrelevant. I mean... I haven't exactly needed the things I learned (and forgot) in my required "Chemistry of Materials" course. And my "Software Engineering" course was silly. But the core is real.

17:38 PM - 21 May 2020

5 37

Jan

@janwilmans

@Cor3ntin Just try java, javascript or C# for a while, I did, I really prefer the problems I have in C++. Namely problems I can just solve instead of problems you can only work around or are just going to have to life with.

20:39 PM - 22 Apr 2020

0 20

One Devloper Army

@onedevloperarmy

The problem with object-oriented languages is theyve got all this implicit environment that they carry around with them. You wanted a banana but what you got was a gorilla holding the banana and the entire jungle.

03:18 AM - 12 May 2020

50 262

Prerequisite ()

If you're reading this article right now, please considered to read our Part 01: Big-O Notation, Part 02: JavaScript Unique Part, Part 03: JavaScript Numbers to Part 10: Searching and Sorting Algorithm

Table of Contents
Part 01: Big-O Notation() Learn Data Structure & Algorithm in JavaScript | Part 01 Edison Pebojot() Jun 29 8 min read #javascript #computerscience #beginners #algorithms
Part 02: JavaScript Unique Parts() Learn Data Structure & Algorithm in JavaScript | Part 02 Edison Pebojot() Jul 1 8 min read #javascript #computerscience #beginners #algorithms
Part 03: JavaScript Numbers() Learn Data Structure and Algorithm in JavaScript | Part 03 Edison Pebojot() Jul 4 12 min read #javascript #computerscience #algorithms #beginners
Part 04: JavaScript Strings() Learn Data Structure and Algorithm in JavaScript | Part 04 Edison Pebojot() Jul 5 13 min read #javascript #computerscience #beginners #algorithms
Part 05: JavaScript Array() Learn Data Structure and Algorithm in JavaScript | Part 05 Edison Pebojot() Jul 7 12 min read #javascript #computerscience #beginners #algorithms
Part 06: JavaScript Object() Learn Data Structure and Algorithm in JavaScript | Part 06 Edison Pebojot() Jul 9 5 min read #javascript #computerscience #beginners #algorithms
Part 07: JavaScript Memory Management() Learn Data Structure and Algorithm in JavaScript | Part 07 Edison Pebojot() Jul 11 7 min read #javascript #computerscience #beginners #algorithms
Part 08: Recursion() Learn Data Structure and Algorithm in JavaScript | Part 08 Edison Pebojot() Jul 17 14 min read #javascript #computerscience #datastructures #algorithms
Part 09: Sets() Learn Data Structure and Algorithm in JavaScript | Part 09 Edison Pebojot() Jul 23 9 min read #javascript #computerscience #beginners #algorithms
Part 10: Searching and Sorting() Learn Data Structure and Algorithm in JavaScript | Part 10 Edison Pebojot() Jul 25 19 min read #javascript #computerscience #beginners #algorithms

Part 11: Hash Tables ( )

A hash table is a fixed-sized data structure in which the size is defined at the start. This part 11 explains how hash tables work, and the method of generating a unique key. By the end of this part 11, you will understand various hashing techniques and know how to implement a hash table. ()

Introducing Hash Tables ()

Hash tables are excellent for quick storage and retrieval of data based on key-value pairs. In JavaScript, JavaScript objects work this way by defining a key and value.

Figure 11-1. Simple hash table overview

Figure 11-1 shows each key and its associated item. A hash table contains two functions: put() and get(). put() is used for storing data, while get() is used for retrieving data from the hash table. Both of these functions have a time complexity of $O(1)$.

localStorage is an example of a data structure based on a hash table. It is a native JavaScript object. It lets developers persist(preserve) data. Let's see an example of localstorage:

Example:

localStorage.setItem("testKey", "testValue");//-----------------------------------console.log(localStorage.getItem("testKey")); // prints "testValue"

Note (): click remix to edit. And view app to view the result. To see the localstorage example please see the script.js

Hashing Technique ()

The most important part of a hash table is the hash function. The hash function converts a key into an index that stores the data. The three(3) primary requirements for a good hash function are as follows(see below):

• Deterministic: Equal keys produce equal values.
• Efficiency: It should be $O(1)$ in time.
• Uniform distribution: It makes the most use of the array. ()

The first technique for hashing is to use prime numbers. With prime numbers, a uniform distribution of the index can be guaranteed.

Prime Number Hashing (1)

Remember: Prime numbers in hashing are important. Modulus division using prime numbers yields an array index in a distributed(uniform) manner. Let's see an example below:

We have Prime Numbers: $5,7,4,13,15,17$ and a Modulus Number: $11$

Collisions can be seen with $15$ and $4$ yielding the same key because they're not even a prime numbers. This is the list of prime numbers just below:

Handling this collision is discussed later below. As of now, I just want to remind you that such collision exist in hash table. What is important here is that modulus by prime numbers guarantees the best distribution for a fixed size, okay? (). A small modulus number such as $4$ by a non-prime number which is $6$ and $10$ guarantees only a range from $0$ to $3$ and leads to a large number of collisions (). Let's see an example below:

We have Non-Prime Numbers: $6,10$ and a Modulus Number: $4$

Remember: This is the first(or basic) hashing technique. Let's see an example hash table below:

Figure 11-2. Hash table of size 11, with all empty elements

This hash table of size 11, with all empty elements is the same as the example JavaScript code below(now look ()):

Example:

[    { keys: "", values: "" }, // 0    { keys: "", values: "" }, // 1    { keys: "", values: "" }, // 2    { keys: "", values: "" }, // 3    { keys: "", values: "" }, // 4    { keys: "", values: "" }, // 5    { keys: "", values: "" }, // 6    { keys: "", values: "" }, // 7    { keys: "", values: "" }, // 8    { keys: "", values: "" }, // 9    { keys: "", values: "" }  // 10]

In this example below(look first), we will only use 4 index for the sake of simplifying my explanation (), now in the example below, lets hash the following key-value pairs:

Example:

[    { keys: 7, values: "hi" },      // 0    { keys: 23, values: "hello" },  // 1    { keys: 43, values: "sunny" },  // 2    { keys: 31, values: "weather" },// 3]// We have index 0, 1, 2, 3. With a total of 4

We have Prime Numbers: $7,23,43,31$ and a Modulus Number: $11$

The resulting hash table is shown in Figure 11-3 below:

Figure 11-3. Hash table after inserting the value pairs

Now lets hash non-prime number 18 with modulus 11:

Results: $18\%11=7$

This is a problem because 7 already exists in the index and causes an index collision. With a perfect hashing function, there are no collisions. Therefore, there are strategies for handling collisions needed for hash tables which is: Linear Probing, Quadratic Probing, and Double Hashing. Let's see them below. Let's go! ()

Probing ()

To work around collisions, probing finds the next available index in the array. The linear probing technique resolves conflicts by finding the next available index via incremental trials ( $n+1$), while quadratic probing uses quadratic functions to generate incremental trials ( n2n^{2}n2). Don't confuse them for now, we will see more example below! ()

Linear Probing ()

Linear probing works by finding the next available index by incrementing one index ( $n+1$). For example, in the case of 18 hashing to the same key of 7, 18 would be hashed into key 8 because thats the next empty spot. See the example below:

Figure 11-4. Hash table 1 after using linear probing

When the get( key ) function is used, it has to start at the original hash and then iterate. We will discuss later what get( key ) function is just below.

Note (): The main disadvantage of linear probing is it easily creates clusters(A grouping of a similar number), which are bad because they create more data to iterate through.

Quadratic Probing ()

Quadratic probing is a good technique for addressing the cluster issue (). Quadratic probing uses perfect squares instead of incrementing by 1, and this helps to evenly distribute the indices, as shown in Figure 11-5 below:

Figure 11-5. Linear probing (on top) and quadratic probing (on bottom)

Double Hashing ()

Another great way to distribute the keys is by having a second hashing function that hashes the result from the original. These are the three primary requirements for a good second hash function:

• Different: It needs to be different
• Efficiency: It should still be $O(1)$ in time.
• Nonzero: It should never evaluate to zero.

A second hashing function is as follows. See below:

Here, $x$ is the result from hashing the first, and $R$ is less than the size of the hash table. Each hash collision is resolved by the following, where $i$ is the iteration trial number:

Hash Table Implementation ()

In this section, you will apply three techniques to the same example. The following are the example key-value pairs that will be used:

[    { keys: 7, values: "hi" },       // 0    { keys: 23, values: "hello" },   // 1    { keys: 37, values: "sunny" },   // 2    { keys: 47, values: "weather" }, // 3    { keys: 59, values: "wow" },     // 4    { keys: 73, values: "forty" },   // 5    { keys: 89, values: "happy" },   // 6    { keys: 97, values: "sad" }      // 7]

Using Linear Probing ()

Lets start the example with simple linear probing:

Example:

function HashTable(size) {    this.size = size;    this.keys = this.initArray(size);    this.values = this.initArray(size);    this.limit = 0;}HashTable.prototype.initArray = function (size) {    var array = [];    for (var i = 0; i < size; i++) {        array.push(null);    }    return array;}HashTable.prototype.put = function (key, value) {    if (this.limit >= this.size) throw 'hash table is full'    var hashedIndex = this.hash(key);    // Linear probing    while (this.keys[hashedIndex] != null) {        hashedIndex++;        hashedIndex = hashedIndex % this.size;    }    this.keys[hashedIndex] = key;    this.values[hashedIndex] = value;    this.limit++;}HashTable.prototype.get = function (key) {    var hashedIndex = this.hash(key);    while (this.keys[hashedIndex] != key) {        hashedIndex++;        hashedIndex = hashedIndex % this.size;    }    return this.values[hashedIndex];}HashTable.prototype.log = function () {    return {        keys: this.keys,        values: this.values    };}HashTable.prototype.hash = function (key) {    // Check if int    if (!Number.isInteger(key)) throw 'must be int';    return key % this.size;}var exampletable = new HashTable(13);exampletable.put(7, "hi");exampletable.put(23, "hello");exampletable.put(37, "sunny");exampletable.put(47, "weather");exampletable.put(59, "wow");exampletable.put(73, "fourty");exampletable.put(89, "happy");exampletable.put(97, "sad");exampletable.log();

Execution:

Here is the result on my computer. Take a look carefully ():

Note (): I advice, get a piece of paper or a white board, and draw them, I also advice to draw the code on the paper instead on your computer. You are more likely to remember them. Okay?()

Using Quadratic Probing ()

Now, we will just change the put() and get() methods from the linear probing to use quadratic probing. Let's see the example below:

Example:

HashTable.prototype.put = function(key, value) {    if (this.limit >= this.size) throw 'hash table is full'    var hashedIndex = this.hash(key),        squareIndex = 1;    // quadratic probing    while (this.keys[hashedIndex % this.size] != null) {        hashedIndex += Math.pow(squareIndex, 2);        squareIndex++;    }    this.keys[hashedIndex % this.size] = key;    this.values[hashedIndex % this.size] = value;    this.limit++;}HashTable.prototype.get = function(key) {    var hashedIndex = this.hash(key),        squareIndex = 1;    while (this.keys[hashedIndex % this.size] != key) {        hashedIndex += Math.pow(squareIndex, 2);        hashedIndex = hashedIndex % this.size;        squareIndex++;    }    return this.values[hashedIndex % this.size];}

Execution:

Here is the result on my computer. Take a look carefully ():

Note (): I advice, get a piece of paper or a white board, and draw them, I also advice to draw the code on the paper instead on your computer. You are more likely to remember them. Okay?()

If you look at the output. This result is more uniform than the result from linear probing. ()

Using Double-Hashing in Linear Probing ()

Finally, lets combine double-hashing and linear probing. Recall the common second hash function, $hash2(x)=R(x\%R)$, where $x$ is the result from hashing the first time, and $R$ is less than the size of the hash table. Let's look at the example below:

Example:

HashTable.prototype.put = function(key, value) {    if (this.limit >= this.size) throw 'hash table is full'    var hashedIndex = this.hash(key);    while (this.keys[hashedIndex] != null) {        hashedIndex++;        hashedIndex = hashedIndex % this.size;    }    this.keys[hashedIndex] = key;    this.values[hashedIndex] = value;    this.limit++;}HashTable.prototype.get = function(key) {    var hashedIndex = this.hash(key);    while (this.keys[hashedIndex] != key) {        hashedIndex++;        hashedIndex = hashedIndex % this.size;    }    return this.values[hashedIndex];}HashTable.prototype.hash = function(key) {    if (!Number.isInteger(key)) throw 'must be int'; // check if int    return this.secondHash(key);}HashTable.prototype.secondHash = function(hashedKey) {    var R = this.size - 2;    return R - hashedKey % R;}

Execution:

Here is the result on my computer. Take a look carefully ():

Note (): I advice, get a piece of paper or a white board, and draw them, I also advice to draw the code on the paper instead on your computer. You are more likely to remember them. Okay?()

Again, double-hashing results in a more uniform distributed array than the result from linear probing. Both quadratic probing and double-hashing are great techniques to reduce the number of collisions in a hash table. Remember: There are collision algorithms far more advanced than these techniques, but they are beyond the scope of this article. (Learn more)

Summary ()

A hash table is a fixed-sized data structure in which the size is defined. Hash tables are implemented using a hash function to generate an index for the array. A good hash function is deterministic, efficient, and uniformly distributive. Hash collisions should be minimized with a good uniformly distributive hash function, but having some collisions is unavoidable (). Hash collision-handling techniques include: linear probing, quadratic probing, and double-hashing. The next part explores Stacks and Queues, which are dynamically sized data structures. See you soon! ()

Up Next Part 12: Stacks and Queues () (August 9-10, 2020)