let hashCode = 0

//取一个很大的数

for (let i = 0; i < str.length; i ++) {

hashCode = 37 * hashCode + str.charCodeAt(i)

}

//取余

return hashCode % size

}

// 插入或修改数据

HashTable.prototype.put = function (key, value) {

// 1.哈希化获得下标值

let index = this.hashFunc(key, this.length)

let current = this.storage[index]

// 2.判断该下标值的位置是否有数据

// 2.1无数据

if(!current) {

this.storage[index] = [[key, value]]

this.count ++

return;

}

// 2.2有数据

// 3.遍历对应索引上的数组

for (let i = 0; i < current.length; i ++) {

// 3.1已存在相同数据

if(current[i][0] === key) {

current[i][1] = value

return;

}

}

// 3.2未存在相同数据,直接添加数据

current.push([key, value])

this.count ++

}

}

我们来使用一下该方法

let ht = new HashTable()

// 执行put()方法6次

ht.put(‘abc’, ‘123’)

ht.put(‘hgf’, ‘124’)

ht.put(‘wds’, ‘125’)

ht.put(‘wer’, ‘126’)

ht.put(‘kgl’, ‘127’)

ht.put(‘kmg’, ‘128’)

// 查看哈希表内数据个数

console.log(ht.count) // 6

// 通过storage属性查看一下哈希表的内部结构

console.log(ht.storage)

/* storage打印结果

[

[ [ ‘wds’, ‘125’ ], [ ‘kgl’, ‘127’ ], [ ‘kmg’, ‘128’ ] ],

[ [ ‘wer’, ‘126’ ] ],

,

[ [ ‘hgf’, ‘124’ ] ],

[ [ ‘abc’, ‘123’ ] ]

]

*/

此时的哈希表内部是这样的

（4）实现get()方法

get()方法是用于查询哈希表中某个数据。该方法直接收一个参数，即用于查询的 key

实现思路：

通过哈希函数，将 key 哈希化，获取一个索引 index

判断哈希表 storage 数组的索引 index 上有无数据，若无，则返回 false

若有数据，则遍历该索引上的数组每个元素，比对每个元素的 key 是否与我们传入的 key 相等，若有查询到相等的值，则返回该值的 value

若无数据，则返回 false

思路和代码都比较简单，我们直接来看代码

function HashTable() {

// 属性

// 用于存储数据

this.storage = []

// 统计哈希表内数据个数

this.count = 0

// 设定哈希表初始长度

this.length = 7

//封装哈希函数

HashTable.prototype.hashFunc = function (str, size) {

let hashCode = 0

//取一个很大的数

for (let i = 0; i < str.length; i ++) {

hashCode = 37 * hashCode + str.charCodeAt(i)

}

//取余

return hashCode % size

}

// 获取数据

HashTable.prototype.get = function (key) {

// 1.获取相应的下标值

let index = this.hashFunc(key, this.length)

let current = this.storage[index]

// 2.判断该下标值的位置是否有数据

// 2.1 若该下标值位置不存在任何数据，则查找失败

if(!current) {

return false

}

// 2.2 该下标值位置有数据

// 3. 进行遍历查找

for(let i in current) {

// 3.1 找到对应数据并返回value

if(current[i][0] === key) {

return current[i][1]

}

}

// 3.2 没有找到对应数据，返回false

return false

}

}

我们来使用以下该方法

let ht = new HashTable()

// 执行put()方法 6次

ht.put(‘abc’, ‘123’)

ht.put(‘hgf’, ‘124’)

ht.put(‘wds’, ‘125’)

ht.put(‘wer’, ‘126’)

ht.put(‘kgl’, ‘127’)

ht.put(‘kmg’, ‘128’)

// 执行get()方法，获取 key为 ‘hgf’ 的值

console.log(ht.get(‘hgf’)) // 124

（5）实现del()方法（不具备减少容量功能）

del()方法是删除哈希表中某个数据。该方法接收一个参数 key

实现思路：

通过哈希函数，将 key 哈希化，获取一个索引 index

判断哈希表 storage 数组的索引 index 上有无数据，若无，则返回 false ，表示删除失败

若有数据，则遍历该索引上的数组每个元素，比对每个元素的 key 是否与我们传入的 key 相等，若有查询到相等的值，则直接删除该值，此时 this.count --，并返回被删除元素的 value值

若没有查询到相等的值，则返回 false ，表示删除失败

我们来看一下代码

