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
Java中的二叉树结构详解Java中的二叉树结构详解Jun 16, 2023 am 08:58 AM

二叉树是计算机科学中常见的数据结构,也是Java编程中常用的一种数据结构。本文将详细介绍Java中的二叉树结构。一、什么是二叉树?在计算机科学中,二叉树是一种树形结构,每个节点最多有两个子节点。其中,左侧子节点比父节点小,右侧子节点则比父节点大。在Java编程中,常用二叉树表示排序,搜索以及提高对数据的查询效率。二、Java中的二叉树实现在Java中,二叉树

Python 实现栈的几种方式及其优劣Python 实现栈的几种方式及其优劣May 19, 2023 am 09:37 AM

​​想了解更多关于开源的内容,请访问:​​​​51CTO开源基础软件社区​​​​https://ost.51cto.com​​一、栈的概念栈由一系列对象对象组织的一个集合,这些对象的增加和删除操作都遵循一个“后进先出”(LastInFirstOut,LIFO)的原则。在任何时刻只能向栈中插入一个对象,但只能取得或者删除只能在栈顶进行。比如由书构成的栈,唯一露出封面的书就是顶部的那本,为了拿到其他的书,只能移除压在上面的书,如图:栈的实际应用实际上很多应用程序都会用到栈,比如:网络浏览器将最近浏览

PHP8中会支持的数据结构,将为你的代码提供更大空间PHP8中会支持的数据结构,将为你的代码提供更大空间Jun 21, 2023 am 08:13 AM

PHP是一种广泛使用的脚本语言,被广泛用于Web开发,服务器端编程以及命令行编程等。随着PHP不断更新和发展,它也日益成为一个更强大的编程工具,为用户提供了更多的功能和更多的工具来开发高质量的应用程序。其中,数据结构是一个非常重要的领域,一种有效的数据结构可以大大提高程序的性能和可读性。在这篇文章中,我们将讨论PHP8中支持的新数据结构,这些新的数据结构将让

如何解决Java中遇到的代码性能优化问题如何解决Java中遇到的代码性能优化问题Jun 29, 2023 am 10:13 AM

如何解决Java中遇到的代码性能优化问题随着现代软件应用的复杂性和数据量的增加,对于代码性能的需求也变得越来越高。在Java开发中,我们经常会遇到一些性能瓶颈,如何解决这些问题成为了开发者们关注的焦点。本文将介绍一些常见的Java代码性能优化问题,并提供一些解决方案。一、避免过多的对象创建和销毁在Java中,对象的创建和销毁是需要耗费资源的。因此,当一个方法

Java语言中的数据结构与算法介绍Java语言中的数据结构与算法介绍Jun 10, 2023 pm 01:37 PM

随着计算机科学的不断发展,数据结构与算法成为了计算机科学领域中最为基础、重要的模块。数据结构是一种组织和存储数据的方式,它是解决问题的基础。算法则是计算机科学的核心,它是指在计算机程序中解决问题的方法和技术。Java作为一种广泛应用的编程语言,其自带的数据结构和算法库是非常强大的,赋予了开发人员更多的力量。一、数据结构Java中提供了多种数据结构,包括数组

go语言有哪些数据结构go语言有哪些数据结构Dec 16, 2022 pm 02:00 PM

go语言数据结构有四大类:1、基础类型,包括整型(有符号和无符号整数)、浮点数、复数、字符串(由不可变的字节序列构成)、布尔值(只有true和false两个值);2、聚合类型,包括数组、结构体(是由任意个任意类型的变量组合在一起的数据类型);3、引用类型,包括指针、slice(是一个拥有相同元素的可变长度序列)、map、function、channel;4、接口类型。

c语言中数据结构是什么?常见数据结构有哪些?c语言中数据结构是什么?常见数据结构有哪些?Nov 03, 2020 am 11:38 AM

c语言中,数据结构是指相互之间存在一种或多种特定关系的数据元素的集合,它是计算机存储、组织数据的方式;常见数据结构有:线性数据结构(数组、链表、栈、队列和线性表)、树形结构(二叉树、完全二叉树、二叉查找树、堆)、图形结构(有向图和无向图)。

如何使用Python正则表达式进行数据结构和算法如何使用Python正则表达式进行数据结构和算法Jun 22, 2023 pm 08:01 PM

Python正则表达式是一种基于模式匹配的字符串处理工具,它可以帮助我们快速有效地从文本中提取所需信息。在数据结构和算法中,正则表达式可以用来实现文本匹配、替换、分割等功能,为我们的编程提供更加强大的支持。本文将介绍如何使用Python正则表达式进行数据结构和算法。一、正则表达式的基础知识在开始之前,先了解一下正则表达式的一些基础知识:字符集:用方括号表示,

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

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
3 weeks agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

WebStorm Mac version

WebStorm Mac version

Useful JavaScript development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Safe Exam Browser

Safe Exam Browser

Safe Exam Browser is a secure browser environment for taking online exams securely. This software turns any computer into a secure workstation. It controls access to any utility and prevents students from using unauthorized resources.

Dreamweaver Mac version

Dreamweaver Mac version

Visual web development tools