Knowledge Bank
  • My GitBook
  • Miscellaneous
  • Project
    • Rider and Intellij
    • Code
    • Frontend
      • Condition
      • AddConditionModalDialog
    • Backend
    • e2e
      • fragments
  • JAVASCRIPT
    • Promise
    • Destructuring
    • Spread Syntax and Rest Parameters
    • Typescript
      • Examples of Types
      • React Typescript
    • This
    • Dot Notation vs Bracket Notation
    • Shallow vs Deep Clone
    • New ES Edition
  • C#
    • Project Note
    • Basic
    • Shortcut and Debugging
  • Programming Paradigms
    • SOLID Principles
    • Object Oriented Programming (OOP)
      • Evolution of OOP (Procedural to OOP)
      • Instantiation
      • 4 Pillars of OOP
      • Extra
    • Functional Programming (FP)
      • Idempotent
      • Imperative vs Declarative
      • Immutability
      • High Order Function and Closure
      • Currying
      • Partial Application
      • Memoization and Caching
      • Compose and Pipe
      • Extra
      • Example of FP
    • OOP vs FP
      • Composition vs Inheritance
  • DATA STRUCTURE
    • Big O
    • Data Structure
    • Array
    • Hash Table
    • Linked List
    • Queue and Stack
    • Tree
      • Binary Heap
      • Trie
    • Graph
      • Example of Graph
  • React-Redux
    • MobX
    • Best Practices
  • Algorithms
    • Recursion
      • Examples of Recursion
    • Sorting
    • Searching and Traversal
    • Dynamic Programming
  • REFACTORING
    • Clean Code
      • Formatting
      • Error Handling
      • Concurrency
      • Testing
      • SOLID Principles
      • Classes
      • Objects and Data Structures
      • Variables
      • Functions
    • Code Smells
      • Long Function
      • Duplicate Code
      • Loops
      • Double Negative
      • Christmas Tree Code
      • Complex Condition
      • Primitive Obsession
      • Speculative Generality
      • God Class
      • Long Parameter List
  • Junior to Senior
    • AWS
      • Lambda
    • Session + Authentication
    • Redis
    • Kubernetes
      • Networking
      • Services
      • Deployment
      • Replica Set
      • YAML
      • pod-definition.yml
      • Kubectl
      • Pods
      • Fundamentals
    • Docker
      • Operating System - Extra
      • Dockerfile - Docker Image
      • Docker Storage
      • Docker Network
      • Docker Registry
      • Docker Command
      • Docker Compose
      • Docker Compose - Postgres
    • Security
      • Logging
      • HTTPS, Cross-Site-Scripting (XSS) and Cross-Site-Request-Forgery (CSRF)
      • 3rd Party Library
      • Injection
      • Code Secret, Secure Header, Access Control, Data Management, Authentication
    • CI/CD
    • SPA vs Server-Side Rendering
    • Performance
      • Optimized Code
      • Critical Render Path
      • Backend Optimization
      • Minimized Files and Images
      • Minimized Delivery
  • SECURITY
    • Encryption
    • SSH
  • Command
  • Cheatsheet
    • NPM
    • GIT
  • Writing Template
    • Guide
    • API
    • ChangeLog
    • FAQ
  • Linux
Powered by GitBook
On this page

Was this helpful?

  1. DATA STRUCTURE

Hash Table

PreviousArrayNextLinked List

Last updated 5 years ago

Was this helpful?

Hash table has key-value pair. How it works is the KEY is used as the index of where to find the VALUE in memory. This is done with Hash Function - it is a function that generates a fixed value for each input that it gets (idempotent)

Hash function is going to take the KEY and generate some sort gibberish number that convert into an address space and index space. Unlike array where there is ordered index, with hash table all we need is to give a key and we know exactly where that item is in our memory.

  • Search - O(1)

  • Insert - O(1)

  • Lookup - O(1)

  • Delete - O(1)

Advantages of Hash Table

  1. Fast lookup* Good collision resolution needed

  2. Fast insert - It is un-ordered thus we do not have to shift indexes like arrays

  3. Flexible keys - unlike array, where it is indexed from 0, 1, 2... etc

Downside

  1. Un-ordered - there is nothing to tell the hash function to evenly distribute data in the memory spaces. So there is a possibility of collision (see picture)

  2. Slow key iteration - if you want to get all the keys, you have to loop the entire memory space (if you allocate 50 as size, but put only 3 items, you have to loop the whole length of 50) VS array that just loop only the length of an array. If it has 3 keys, it would have looped over 3 times only

Collision - when you have collision, it slows down reading and inserting with a hash table, O(n) because if we have many data in one address space, we have to loop. One way to deal with collision is linked-list

Types of Hash Table:

  1. Object - it allows only string keys, so if you pass a number or function, it get stringify

  2. Map - it allows you to save any data type as key. Map maintain insertion order VS Object that does not maintain order, random insertion

  3. Set - similar to Map. The only difference is that it only store the unique keys with no values