function HashTable() {

// 属性

// 用于存储数据

this.storage = []

// 统计哈希表内数据个数

this.count = 0

// 设定哈希表初始长度

this.length = 7

//封装哈希函数

HashTable.prototype.hashFunc = function (str, size) {

let hashCode = 0

//取一个很大的数

for (let i = 0; i < str.length; i ++) {

hashCode = 37 * hashCode + str.charCodeAt(i)

}

//取余

return hashCode % size

}

// 删除数据

HashTable.prototype.del = function (key) {

// 1.获取相应的下标值

let index = this.hashFunc(key, this.length)

let current = this.storage[index]

// 2. 判断该索引位置有无数据

// 2.1 该下标值位置没有数据，返回false，删除失败

if(!current) {

return false

}

// 2.2 该下标值位置有数据

// 3. 遍历数组查找对应数据

for (let i in current) {

let inner = current[i]

// 3.1 找到对应数据了，删除该数据

if(inner[0] === key) {

current.splice(i, 1)

this.count –

return inner[1]

}

}

// 3.2 没有找到对应数据，则删除失败，返回false

return false

}

}

我们来使用一下该方法

let ht = new HashTable()

// 执行put()方法 6次

ht.put(‘abc’, ‘123’)

ht.put(‘hgf’, ‘124’)

ht.put(‘wds’, ‘125’)

ht.put(‘wer’, ‘126’)

ht.put(‘kgl’, ‘127’)

ht.put(‘kmg’, ‘128’)

// 删除 key为 'hgf’的元素

ht.del(‘hgf’) // 删除成功，返回 124

// 删除 key为 'ppp’的元素

ht.del(‘ppp’) // 删除失败，返回 false

// 查看哈希表内部结构

console.log(ht.storage)

/* storage打印结果

[

[ [ ‘wds’, ‘125’ ], [ ‘kgl’, ‘127’ ], [ ‘kmg’, ‘128’ ] ],

[ [ ‘wer’, ‘126’ ] ],

,

[],

[ [ ‘abc’, ‘123’ ] ]

]

*/

此时的哈希表内是这样的

（6）实现isEmpty()方法

isEmpty()方法是用于判断哈希表是否为空。该方法无需传参

该方法思路比较简单，直接判断属性 count 是否为 0 即可

我们来看一下代码

function HashTable() {

// 属性

// 用于存储数据

this.storage = []

// 统计哈希表内数据个数

this.count = 0

// 设定哈希表初始长度

this.length = 7

//封装哈希函数

HashTable.prototype.hashFunc = function (str, size) {

let hashCode = 0

//取一个很大的数

for (let i = 0; i < str.length; i ++) {

hashCode = 37 * hashCode + str.charCodeAt(i)

}

//取余

return hashCode % size

}

//判断哈希表是否为空

HashTable.prototype.isEmpty = function () {

return this.count === 0

}

}

我们来用一下该方法

let ht = new HashTable()

console.log(ht.isEmpty()) // false,哈希表为空

ht.put(‘abc’, ‘123’)

console.log(ht.isEmpty()) // true,哈希表不为空

（7）实现size()方法

size()方法就是用于返回哈希表中数据个数。该方法也无需传参

该方法实现思路也特别简单，直接返回属性 count 即可

我们来看一下代码

function HashTable() {

// 属性

// 用于存储数据

this.storage = []

// 统计哈希表内数据个数

this.count = 0

// 设定哈希表初始长度

this.length = 7

//封装哈希函数

HashTable.prototype.hashFunc = function (str, size) {

let hashCode = 0

//取一个很大的数

for (let i = 0; i < str.length; i ++) {

hashCode = 37 * hashCode + str.charCodeAt(i)

}

//取余

return hashCode % size

}

// 返回哈希表内元素个数

HashTable.prototype.size = function () {

return this.count

}

}

我们来用一下该方法

let ht = new HashTable()

console.log(ht.size()) // 0,哈希表内没有数据

ht.put(‘abc’, ‘123’)

console.log(ht.size()) // 1,哈希表内有一条数据

（8）实现resize()方法

resize()方法就是用来对哈希表的容量进行改变的，当填充因子过大，我们就对其进行扩容；当填充因子较小，我们就增加其容量。该方法接收一个参数 newLength，表示新的哈希表的容量。

实现思路：

将原本的属性 storage 赋值给一个新的变量 oldStorage，然后我们创建一个新的空数组赋值给 storage，并将参数 newLength 赋值给属性 length

遍历 oldStorage，根据哈希表新的容量大小 newLength 将原本哈希表中所有的数据重新哈希化 、插入数据即可

该方法难以用动图演示，所以大家好好理解一下，我们直接用代码来实现

