search
HomeWeb Front-endJS TutorialDetailed introduction to hash table (hash table) in JavaScript (code example)

This article brings you a detailed introduction (code example) about hash tables (hash tables) in JavaScript. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you. help.

Hash table

Hash table (Hash table, also called hash table) directly accesses the memory storage location based on the key (Key) data structure. That is, it accesses the record by computing a function on the key value that maps the required query data to a location in the table, which speeds up the lookup. This mapping function is called a hash function, and the array storing the records is called a hash table.

Detailed introduction to hash table (hash table) in JavaScript (code example)

We start from the above picture to analyze

  • There is a set U, which are 1000, 10, 152, 9733, 1555, 997, 1168

  • The right side is a list (hash table) of 10 slots. We need to store the integers in the set U into this list

  • How to store it and in which slot? This problem needs to be solved through a hash function. My storage method is to take the remainder of 10. Let’s look at this picture

    • 1000 =0, 10 =0 Then the two integers 1000 and 10 will be It is stored in the slot numbered 0

    • 152 =2, then it is stored in the slot 2

    • 9733 =3 Stored in slot numbered 3

Through the above simple example, you should have a general understanding of the following points

  • The set U is the key that may appear in the hash table

  • The hash function is a method of your own design to convert the keys in the set U The value is stored in the hash table through some calculation, such as the remainder in the example

  • The hash table stores the calculated key

Then let’s see how we usually get the value?

For example, we store a key of 1000 and a value of 'Zhang San' ---> {key: 1000, value: 'Zhang San'}
From our above explanation, it Should it be stored in the slot of 1000?
When we want to find the value Zhang San through the key, can we just search in the key slot? At this point you can stop and think.

Some terms of hashing (you can take a brief look)

  • All the keys that may appear in the hash table are called the complete set U

  • Use M to represent the number of slots

  • Given a key, the hash function calculates which slot it should appear in. The hash function h=k% in the above example M, the hash function h is a mapping from key k to slot.

  • 1000 and 10 are both stored in the slot numbered 0. This situation is called a collision.

After reading this, I don’t know if you have a general understanding of what a hash function is. Through the example and your thinking, you can go back and read the definition of hash table at the top of the article. If you can read it, then I guess you should understand it.

Commonly used hash functions

Processing integers h=>k%M (that is, the example we gave above)

Processing strings:

    function h_str(str,M){
        return [...str].reduce((hash,c)=>{
            hash = (31*hash + c.charCodeAt(0)) % M
        },0)
    }

The hash algorithm is not the focus here, and I have not studied it in depth. The main thing here is to understand what kind of data structure a hash table is, what advantages it has, and what specifically it does.
The hash function just maps keys to lists through a certain algorithm.

Building a hash table

Through the above explanation, we will make a simple hash table here

The composition of the hash table

  • M slots

  • There is a hash function

  • There is an add method to add the key value to the hash table

  • There is a delete method to delete

  • There is a search method to find the corresponding value based on the key

Initialization

- Initialize how many slots the hash table has
- Use an array to create M slots

    class HashTable {
        constructor(num=1000){
            this.M = num;
            this.slots = new Array(num);
        }
    }

Hash function

Hash function for processing strings, Strings are used here because values ​​can also be transferred into strings, which is more general.

First convert the passed key value into a string. In order to be more rigorous,

convert the string is an array, for example 'abc' => [...'abc'] => ['a','b','c']

Calculate the charCodeAt of each character separately, The purpose of taking the remainder of M is to exactly correspond to the number of slots. You only have 10 slots in total, and your value will definitely fall into the slots of 0-9

    h(str){
        str = str + '';
        return [...str].reduce((hash,c)=>{
            hash = (331 * hash + c.charCodeAt()) % this.M;
            return hash;
        },0)
    }

Add

Call the hash function Get the corresponding storage address (which is the slot of our analogy)

Because there may be multiple values ​​stored in a slot, it needs to be represented by a two-dimensional array, such as the slot number we calculated is 0, which is slot[0], then we should store it in slot[0] [0]. If the slot that comes in later is also the slot numbered 0, then we should store it in slot[0] [1]

    add(key,value) {
        const h = this.h(key);
        // 判断这个槽是否是一个二维数组, 不是则创建二维数组
        if(!this.slots[h]){
            this.slots[h] = [];
        }
        // 将值添加到对应的槽中
        this.slots[h].push(value);
    }

Delete

Find the slot through hash algorithm

Delete through filtering

    delete(key){
        const h = this.h(key);
        this.slots[h] = this.slots[h].filter(item=>item.key!==key);
    }

Find

Find the corresponding slot through hash algorithm

Use the find function to find the value of the same key

Return the corresponding value

    search(key){
        const h = this.h(key);
        const list = this.slots[h];
        const data = list.find(x=> x.key === key);
        return data ? data.value : null;    
    }

总结

讲到这里,散列表的数据结构已经讲完了,其实我们每学一种数据结构或算法的时候,不是去照搬实现的代码,我们要学到的是思想,比如说散列表它究竟做了什么,它是一种存储方式,可以快速的通过键去查找到对应的值。那么我们会思考,如果我们设计的槽少了,在同一个槽里存放了大量的数据,那么这个散列表它的搜索速度肯定是会大打折扣的,这种情况又应该用什么方式去解决,又或者是否用其他的数据结构的代替它。

补充一个小知识点

v8引擎中的数组 arr = [1,2,3,4,5] 或 new Array(100) 我们都知道它是开辟了一块连续的空间去存储,而arr = [] , arr[100000] = 10 这样的操作它是使用的散列,因为这种操作如果连续开辟100万个空间去存储一个值,那么显然是在浪费空间。


