Skip to main content

哈希

是什么​

哈希表的结构就是数组，但它神奇之处在于对下标值的一种变换，这种变换我们可以称之为哈希函数，通过哈希函数可以获取 HashCode。

怎么做​

class HashMap{
    constructor(size) {
        this.table = []
        // 模拟已经使用储存地址
        for(let i = 0; i < size; i++) {
        this.table.push([undefined, 0])
        }
        this.size = 0
    }

    //哈希函数:返回数据在空间占用的唯一地址（key）
    hashConversion(index) {
        let keyCode = 0
        for(let item of index) {
        keyCode += item.charCodeAt(0) // 方法返回 0 到 65535 之间的整数，表示给定索引处的 UTF-16 代码单元
        }
        let key = keyCode % this.table.length
        return key
    }

    //展示存储到哈希表中的所有数据，去除未使用的空间
    showAllData() {
        let result = []
        for (let item of this.table) {
        if(item[0] !== undefined) {
            result.push(item)
        }
        }
        return result
    }

    //增：用来向哈希表中填入数据
    set(index, value) {
        let key = this.hashConversion(index)

        // 计算可用储存空间
        while((this.table[key])[0] !== undefined && (this.table[key])[0] !== index) {
        key++
        if(key >= this.table.length) {
            throw new Error('已经没有可用空间')
        }
        }
        if ((this.table[key])[0] !== index) {
            this.size++
            this.table[key][0] = index
            this.table[key][1] = value
        }
    }
    //查：用来从哈希表中取值
    get(index){
        let key = this.hashConversion(index)
        // 防御性
        while((this.table[key])[0] !== undefined && (this.table[key])[0] !== index) {
        key++
        if(key >= this.table.length) {
            return undefined
        }
        }

        return this.table[key][1]
    }
    //查：判断哈希表中有没有该值
    has(index) {
        let key = this.hashConversion(index)
        // 防御性
        while((this.table[key])[0] !== undefined && (this.table[key])[0] !== index) {
        key++
        if(key >= this.table.length) {
            return false
        }
        }
        if((this.table[key])[0] !== undefined) {
        return true
        } else {
        return false
        }
    }

    // 删：用来删除哈希表的制定数据
    delete(index){
        let key = this.hashConversion(index)

        for(let item in this.table ){
        const k = item
        const v = this.table[item]
        if(index === v[0]){
            this.table[k] = [undefined, 0]
            this.size --
            return
        }
        }
    }
}

使用方法

let hashTable = new HashMap(5)
hashTable.set('name','xjn')
hashTable.set('age','27')
hashTable.set('sex','men')
// console.log(hashTable.get('name'))
// hashTable.delete('age')
console.log(hashTable.has('sex'))

console.log('hashTable',hashTable)
console.log('showAllData',hashTable.showAllData())

解决了什么问题​

优点是​

哈希表通常是基于数组实现的，但是相对于数组，它存在更多优势：

哈希表可以提供非常快速的插入-删除-查找操作； 无论多少数据，插入和删除值都只需要非常短的时间，即 O(1)的时间级。实际上，只需要几个机器指令即可完成； 哈希表的速度比树还要快，基本可以瞬间查找到想要的元素。但是相对于树来说编码要简单得多。

缺点是​

哈希表中的数据是没有顺序的，所以不能以一种固定的方式（比如从小到大 ）来遍历其中的元素。 通常情况下，哈希表中的 key 是不允许重复的，不能放置相同的 key，用于保存不同的元素。

怎么解决缺点​

与字典区别​

  1. 存值时： 哈希表以键值对的形式存入数据每个键对应一个值）， 存值时不允许重复(key 不能重复)

  2. 取值时： 键值对的排列具有无序性； 取值时找 key（键），value（值）与 key 对应； 显示数据要用 foreach 循环，foreach 从开始循环到结束，中间不会停下。

参考​