哈希表（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'));