function HashTable() {

// 属性

// 用于存储数据

this.storage = []

// 统计哈希表内数据个数

this.count = 0

// 设定哈希表初始长度

this.length = 7

//封装哈希函数

HashTable.prototype.hashFunc = function (str, size) {

let hashCode = 0

//取一个很大的数

for (let i = 0; i < str.length; i ++) {

hashCode = 37 * hashCode + str.charCodeAt(i)

}

//取余

return hashCode % size

}

//改变哈希表的容量

HashTable.prototype.resize = function(newLength) {

// 1.将旧的哈希表赋值给新变量

let oldStorage = this.storage

// 2.创建新的空数组作为新的哈希表容器

this.storage = []

// 3.修改哈希表容量

this.length = newLength

// 4.遍历旧的哈希表

for(let i = 0; i < oldStorage.length; i++) {

let box = oldStorage[i]

// 4.1 某索引位置上没有数据

if(box === null) {

continue;

}

// 4.2 某索引上有数据

for(let j = 0; j < box.length; j++) {

let inner_box = box[j]

// 4.2.1 将数据重新经过哈希化插入到新的哈希表中

this.put(inner_box[0], inner_box[1])

}

}

}

}

这里就不对该方法做过多的演示了，后面会在 put()方法 和 del() 方法的改写中用到

（9）实现isPrime()方法

isPrime()方法使用于判断某个数是否为质数的，因此也就只需要接收一个数字为参数即可。

因为我们要实现哈希表的自动扩容与减容，所以在每次容量改变的时候，需要判断新的容量是否为质数，以此来保证之后哈希表中的数据均匀地分布，所以我们还是有必要来封装一下这个方法的。

在说方法实现思路之前，我们来回顾一下，质数是只能被 1 和 自身 整除，因此我们来看一下数字 16，显然它不是一个质数，那来看看他能被哪些数整除吧

| 左 | 右 | 等于 |

| — | — | — |

| 1 | 16 | 16 |

| 2 | 8 | 16 |

| 4 | 4 | 16 |

| 8 | 2 | 16 |

| 16 | 1 | 16 |

非常明显地看到，只要一个数能被整除，那么一个数肯定是大于等于该数的算数平方根；另一个数肯定小于等于该数的算数平方根

因此，我们在判断一个数是否为质数时，只需从 2 开始逐个判断该数能否被整除，一直判断到该数的算数平方根即可

那么我们来看一下代码怎么实现的吧

function HashTable() {

// 属性

// 用于存储数据

this.storage = []

// 统计哈希表内数据个数

this.count = 0

// 设定哈希表初始长度

this.length = 7

//封装哈希函数

HashTable.prototype.hashFunc = function (str, size) {

let hashCode = 0

//取一个很大的数

for (let i = 0; i < str.length; i ++) {

hashCode = 37 * hashCode + str.charCodeAt(i)

}

//取余

return hashCode % size

}

//判断是是否为质数

HashTable.prototype.isPrime = function(number) {

// 1.获取算数平方根，并取整

let sqrt = Math.floor(Math.sqrt(number))

// 2.从2开始遍历到算数平方根

for(let i = 2; i

// 4.1 将哈希表容量扩大一倍

let newLength = this.length * 2

// 4.2 获取质数容量

newLength = this.toPrime(newLength)

// 4.3 扩容

this.resize(newLength)

}

}

}

（12）给del()方法增加减容功能

同样的，在我们的 del() 方法中会涉及到数据减少的情况，即 this.count --，那么此时我们就需要考虑哈希表是否需要减少容量，也就是填充因子是否小于 0.25，若小于并且哈希表容量大于7，则进行减容；否则不做处理

这里说一下为什么哈希表容量要大于7，因为在减容时，我们要将容量除以2，但哈希表的容量不方便太小太小，所以我就自己设定了一个容量的下限值为7，意思就是当哈希表容量小于或等于7时，即使填充因子小于0.25，也无需进行减容

实现思路：

在 this.count -- 之后，判断填充因子的大小，即 this.count / this.length 是小于 0.25，若大于 0.25，则不做任何处理

若小于 0.25 并且哈希表容量大于 7，则先获取一个原来哈希表容量一半的数 number，再调用 this.toPrime 方法获得一个离 number 最近的一个质数 prime

最后调用 this.resize 方法，并将 prime 作为参数传入，完成减容功能

我们直接来看代码

function HashTable() {

// 属性

// 用于存储数据

this.storage = []

// 统计哈希表内数据个数

this.count = 0

// 设定哈希表初始长度

this.length = 7

//封装哈希函数

HashTable.prototype.hashFunc = function (str, size) {

let hashCode = 0

//取一个很大的数

for (let i = 0; i < str.length; i ++) {

hashCode = 37 * hashCode + str.charCodeAt(i)

}

//取余

return hashCode % size

}

// 删除数据

HashTable.prototype.del = function (key) {

// 1.获取相应的下标值

let index = this.hashFunc(key, this.length)

let current = this.storage[index]

// 2. 判断该索引位置有无数据

// 2.1 该下标值位置没有数据，返回false，删除失败

if(!current) {

return false

}

// 2.2 该下标值位置有数据

// 3. 遍历数组查找对应数据

for (let i in current) {

let inner = current[i]

// 3.1 找到对应数据了，删除该数据

if(inner[0] === key) {

current.splice(i, 1)

this.count –

// 判断是否需要减容

if(this.count / this.length < 0.25 && this.length > 7) {

// 将哈希表容量减小一倍

let number = Math.floor(this.length / 2)

// 获取质数容量

number = this.toPrime(number)

// 减容

this.resize(number)

}

return inner[1]

}

}

// 3.2 没有找到对应数据，则删除失败，返回false

return false

}

}

