Jadual Kandungan
散列的一些术语(可以简单的看一下)
常用的散列函数
构建散列表
散列表的组成
初始化
散列函数
添加
删除
查找
总结
补充一个小知识点
Rumah hujung hadapan web tutorial js JavaScript中散列表(哈希表)的详细介绍(代码示例)

JavaScript中散列表(哈希表)的详细介绍(代码示例)

Jan 02, 2019 am 09:37 AM
javascript node.js struktur data

本篇文章给大家带来的内容是关于JavaScript中散列表(哈希表)的详细介绍(代码示例),有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。

散列表

散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。

2472848212-5c2afb47f10ad_articlex.png

我们从上图开始分析

  • 有一个集合U,里面分别是1000,10,152,9733,1555,997,1168

  • 右侧是一个10个插槽的列表(散列表),我们需要把集合U中的整数存放到这个列表中

  • 怎么存放,分别存在哪个槽里?这个问题就是需要通过一个散列函数来解决了。我的存放方式是取10的余数,我们对应这图来看

    • 1000%10=0,10%10=0 那么1000和10这两个整数就会被存储到编号为0的这个槽中

    • 152%10=2那么就存放到2的槽中

    • 9733%10=3 存放在编号为3的槽中

通过上面简单的例子,应该会有一下几点一个大致的理解

  • 集合U,就是可能会出现在散列表中的键

  • 散列函数,就是你自己设计的一种如何将集合U中的键值通过某种计算存放到散列表中,如例子中的取余数

  • 散列表,存放着通过计算后的键

那么我们在接着看一般我们会怎么去取值呢?

比如我们存储一个key为1000,value为'张三' ---> {key:1000,value:'张三'}
从我们上述的解释,它是不是应该存放在1000%10的这个插槽里。
当我们通过key想要找到value张三,是不是到key%10这个插槽里找就可以了呢?到了这里你可以停下来思考一下。

散列的一些术语(可以简单的看一下)

  • 散列表中所有可能出现的键称作全集U

  • 用M表示槽的数量

  • 给定一个键,由散列函数计算它应该出现在哪个槽中,上面例子的散列函数h=k%M,散列函数h就是键k到槽的一个映射。

  • 1000和10都被存到了编号0的这个槽中,这种情况称之为碰撞。

看到这里不知道你是否大致理解了散列函数是什么了没。通过例子,再通过你的思考,你可以回头在读一遍文章头部关于散列表的定义。如果你能读懂了,那么我估计你应该是懂了。

常用的散列函数

处理整数 h=>k%M (也就是我们上面所举的例子)

处理字符串:

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

hash算法不是这里的重点,我也没有很深入的去研究,这里主要还是去理解散列表是个怎样的数据结构,它有哪些优点,它具体做了怎样一件事。
而hash函数它只是通过某种算法把key映射到列表中。

构建散列表

通过上面的解释,我们这里做一个简单的散列表

散列表的组成

  • M个槽

  • 有个hash函数

  • 有一个add方法去把键值添加到散列表中

  • 有一个delete方法去做删除

  • 有一个search方法,根据key去找到对应的值

初始化

- 初始化散列表有多少个槽
- 用一个数组来创建M个槽

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

散列函数

处理字符串的散列函数,这里使用字符串是因为,数值也可以传换成字符串比较通用一些

先将传递过来的key值转为字符串,为了能够严谨一些

将字符串转换为数组, 例如'abc' => [...'abc'] => ['a','b','c']

分别对每个字符的charCodeAt进行计算,取M余数是为了刚好对应插槽的数量,你总共就10个槽,你的数值%10 肯定会落到 0-9的槽里

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

添加

调用hash函数得到对应的存储地址(就是我们之间类比的槽)

因为一个槽中可能会存多个值,所以需要用一个二维数组去表示,比如我们计算得来的槽的编号是0,也就是slot[0],那么我们应该往slot[0] [0]里存,后面进来的同样是编号为0的槽的话就接着往slot[0] [1]里存

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

删除

通过hash算法,找到所在的槽

通过过滤来删除

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

查找

通过hash算法找到对应的槽

用find函数去找同一个key的值