The above is the detailed content of Detailed introduction to hash table (hash table) in JavaScript (code example). For more information, please follow other related articles on the PHP Chinese website!

Statement
This article is reproduced at:segmentfault. If there is any infringement, please contact admin@php.cn delete
From Websites to Apps: The Diverse Applications of JavaScriptFrom Websites to Apps: The Diverse Applications of JavaScriptApr 22, 2025 am 12:02 AM

JavaScript is widely used in websites, mobile applications, desktop applications and server-side programming. 1) In website development, JavaScript operates DOM together with HTML and CSS to achieve dynamic effects and supports frameworks such as jQuery and React. 2) Through ReactNative and Ionic, JavaScript is used to develop cross-platform mobile applications. 3) The Electron framework enables JavaScript to build desktop applications. 4) Node.js allows JavaScript to run on the server side and supports high concurrent requests.

Python vs. JavaScript: Use Cases and Applications ComparedPython vs. JavaScript: Use Cases and Applications ComparedApr 21, 2025 am 12:01 AM

Python is more suitable for data science and automation, while JavaScript is more suitable for front-end and full-stack development. 1. Python performs well in data science and machine learning, using libraries such as NumPy and Pandas for data processing and modeling. 2. Python is concise and efficient in automation and scripting. 3. JavaScript is indispensable in front-end development and is used to build dynamic web pages and single-page applications. 4. JavaScript plays a role in back-end development through Node.js and supports full-stack development.

The Role of C/C   in JavaScript Interpreters and CompilersThe Role of C/C in JavaScript Interpreters and CompilersApr 20, 2025 am 12:01 AM

C and C play a vital role in the JavaScript engine, mainly used to implement interpreters and JIT compilers. 1) C is used to parse JavaScript source code and generate an abstract syntax tree. 2) C is responsible for generating and executing bytecode. 3) C implements the JIT compiler, optimizes and compiles hot-spot code at runtime, and significantly improves the execution efficiency of JavaScript.

JavaScript in Action: Real-World Examples and ProjectsJavaScript in Action: Real-World Examples and ProjectsApr 19, 2025 am 12:13 AM

JavaScript's application in the real world includes front-end and back-end development. 1) Display front-end applications by building a TODO list application, involving DOM operations and event processing. 2) Build RESTfulAPI through Node.js and Express to demonstrate back-end applications.

JavaScript and the Web: Core Functionality and Use CasesJavaScript and the Web: Core Functionality and Use CasesApr 18, 2025 am 12:19 AM

The main uses of JavaScript in web development include client interaction, form verification and asynchronous communication. 1) Dynamic content update and user interaction through DOM operations; 2) Client verification is carried out before the user submits data to improve the user experience; 3) Refreshless communication with the server is achieved through AJAX technology.

Understanding the JavaScript Engine: Implementation DetailsUnderstanding the JavaScript Engine: Implementation DetailsApr 17, 2025 am 12:05 AM

Understanding how JavaScript engine works internally is important to developers because it helps write more efficient code and understand performance bottlenecks and optimization strategies. 1) The engine's workflow includes three stages: parsing, compiling and execution; 2) During the execution process, the engine will perform dynamic optimization, such as inline cache and hidden classes; 3) Best practices include avoiding global variables, optimizing loops, using const and lets, and avoiding excessive use of closures.

Python vs. JavaScript: The Learning Curve and Ease of UsePython vs. JavaScript: The Learning Curve and Ease of UseApr 16, 2025 am 12:12 AM

Python is more suitable for beginners, with a smooth learning curve and concise syntax; JavaScript is suitable for front-end development, with a steep learning curve and flexible syntax. 1. Python syntax is intuitive and suitable for data science and back-end development. 2. JavaScript is flexible and widely used in front-end and server-side programming.

Python vs. JavaScript: Community, Libraries, and ResourcesPython vs. JavaScript: Community, Libraries, and ResourcesApr 15, 2025 am 12:16 AM

Python and JavaScript have their own advantages and disadvantages in terms of community, libraries and resources. 1) The Python community is friendly and suitable for beginners, but the front-end development resources are not as rich as JavaScript. 2) Python is powerful in data science and machine learning libraries, while JavaScript is better in front-end development libraries and frameworks. 3) Both have rich learning resources, but Python is suitable for starting with official documents, while JavaScript is better with MDNWebDocs. The choice should be based on project needs and personal interests.

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

Atom editor mac version download

Atom editor mac version download

The most popular open source editor

SublimeText3 Linux new version

SublimeText3 Linux new version

SublimeText3 Linux latest version

mPDF

mPDF

mPDF is a PHP library that can generate PDF files from UTF-8 encoded HTML. The original author, Ian Back, wrote mPDF to output PDF files "on the fly" from his website and handle different languages. It is slower than original scripts like HTML2FPDF and produces larger files when using Unicode fonts, but supports CSS styles etc. and has a lot of enhancements. Supports almost all languages, including RTL (Arabic and Hebrew) and CJK (Chinese, Japanese and Korean). Supports nested block-level elements (such as P, DIV),

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

SecLists

SecLists

SecLists is the ultimate security tester's companion. It is a collection of various types of lists that are frequently used during security assessments, all in one place. SecLists helps make security testing more efficient and productive by conveniently providing all the lists a security tester might need. List types include usernames, passwords, URLs, fuzzing payloads, sensitive data patterns, web shells, and more. The tester can simply pull this repository onto a new test machine and he will have access to every type of list he needs.