更快的取值方式之散列表

该文章由 leevare 发布于 ,归类于 Javascript

散列算法的作用是尽可能快的在数据结构中找到一个值。如果使用数组,或是链表的方式存取数据,要想查找一个特定的值,必须要遍历整个数据结构。但是,如果使用散列的方式,就相当于知道了这个值的位置,因此就可以轻松快速地获取该值。

在创建散列表之前,需要创建一个散列函数。散列函数的作用是给定一个键值,然后返回值在表中的地址。

const getHashCode = function (key) {
    let hash = 5381
    for (let i = 0, l = key.length; i < l; i++) {
        hash = hash * 33 + key.charCodeAt(i)
    }
    return hash % 1013
}

一个表现良好的散列函数由几个方面构成:插入和检索元素的时间,当然也要包括较低的散列冲突(也叫做散列碰撞)可能性,因为key值经过散列函数处理之后与散列的值并不是一一对应的,这就会出现多个key对应同一个地址,然后就出现了散列冲突。

为了解决散列冲突问题,常见的有:分离链接法、线性探查法等。

所谓分离链接法,就是在散列表的每一个位置创建一个链表,并将元素存储在里面。第一次存储时,计算的位置还没有值,那么就新创建一个链表,将值保存于链表中,再将链表存储到该位置。如果下次散列地址计算到了相同的位置,就在当前位置的链表中追加元素即可。

分离链接法

分离链接法(图片来源于网络)

再一个是线性探查。当计算的位置已经有值时,则探查当前位置+1的位置是否有值,如果仍然有值,再探查+2的位置,以此往复,直到探查的位置无值,将值保存到探查到的位置。

以下代码基于线性探查实现:

let HashTable = (function () {
    const getHashCode = function (key) {
        let hash = 5381
        for (let i = 0, l = key.length; i < l; i++) {
            hash = hash * 33 + key.charCodeAt(i)
        }
        return hash % 1013
    }
    let items = []

    const ValuePair = class {
        constructor(key, value) {
            this.key = key
            this.value = value
        }

        toString() {
            return `[key:${this.key} value:${this.value}]`
        }
    }

    class HashTable {

        put(key, value) {
            let position = getHashCode(key);
            if (items[position] === undefined) {
                items[position] = new ValuePair(key, value)
            } else {
                let index = position
                while (++index) {
                    if (items[position] === undefined) {
                        items[position] = new ValuePair(key, value)
                        break;
                    }
                }
            }
        }

        remove(key) {
            let position = getHashCode(key)
            if (items[position] !== undefined) {
                if (items[position].key === key) {
                    items[position] = undefined
                } else {
                    let index = ++position
                    while (items[index] === undefined || items[index].key !== key) {
                        index++
                    }

                    if (items[index].key === key) {
                        items[index] = undefined
                    }
                }
            }
        }

        get(key) {
            let position = getHashCode(key)
            if (items[position] !== undefined) {
                if (items[position].key === key) {
                    return items[position].value
                } else {
                    let index = ++position
                    while (items[index] === undefined || items[index].key !== key) {
                        index++
                    }
                    if (items[index].key === key) {
                        return items[index].value
                    }
                }
            } else {
                return undefined
            }
        }

        toString() {
            let str = ''
            for (let i = 0; i < items.length; i++) {
                if (items[i] !== undefined) {
                    str += items[i].toString() + "\r\n"
                }
            }
            return str
        }
    }

    return HashTable
}())

const hashTable = new HashTable()
hashTable.put('a', 'hello Jason')
hashTable.put('b', 'hello Mick')
console.log(hashTable.toString());
console.log(hashTable.get('a'));
hashTable.remove('a')
console.log(hashTable.toString());

// 输出:
// [key:a value:hello Jason]
// [key:b value:hello Mick]
//
// hello Jason
// [key:b value:hello Mick]

如果觉得我的文章对您有用,请您随意打赏。您的支持将鼓励我更加努力创作!

相关文章:

说点什么

avatar
300
  Subscribe  
提醒