返回对应的值

    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;    
    }
Salin selepas log masuk

总结

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

补充一个小知识点

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


Atas ialah kandungan terperinci JavaScript中散列表(哈希表)的详细介绍(代码示例). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Alat AI Hot

Undresser.AI Undress

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Clothoff.io

Penyingkiran pakaian AI

AI Hentai Generator

AI Hentai Generator

Menjana ai hentai secara percuma.

Artikel Panas

R.E.P.O. Kristal tenaga dijelaskan dan apa yang mereka lakukan (kristal kuning)
2 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Repo: Cara menghidupkan semula rakan sepasukan
4 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Cara mendapatkan biji gergasi
4 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌

Alat panas

Notepad++7.3.1

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Bandingkan struktur data kompleks menggunakan perbandingan fungsi Java Bandingkan struktur data kompleks menggunakan perbandingan fungsi Java Apr 19, 2024 pm 10:24 PM

Apabila menggunakan struktur data kompleks dalam Java, Comparator digunakan untuk menyediakan mekanisme perbandingan yang fleksibel. Langkah-langkah khusus termasuk: mentakrifkan kelas pembanding, menulis semula kaedah bandingkan untuk menentukan logik perbandingan. Buat contoh pembanding. Gunakan kaedah Collections.sort, menghantar contoh koleksi dan pembanding.

Pemahaman mendalam tentang jenis rujukan dalam bahasa Go Pemahaman mendalam tentang jenis rujukan dalam bahasa Go Feb 21, 2024 pm 11:36 PM

Jenis rujukan ialah jenis data khas dalam bahasa Go Nilai mereka tidak menyimpan data itu sendiri secara langsung, tetapi alamat data yang disimpan. Dalam bahasa Go, jenis rujukan termasuk kepingan, peta, saluran dan penunjuk. Pemahaman mendalam tentang jenis rujukan adalah penting untuk memahami pengurusan memori dan kaedah pemindahan data bahasa Go. Artikel ini akan menggabungkan contoh kod khusus untuk memperkenalkan ciri dan penggunaan jenis rujukan dalam bahasa Go. 1. Slices Slices ialah salah satu jenis rujukan yang paling biasa digunakan dalam bahasa Go.

Struktur dan algoritma data Java: penjelasan mendalam Struktur dan algoritma data Java: penjelasan mendalam May 08, 2024 pm 10:12 PM

Struktur data dan algoritma ialah asas pembangunan Java Artikel ini meneroka secara mendalam struktur data utama (seperti tatasusunan, senarai terpaut, pepohon, dll.) dan algoritma (seperti pengisihan, carian, algoritma graf, dll.) dalam Java. Struktur ini diilustrasikan dengan contoh praktikal, termasuk menggunakan tatasusunan untuk menyimpan skor, senarai terpaut untuk mengurus senarai beli-belah, tindanan untuk melaksanakan rekursi, baris gilir untuk menyegerakkan benang, dan pepohon dan jadual cincang untuk carian dan pengesahan pantas. Memahami konsep ini membolehkan anda menulis kod Java yang cekap dan boleh diselenggara.

Era AI JS sudah tiba! Era AI JS sudah tiba! Apr 08, 2024 am 09:10 AM

Pengenalan kepada JS-Torch JS-Torch ialah perpustakaan JavaScript pembelajaran mendalam yang sintaksnya hampir sama dengan PyTorch. Ia mengandungi objek tensor berfungsi sepenuhnya (boleh digunakan dengan kecerunan yang dijejaki), lapisan dan fungsi pembelajaran mendalam, dan enjin pembezaan automatik. JS-Torch sesuai untuk penyelidikan pembelajaran mendalam dalam JavaScript dan menyediakan banyak alatan dan fungsi yang mudah untuk mempercepatkan pembangunan pembelajaran mendalam. Image PyTorch ialah rangka kerja pembelajaran mendalam sumber terbuka yang dibangunkan dan diselenggara oleh pasukan penyelidik Meta. Ia menyediakan set alat dan perpustakaan yang kaya untuk membina dan melatih model rangkaian saraf. PyTorch direka bentuk untuk menjadi ringkas, fleksibel dan mudah digunakan, dan ciri graf pengiraan dinamiknya menjadikan

