数据结构与算法6：用JavaScript 实现 哈希表 结构

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了数据结构与算法6：用JavaScript 实现 哈希表 结构，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3704字，纯文字阅读大概需要6分钟。

内容图文

哈希表（hash table ） 是一种根据关键字直接访问内存存储位置的数据结构，通过哈希表，数据元素的存放位置和数据元素的关键字之间建立起某种对应关系，建立这种对应关系的函数称为哈希函数 。

常用方法：

• put(key, value) 插入&修改操作
• get(key) 获取元素
• remove(element) 删除元素
• size() 查看集合元素个数
• 其它：自动扩容/缩容

// 封装哈希表类
function HashTable() {
    // 属性: 数组（链址法）、 记录当前数组元素个数、 数组长度
    this.storage = [];
    this.count = 0;
    this.limit = 7;

    // 方法
    // 1 哈希函数 (数据, 数组大小)
    HashTable.prototype.hashFunc = function (str, size) {
        // hashCode变量初始化
        let hashCode = 0;
    
        // 利用霍纳算法,计算hashCode,此处用UniCode编码
        for (let i = 0; i < str.length; i++) {
            hashCode = 37 * hashCode + str.charCodeAt(i);
            // 37为质数步长
        }
    
        // 压缩hashCode
        return hashCode % size
    }

    // 2 插入&修改操作
    HashTable.prototype.put = function (key, value) {
        // 1. 根据key获取索引值: 将数据插入到对应的位置
        let index = this.hashFunc (key, this.limit);

        // 2. 根据索引值取出bucket: a.如果bucket不存在,则创建
        let bucket = this.storage[index] ; 

        // 判断bucket 是否为空
        if (bucket == null) {
            this.storage[index] = [[key, value]];
            this.count ++;
            // this.storage[index].push([key, value])
            // bucket = [];
            // this.storage[index] = bucket;
            return
        }

        // 3. 判断是新增还是修改: 若已存在值,则为修改;若不存在,则添加
        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i][0] === key) {
                bucket[i][1] = value;
                return
            }
        }

        // 添加操作
        bucket.push([key, value]);
        this.count ++;

        // 判断是否需要扩容
        if (this.count > this.limit * 0.75) {
            // 获取扩容质数
            let newPrime = this.getPrime(this.limit * 2)
            this.resize(newPrime)
        }
    }

    // 3 获取元素方法
    HashTable.prototype.get = function (key) {
        // 获取hashCode
        let index = this.hashFunc(key, this.limit);

        // 获取当前bucket
        let bucket = this.storage[index];

        // 判断是否存在
        if (bucket == null) {
            return null
        }

        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i][0] === key) {
                return bucket[i][1]
            }
        }
        return null
    }

    // 4 删除操作
    HashTable.prototype.remove = function (key) {
        // 获取hashCode
        let index = this.hashFunc(key, this.limit);

        // 获取当前bucket
        let bucket = this.storage[index];

        // 判断是否存在
        if (bucket == null) {
            return null
        }

        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i][0] === key) {
                let remValue = bucket[i][1];
                bucket.splice(i, 1);
                this.count --;

                // 判断是否需要缩容
                if (this.count >= 14 && this.count < this.limit * 0.25) {
                    // 获取质数
                    let newPrime = this.getPrime(Math.floor(this.limit / 2))
                    this.resize(newPrime)
                }
                return remValue
            }
        }
        return null
    }

    // 5 判断哈希表是否为空
    HashTable.prototype.isEmpty = function () {
        return this.count === 0
    }

    // 6 获取哈希表中元素的个数
    HashTable.prototype.size = function () {
        return this.count
    }

    // 7 哈希表容量更改(扩容/缩容)
    HashTable.prototype.resize = function (newLimit) {
        // 保存旧数据,更新哈希表
        let oldStorage = this.storage;
        let oldLimit = this.limit;
        this.storage = [];
        this.count = 0;
        this.limit = newLimit;

        // 遍历哈希表
        for (let i = 0; i < oldLimit; i++) {
            let bucket = oldStorage[i];

            // 判断是否存在数据
            if (bucket == null) {
                continue
            }

            for (let j = 0; j < bucket.length; j++) {
                // 调用put方法
                this.put(bucket[j][0], bucket[j][1]);
            }
        }
    }

    // 7.1 判断是否为质数
    HashTable.prototype.isPrime = function (num) {  
        // 开平方
        let temp = Math.floor(Math.sqrt(num)) 

        // 循环遍历
        for (let index = 2; index <= temp; index++) {
            if (num % index === 0 ){
                return false
            }
        }
        return true
    }

    // 7.2 获取质数
    HashTable.prototype.getPrime = function (num) {  
        while(!this.isPrime(num)){
            num++
        }
        return num
    }
}

// 测试哈希表

let ht = new HashTable();
ht.put('asd', '123');
ht.put('qwe', '123321');
ht.put('zccv', '978');
ht.put('dfh', '345');

console.log(ht)
// 获取大小
console.log(ht.isEmpty());
console.log(ht.size());

// 获取数据
console.log(ht.get('zccv'));

// 修改方法
ht.put('zccv', 999);
console.log(ht.get('zccv'));

// 删除方法
ht.remove('zccv');
console.log(ht.get('zccv'));

内容总结

以上是互联网集市为您收集整理的数据结构与算法6：用JavaScript 实现 哈希表 结构全部内容，希望文章能够帮你解决数据结构与算法6：用JavaScript 实现 哈希表 结构所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端