loading...
Cover image for Learn Data Structure and Algorithm in JavaScript | Part 11

Learn Data Structure and Algorithm in JavaScript | Part 11

edisonnpebojot profile image Edison Pebojot(๐Ÿ‘จโ€๐Ÿ’ป) Updated on ใƒป18 min read


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

Part Table of Contents Description
01 Big-O Notation By the end of this chapter, you will understand how to analyze an implementation of an algorithm with respect to both time (execution time) and space (memory consumed).
02 JavaScript Unique Parts Big-O is important for analyzing and comparing the efficiencies of algorithms. The analysis of Big-O starts by looking at the code, and, applying the rules, applying the rules is because to simplify the Big-O notation linear or quadratic rule is not enough.
03 JavaScript Numbers This part 3 will focus on JavaScript number operations, number representation, Number objects, common number algorithms, and random number generation.
04 JavaScript Strings This part 4 will focus on strings, JavaScript String object, and the String objectโ€™s built-in functions. You will learn how to access, compare, decompose, and search strings for commonly used real-life purposes. In addition, the chapter will explore string encoding, decoding, encryption, and decryption.
05 JavaScript Arrays As a JavaScript developer, you will use the array often; it is the most commonly used data structure. Arrays in JavaScript come with a lot of built-in methods. By the end of this part, you will understand arrays and choose the right method
06 JavaScript Object This part will focus on what JavaScript objects are, how they are declared, and how their properties can be changed. In addition, this part will cover how JavaScript classes are implemented using prototypal inheritance. Also this part will be short.
07 JavaScript Memory Management A variable takes up some memory. In C, the programmer allocate and deallocate memory manually. In contrast, modern JavaScript engines have garbage collectors that delete unused variables. However, there are pitfalls(unexpected) that developers can fall into(โ—) This part will show these unexpected and present techniques to help the garbage collector minimize the memory problems.
08 Recursion This part 8 introduces the concept of recursion and recursive algorithms(Remember they are different, we will discuss them later(๐Ÿ˜‰)). We will also discuss the definition of recursion and fundamental rules for recursive algorithms.
09 Sets This part focuses on the concepts of sets from both a mathematical definition and on the implementation. Also, Common set operations, as well as their implementations, are covered in great detail (๐Ÿ’ก).
10 Searching and Sorting This part 10 focuses on searching and sorting for arrays. By the end of this part 10, you will understand how to use sorting and searching algorithms for arrays. Also, this article is a bit complicated for beginners, so as much as possible the visual aids is your friend (๐Ÿ‘€). (๐Ÿ˜ƒ)
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. (๐Ÿ˜ƒ)
12 Stacks and Queues This part 12 covers stacks and queues(pronounce as kyooz (๐Ÿ”ˆ)) not (kwewe) okay? hehehe (๐Ÿ˜…); both are data structures used in the implementation of complex data structures. You'll learn what the stacks and queues are, how they're used, when they're used, and how to implement them (๐Ÿ˜ƒ) Let's go! (๐Ÿ”ฅ๐Ÿ”ฅ๐Ÿ”ฅ)
13 Linked Lists A linked list is a data structure in which each node (or element) points to another node. Unlike arrays, which have a fixed size, a linked list is a dynamic data structure. By the end of this part 13, you will understand how to implement and work with linked lists. And oh! (๐Ÿ˜ฎ) There are two types of linked lists: singly (โžก๏ธ) and doubly (โ†”๏ธ). Letโ€™s examine the singly linked list first.(๐Ÿ˜ƒ) Let's go! (๐Ÿ”ฅ๐Ÿ”ฅ๐Ÿ”ฅ)
14 Caching Caching is the process of storing data into temporary memory so that it can be easily retrieved for later use if it is required again. As an example, a database keeps data cached to avoid re-reading the hard drive, and a web browser caches web images to avoid re-downloading. In this part 14, two caching techniques will discussed: LFU and LRU caching.
15 Trees A general tree data structure is composed of nodes with children nodes. The top node is called the root node. This part 15 will explore different types of trees such as binary trees, binary search trees, and self-balancing binary search trees. First, this part 15 will cover what trees are and how they are structured. Then, it will cover methods of traversing(crossing or taking a zigzag path) the tree data structure in detail. Finally, you will learn about binary search trees and self-balancing binary search trees to understand how to store searchable data. (๐Ÿ˜ƒ)
16 Heaps A heap is an important data structure that returns the highest or lowest element in O(1) time. This part 16 will focus on explaining how heaps are implemented as well as how to work with them. One example is heap sort, which is a sorting algorithm based on heaps.
17 Graphs In this Part 17, you will learn graph basics, including fundamental terminology and graph types. The Part 17 will also cover working with these different graph types and methods of representing graphs in data structures. Finally, algorithms for traversing, searching, and sorting graphs are explored to solve problems such as finding the shortest path between two graph nodes. (๐Ÿ‘)
18 Advance Strings Part 18 will cover more complex string algorithms than covered in the previous section. Now that you have heard of certain other data models or structures, they should be easier to comprehend. Specifically, Part 18 will focus on string searching algorithms. (๐Ÿ˜‰)
19 Dynamic Programming Dynamic programming involves breaking down problems into their subproblems. Solving the subproblems and saving those results into memory to access them whenever a repeated problem needs to be solved, the algorithmic complexity decreases significantly (โฌ‡๏ธ). To explain dynamic programming, letโ€™s re examine the Fibonacci sequence that was discussed in Part 8. Then Part 19 will cover the rules of dynamic programming and walk you through some examples to make the concepts more concrete. (๐Ÿ˜‰)
20 Bit Manipulation Bit manipulation is an advanced topic that JavaScript developers typically do not need to know. However, you should learn a bit about bit manipulation if you want to implement high-performance server-side code. Understanding bit manipulation requires some knowledge of digital logic. Any introductory course in discrete math or circuits would be helpful to understand these concepts.