Analisis penuh rangka kerja pengumpulan Java: membedah struktur data dan mendedahkan rahsia storan yang cekap Analisis penuh rangka kerja pengumpulan Java: membedah struktur data dan mendedahkan rahsia storan yang cekap Feb 23, 2024 am 10:49 AM

Gambaran Keseluruhan Rangka Kerja Koleksi Java Rangka kerja pengumpulan Java ialah bahagian penting dalam bahasa pengaturcaraan Java Ia menyediakan satu siri perpustakaan kelas kontena yang boleh menyimpan dan mengurus data. Pustaka kelas kontena ini mempunyai struktur data yang berbeza untuk memenuhi keperluan penyimpanan dan pemprosesan data dalam senario yang berbeza. Kelebihan rangka kerja koleksi ialah ia menyediakan antara muka bersatu, membolehkan pembangun mengendalikan perpustakaan kelas kontena yang berbeza dengan cara yang sama, dengan itu mengurangkan kesukaran pembangunan. Struktur data rangka kerja pengumpulan Java Rangka kerja pengumpulan Java mengandungi pelbagai struktur data, setiap satunya mempunyai ciri unik dan senario yang boleh digunakan. Berikut adalah beberapa struktur data rangka kerja pengumpulan Java yang biasa: 1. Senarai: Senarai ialah koleksi tersusun yang membolehkan elemen diulang. Li

Struktur data PHP: Keseimbangan pepohon AVL, mengekalkan struktur data yang cekap dan teratur Struktur data PHP: Keseimbangan pepohon AVL, mengekalkan struktur data yang cekap dan teratur Jun 03, 2024 am 09:58 AM

Pokok AVL ialah pokok carian binari seimbang yang memastikan operasi data yang pantas dan cekap. Untuk mencapai keseimbangan, ia melakukan operasi belok kiri dan kanan, melaraskan subpokok yang melanggar keseimbangan. Pokok AVL menggunakan pengimbangan ketinggian untuk memastikan ketinggian pokok sentiasa kecil berbanding bilangan nod, dengan itu mencapai kerumitan masa logaritma (O(logn)) operasi carian dan mengekalkan kecekapan struktur data walaupun pada set data yang besar.

Perbandingan Golang dan Node.js dalam pembangunan back-end Perbandingan Golang dan Node.js dalam pembangunan back-end Jun 03, 2024 pm 02:31 PM

Go dan Node.js mempunyai perbezaan dalam menaip (kuat/lemah), konkurensi (goroutine/gelung peristiwa) dan pengumpulan sampah (automatik/manual). Go mempunyai daya pemprosesan yang tinggi dan kependaman rendah, dan sesuai untuk bahagian belakang beban tinggi Node.js bagus pada I/O tak segerak dan sesuai untuk permintaan serentak tinggi dan pendek. Kes praktikal kedua-duanya termasuk Kubernetes (Go), sambungan pangkalan data (Node.js) dan aplikasi web (Go/Node.js). Pilihan terakhir bergantung pada keperluan aplikasi, kemahiran pasukan, dan keutamaan peribadi.

Ketahui rahsia struktur data bahasa Go secara mendalam Ketahui rahsia struktur data bahasa Go secara mendalam Mar 29, 2024 pm 12:42 PM

Kajian mendalam tentang misteri struktur data bahasa Go memerlukan contoh kod khusus Sebagai bahasa pengaturcaraan yang ringkas dan cekap, bahasa Go juga menunjukkan daya tarikannya yang unik dalam memproses struktur data. Struktur data adalah konsep asas dalam sains komputer, yang bertujuan untuk mengatur dan mengurus data supaya ia boleh diakses dan dimanipulasi dengan lebih cekap. Dengan mempelajari secara mendalam tentang misteri struktur data bahasa Go, kami dapat memahami dengan lebih baik cara data disimpan dan dikendalikan, seterusnya meningkatkan kecekapan pengaturcaraan dan kualiti kod. 1. Array Array ialah salah satu struktur data yang paling mudah

See all articles