七、结束语

==============================================================

哈希表的讲解就到这里了，希望大家对哈希表有了更深一层的理解。下一篇文章我将讲解一下树结构。

大家可以关注我，之后我还会一直更新别的数据结构与算法的文章来供大家学习，并且我会把这些文章放到【数据结构与算法】这个专栏里，供大家学习使用。

然后大家可以关注一下我的微信公众号：前端印象，等这个专栏的文章完结以后，我会把每种数据结构和算法的笔记放到公众号上，大家可以去那获取。

或者也可以去我的github上获取，欢迎大家点个Star

自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数前端工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但对于培训机构动则几千的学费，着实压力不小。自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年Web前端开发全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上前端开发知识点，真正体系化！

由于文件比较大，这里只是将部分目录大纲截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且后续会持续更新

如果你觉得这些内容对你有帮助，可以添加V获取：vip1024c （备注前端）

ES6

列举常用的ES6特性：

箭头函数需要注意哪些地方？

let、const、var

拓展：var方式定义的变量有什么样的bug？

Set数据结构

拓展：数组去重的方法

箭头函数this的指向。

手写ES6 class继承。

微信小程序

简单描述一下微信小程序的相关文件类型?

你是怎么封装微信小程序的数据请求？

有哪些参数传值的方法？

你使用过哪些方法，来提高微信小程序的应用速度？

小程序和原生App哪个好？

简述微信小程序原理？

分析微信小程序的优劣势

怎么解决小程序的异步请求问题？

其他知识点面试

webpack的原理

webpack的loader和plugin的区别？

怎么使用webpack对项目进行优化?

防抖、节流

浏览器的缓存机制

描述一下二叉树, 并说明二叉树的几种遍历方式?

项目类问题

笔试编程题：

技术栈比较搭，基本用过的东西都是一模一样的。快手终面喜欢问智力题，校招也是终面问智力题，大家要准备一下一些经典智力题。如果排列组合、概率论这些基础忘了，建议回去补一下。

一个人可以走的很快，但一群人才能走的更远。不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎扫码加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！

份《2024年Web前端开发全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。** [外链图片转存中…(img-RsRSQ0DB-1712879960206)] [外链图片转存中…(img-VlxrWSij-1712879960206)] [外链图片转存中…(img-V1NHZnNT-1712879960207)] [外链图片转存中…(img-9ZQtvZVo-1712879960207)] [外链图片转存中…(img-kDMyu6qD-1712879960207)] [外链图片转存中…(img-IFR4LUmh-1712879960207)]

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上前端开发知识点，真正体系化！

由于文件比较大，这里只是将部分目录大纲截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且后续会持续更新

如果你觉得这些内容对你有帮助，可以添加V获取：vip1024c （备注前端） [外链图片转存中…(img-h9dfWL4U-1712879960208)]

ES6

列举常用的ES6特性：

箭头函数需要注意哪些地方？

let、const、var

拓展：var方式定义的变量有什么样的bug？

Set数据结构

拓展：数组去重的方法

箭头函数this的指向。

手写ES6 class继承。

微信小程序

简单描述一下微信小程序的相关文件类型?

你是怎么封装微信小程序的数据请求？

有哪些参数传值的方法？

你使用过哪些方法，来提高微信小程序的应用速度？

小程序和原生App哪个好？

简述微信小程序原理？

分析微信小程序的优劣势

怎么解决小程序的异步请求问题？

其他知识点面试

webpack的原理

webpack的loader和plugin的区别？

怎么使用webpack对项目进行优化?

防抖、节流

浏览器的缓存机制

描述一下二叉树, 并说明二叉树的几种遍历方式?

项目类问题

笔试编程题：

技术栈比较搭，基本用过的东西都是一模一样的。快手终面喜欢问智力题，校招也是终面问智力题，大家要准备一下一些经典智力题。如果排列组合、概率论这些基础忘了，建议回去补一下。

一个人可以走的很快，但一群人才能走的更远。不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎扫码加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！ [外链图片转存中…(img-BAgrAZPZ-1712879960208)]