Part 11: Hash Tables (๐Ÿ˜ฑ ๐Ÿ”ฅ ๐Ÿ“)

Alt Text

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 (๐Ÿ“๐Ÿ“)

Alt text

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.


Alt Text

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)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"
Enter fullscreen mode Exit fullscreen mode

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

Hashing Technique (โžก๏ธ๐Ÿ”ข)

Alt text

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)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,ย 175,\space 7,\space 4,\space 13,\space 15,\space 17 and a Modulus Number: 1111

5ย %ย 11=55 \space \% \space 11 = 5

7ย %ย 11=77 \space \% \space 11 = 7

4ย %ย 11=44 \space \% \space 11 = 4

13ย %ย 11=213 \space \% \space 11 = 2

15ย %ย 11=415 \space \% \space 11 = 4

17ย %ย 11=617 \space \% \space 11 = 6

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

Alt Text

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 44 by a non-prime number which is 66 and 1010 guarantees only a range from 00 to 33 and leads to a large number of collisions (๐Ÿ’ฅ). Let's see an example below:

We have Non-Prime Numbers: 6,ย 106,\space 10 and a Modulus Number: 44

6ย %ย 4=26 \space \% \space 4 = 2

10ย %ย 4=210 \space \% \space 4 = 2

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

Alt Text

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
]
Enter fullscreen mode Exit fullscreen mode

In this example below(look first), we will only use 4 index for the sake of simplifying my explanation (๐Ÿ˜…), now in the example below, letโ€™s 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
Enter fullscreen mode Exit fullscreen mode

We have Prime Numbers: 7,ย 23,ย 43,ย 317,\space 23,\space 43,\space 31 and a Modulus Number: 1111

7ย %ย 11=77 \space \% \space 11 = 7
23ย %ย 11=123 \space \% \space 11 = 1
43ย %ย 11=1043 \space \% \space 11 = 10
31ย %ย 11=931 \space \% \space 11 = 9

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

Alt Text

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

Now letโ€™s hash non-prime number 18 with modulus 11:

Results: 18ย %ย 11=718 \space \% \space 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+1n + 1 ), while quadratic probing uses quadratic functions to generate incremental trials ( n2n^{2} ). 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+1n + 1 ). For example, in the case of 18 hashing to the same key of 7, 18 would be hashed into key 8 because thatโ€™s the next empty spot. See the example below:

Alt Text

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:

h+(1)2,ย h+(2)2,ย h+(3)2,ย h+(4)2ย =ย h+1,ย h+4,ย h+9,ย h+16 h + (1)^2,\space h + (2)^2,\space h + (3)^2,\space h + (4)^2\space = \space h + 1,\space h + 4,\space h + 9,\space h + 16

Alt Text

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)O(1) in time.
  • Nonzero: It should never evaluate to zero.

A second hashing function is as follows. See below:

hash2(x)ย =ย Rย โˆ’ย (xย %ย R)hash2(x) \space = \space R \space โˆ’ \space (x \space \% \space R)

Here, xx is the result from hashing the first, and RR is less than the size of the hash table. Each hash collision is resolved by the following, where ii is the iteration trial number:

iย โˆ—ย hash2(x)i \space * \space hash2(x)

Hash Table Implementation (๐Ÿ”ข๐Ÿ”จ)

Alt Text

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
]
Enter fullscreen mode Exit fullscreen mode

Using Linear Probing (๐Ÿ”ขโžก๏ธโžก๏ธ)

Letโ€™s 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();
Enter fullscreen mode Exit fullscreen mode

Execution:

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.hash = function (key) { // Check if int if (!Number.isInteger(key)) throw 'must be int'; return key % this.size; } HashTable.prototype.log = function () { return { keys: this.keys, values: this.values }; } 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(); // You can also use exampletable.get(key) if you want to retrieve specific value but now, we only use exampletable.log()

Here is the result on my computer. Take a look carefully (๐Ÿ‘€):
Alt Text

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];
}
Enter fullscreen mode Exit fullscreen mode

Execution:

function HashTable(size) { this.size = size; this.keys = this.initArray(size); this.values = this.initArray(size); this.limit = 0; } 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]; } HashTable.prototype.hash = function (key) { // Check if int if (!Number.isInteger(key)) throw 'must be int'; return key % this.size; } HashTable.prototype.initArray = function (size) { var array = []; for (var i = 0; i < size; i++) { array.push(null); } return array; } HashTable.prototype.log = function () { return { keys: this.keys, values: this.values }; } 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(); // You can also use exampletable.get(key) if you want to retrieve specific value but now, we only use exampletable.log()

Here is the result on my computer. Take a look carefully (๐Ÿ‘€):
Alt Text

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, letโ€™s combine double-hashing and linear probing. Recall the common second hash function, hash2(x)ย =ย Rย โˆ’ย (xย %ย R)hash2(x) \space = \space R \space โˆ’ \space (x \space \% \space R) , where xx is the result from hashing the first time, and RR 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;
}
Enter fullscreen mode Exit fullscreen mode

Execution:

function HashTable(size) { this.size = size; this.keys = this.initArray(size); this.values = this.initArray(size); this.limit = 0; } 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; } HashTable.prototype.initArray = function (size) { var array = []; for (var i = 0; i < size; i++) { array.push(null); } return array; } HashTable.prototype.log = function () { return { keys: this.keys, values: this.values }; } 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(); // You can also use exampletable.get(key) if you want to retrieve specific value but now, we only use exampletable.log()

Here is the result on my computer. Take a look carefully (๐Ÿ‘€):
Alt Text

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 (๐Ÿ“š)

Alt Text

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 7-8, 2020)


Alt Text

Posted on by:

edisonnpebojot profile

Edison Pebojot(๐Ÿ‘จโ€๐Ÿ’ป)

@edisonnpebojot

I started using computers and writing software around 2008 and 2009, I taught myself Programming. However, I wasn't a typical "nerd-klutz". ๐Ÿ˜…

Discussion

pic
Editor guide
 

So, hash table is a dictionary in Python?

 

Good question, yes, they are called hash map library in python instead of hash tables. (๐Ÿ˜ƒ)